Основы дискретной математики

Числа вершинного и реберного покрытий графа на рис.1.1:

(вершины v₂, v₃, v₄, v₅ или v₂, v₃, v₄, v₆ или v₁, v₃, v₄, v₆ или v₁, v₃, v₄, v₅ или v₁, v₂, v₄, v₅).

(ребра e₁, e₅, e₉ или e₁, e₆, e₈).

1.2.7 Вершинное и реберное число внешней устойчивости графа

Множество ТÌV графа G=(V, Г) называют внешне устойчивым, если любая вершина, не принадлежащая Т, соединена ребрами с вершинами из Т, т.е. для любого хÏТ имеет место ГхÇТ¹Æ.

Множество внешней  устойчивости, содержащее наименьшее число элементов, называется наименьшим внешне устойчивым множеством, а число  элементов этого множества –  вершинным числом внешней устойчивости b₀(G) графа G.

Минимальная мощность множества ребер, покрывающих  все ребра графа, называется реберным числом внешней устойчивости b₁(G) графа G.

Вершинное и  реберное числа внешней устойчивости графа на рис.1.1:

b₀(G)=2 (вершины v₂, v₅; v₂, v₆; v₃, v₄)

b₁(G)=2 (ребра )

1.2.8 Радиус и диаметр графа

Для фиксированной  вершины v целое число R(v)=max d(v, w), wÎV соответствует расстоянию от v до наиболее удаленной вершины.

Радиус R₀= min R(v)= R(v₀), vÎV, вершину v₀ считают центром графа.

Диаметром связного графа называется максимальное расстояние между парами вершин.

1. Радиус графа G:

Считая точку v₄ центром графа R₀ (G) = 7.

2. Диаметр графа G:

T(G) = 15 (расстояние между парами вершин v₁ и v₆)

 

1.3 Задача теории графов.

Задача  на самый короткий путь

Решение задачи с помощью алгоритма Флойда – Уоршелла.

Алгоритм  Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами  взвешенного ориентированного графа. Этот алгоритм частично реализует метод динамического программирования. Алгоритм пошаговый, состоит из n+1 этапа, где n – число вершин.

Основная  идея метода Флойда. Пусть есть три узла i, m и j и заданы расстояния между ними (рис. 2). Если выполняется неравенство d_im + d_mj < d_ij, то целесообразно заменить путь i -> j путем i -> m -> j. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Рис.2. Треугольный оператор

Пусть вершины графа  пронумерованы от 1 до n.

Обозначим через длину кратчайшего пути от i до j, который кроме самих вершин проходит только через вершины (это расстояние между i-ой и j-ой вершинами, где присутствует m промежуточных вершин).

Очевидно, что  — длина (вес) ребра , если таковое существует. Если не существует прямого пути из вершины i в вершину j, его длина обозначается как . Расстояние от вершины до ее самой равно 0 ().

Существует два варианта значения :

1. Кратчайший путь между не проходит через вершину m, тогда
2. Существует более короткий путь между , проходящий через m, тогда он сначала идёт от i до m, а потом от m до j. В этом случае, очевидно,

Таким образом, для нахождения значения функции достаточно выбрать минимум  из двух обозначенных значений.

Тогда рекуррентная формула для  имеет вид:

 — длина ребра

 

Алгоритм Флойда — Уоршелла последовательно  вычисляет все значения , для m от 1 до n. Полученные значения являются длинами кратчайших путей между вершинами .

Построим начальную матрицу расстояний , содержащую элементы , т.е матрицу начальных расстояний между всеми вершинами графа (между 1-й вершиной и остальными, между 2-й вершиной и остальными и т.д.)

 

На основе матрицы  построим матрицу , элементы которой вычисляются по формуле

 

В этой матрице первые строка и  столбец переписываются без изменения.

Далее, построим матрицу  , элементы которой удовлетворяют условию . (Вторые строку и столбец переписываем).

 

Обозначим m-ю строку и m-й столбец (в матрицах выделены серым) как ведущую строку и ведущий столбец. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратах) меньше элементов, находящихся в пересечении столбца и строки (показанных в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами:

Рис.3. Иллюстрация  алгоритма Флойда

 

 

Аналогично построению матрицы , используя треугольный оператор построим матрицы :

 

 

 

Результатом расчетов будет самый  короткий путь из вершины v₁ в вершину v₆, равный 13

 

2. . СИНТЕЗ ЛОГИЧЕСКИХ СХЕМ

Формальная  логика делится на три подраздела: логику Буля, логику высказываний и  логику предикатов. «Логика Буля»  основывается на отношении эквивалентности, при котором правая часть равенства  всегда содержит ровно столько же «истины», сколько и левая. Два  последующих раздела базируются уже на отношении порядка, при  котором правая часть выражения  содержит больше «истины», чем левая  [3].

Логической  называют переменную, которая может  принимать одно из двух возможных  значений – «1» или «0» («истина» или «ложь», «да» или «нет»). Логические переменные обозначаются Х_i. Чаще всего под индексом подразумевают разряд двоичного числа, соответствующего набору логической переменной.

Функция, определенная на наборах (x_n-1, …, х_i, …, x₁, x₀) и принимающая на этих наборах значения 0 или 1, называется функцией алгебры логики (ФАЛ, логической функцией, булевой функцией)[2].

2.1 Таблица истинности для заданной  функции алгебры логики

Задавая значения функции алгебры логики на всех возможных  наборах логических переменных (обычно в порядке возрастания их номеров) можно построить таблицу истинности функции алгебры  логики. В этом состоит табличный способ задания  логической функции.

Используя таблицы  истинности, определяющие элементарные функции, можно задать в виде таблицы  истинности любую функцию алгебры  логики, являющуюся суперпозицией этих функций. При этом следует учитывать  приоритеты логических функций.

 

Рассмотрим  заданную функцию:

 

Cоставим таблицу истинности (табл.2.1):

Таблица 2.1

							(1)	(2)	(3)	(4)	(5)	(6)
	x4	x3	x2	x1	x0
1	0	0	0	0	0	1	0	0	1	1	1	0	0
2	0	0	0	0	1	1	0	0	1	1	1	0	0
3	0	0	0	1	0	0	1	0	1	1	1	0	1
4	0	0	0	1	1	0	1	0	1	1	1	0	1
5	0	0	1	0	0	1	0	1	0	1	1	0	0
6	0	0	1	0	1	1	0	1	0	1	1	0	0
7	0	0	1	1	0	0	1	1	0	1	1	0	1
8	0	0	1	1	1	0	1	1	0	1	1	0	1
9	0	1	0	0	0	1	1	0	1	0	1	0	1
10	0	1	0	0	1	1	1	0	1	0	0	1	1
11	0	1	0	1	0	0	1	0	1	0	1	0	1
12	0	1	0	1	1	0	1	0	1	0	0	1	1
13	0	1	1	0	0	1	1	1	0	1	1	0	1
14	0	1	1	0	1	1	1	1	0	1	1	0	1
15	0	1	1	1	0	0	1	1	0	1	1	0	1
16	0	1	1	1	1	0	1	1	0	1	1	0	1
17	1	0	0	0	0	1	0	1	0	1	1	0	0
18	1	0	0	0	1	1	0	1	0	1	1	0	0
19	1	0	0	1	0	0	1	1	0	1	1	0	1
20	1	0	0	1	1	0	1	1	0	1	1	0	1
21	1	0	1	0	0	1	0	1	0	1	1	0	0
22	1	0	1	0	1	1	0	1	0	1	1	0	0
23	1	0	1	1	0	0	1	1	0	1	1	0	1
24	1	0	1	1	1	0	1	1	0	1	1	0	1
25	1	1	0	0	0	1	1	1	0	1	1	0	1
26	1	1	0	0	1	1	1	1	0	1	1	0	1
27	1	1	0	1	0	0	1	1	0	1	1	0	1
28	1	1	0	1	1	0	1	1	0	1	1	0	1
29	1	1	1	0	0	1	1	1	0	1	1	0	1
30	1	1	1	0	1	1	1	1	0	1	1	0	1
31	1	1	1	1	0	0	1	1	0	1	1	0	1
32	1	1	1	1	1	0	1	1	0	1	1	0	1

 

 

2. Совершенные дизъюнктивная и конъюнктивная нормальные формы

Логические  функции для удобства записи выражают в виде суммы произведений логических переменных или в виде произведений их сумм. Первая запись называется дизъюнктивной  нормальной формой, а вторая конъюнктивной  нормальной формой. Для каждой  логической функции может существовать несколько  равносильных дизъюнктивных и конъюнктивных  форм, однако существует только один вид  нормальной формы, в котором функция  может быть записана единственным образом  совершенные дизъюнктивные и  конъюнктивные нормальные формы (СДНФ и СКНФ). В СДНФ функция записывается в виде логической суммы конститутиент единицы (минтермов), а в СКНФ – в виде логического произведения конститутиент нуля (макстермов). Конститутиент единицы и нуля – это комбинации переменных, при которых функция соответственно обращается в единицу или нуль.

Напишем совершенные  дизъюнктивную и конъюнктивную  нормальные формы для заданной функции:

Сложность функции 

 

Сложность функции  

2. Анализ функции алгебры логики на принадлежность к классам

Существует  пять классов логических функций. При анализе функции алгебры логики (ФАЛ) можно определить ее принадлежность (или не принадлежность) к каждому из этих классов.

1. Класс функций сохраняющих ноль

Логическая  функция f(x_n-1, …, x₁, x₀) принадлежит к классу ФАЛ, сохраняющих константу нуля К₀, если при всех x_i=0, где i=0, 1, …, (n-1), выполняется равенство .

Проверим  принадлежность заданной функции к  этому классу ФАЛ:

так как , то данная функция алгебры логики принадлежит к классу функций сохраняющих ноль, т.е .

1. Класс функций сохраняющих единицу

Логическая  функция f(x_n-1, …, x₁, x₀) принадлежит к классу ФАЛ, сохраняющих константу единицы К₁, если при всех x_i=1, где i=0, 1, …, (n-1), выполняется равенство .

Проверим  принадлежность заданной функции к  этому классу ФАЛ:

так как , то данная функция алгебры логики принадлежит к классу функций сохраняющих единицу, т.е..

2. Класс линейных функций

Логическая  функция f(x_n-1, …, x₁, x₀) принадлежит к классу линейных ФАЛ К_л в том случае, когда её можно описать выражением

;     где Å, - знаки операции сложения по модулю 2.

Проверим  принадлежность заданной функции к этому классу ФАЛ:

 

Коэффициент С находим на наборе <0,0,0,0,0>

 

Коэффициент находим на наборе <0,0,0,0,1>

 

Коэффициент находим на наборе <0,0,0,1,0>

 

Коэффициент находим на наборе

 

Коэффициент находим на наборе

 

Коэффициент находим на наборе 

 

 

Сравниваем  наборы функции:

…

В 13-й строке идет несовпадение, значит функция не линейная, т.е. .

3. Класс самодвойственных функций

Логическая  функция f(x_n-1, …, x₁, x₀) принадлежит к классу самодвойственных ФАЛ К_с, если для неё справедливо выражение

 

Проверим принадлежность заданной функции к этому классу ФАЛ:

Исходная функция:

 

Самодвойственная функция:

 

Табл.2.2

										(1)	(2)	(3)	(4)	(5)	(6)	(7)
	x4	x3	x2	x1	x0
1	0	0	0	0	0	1	1	1	1	1	1	0	1	1	0	1	0	0
2	0	0	0	0	1	1	1	1	0	1	1	0	1	1	0	1	0	0
3	0	0	0	1	0	1	1	1	1	1	1	0	1	1	0	1	0	1
4	0	0	0	1	1	1	1	1	0	1	1	0	1	1	0	1	0	1
5	0	0	1	0	0	1	1	0	1	1	1	0	1	1	0	1	0	0
6	0	0	1	0	1	1	1	0	0	1	1	0	1	1	0	1	0	0
7	0	0	1	1	0	1	1	0	1	1	1	0	1	1	0	1	0	1
8	0	0	1	1	1	1	1	0	0	1	1	0	1	1	0	1	0	1
9	0	1	0	0	0	1	0	1	1	1	1	0	1	1	0	1	0	1
10	0	1	0	0	1	1	0	1	0	1	1	0	1	1	0	1	0	1
11	0	1	0	1	0	1	0	1	1	0	1	0	1	1	0	0	1	1
12	0	1	0	1	1	1	0	1	0	0	1	0	1	1	0	0	1	1
13	0	1	1	0	0	1	0	0	1	1	1	0	1	1	0	1	0	1
14	0	1	1	0	1	1	0	0	0	1	1	0	1	1	0	1	0	1
15	0	1	1	1	0	1	0	0	1	0	1	0	1	1	0	0	1	1
16	0	1	1	1	1	1	0	0	0	0	1	0	1	1	0	0	1	1
17	1	0	0	0	0	0	1	1	1	1	1	0	1	1	0	1	0	0
18	1	0	0	0	1	0	1	1	0	1	1	0	1	1	0	1	0	0
19	1	0	0	1	0	0	1	1	1	1	1	0	1	1	0	1	0	1
20	1	0	0	1	1	0	1	1	0	1	1	0	1	1	0	1	0	1
21	1	0	1	0	0	0	1	0	1	1	0	1	0	0	1	1	0	0
22	1	0	1	0	1	0	1	0	0	1	0	1	0	1	0	1	0	0
23	1	0	1	1	0	0	1	0	1	1	0	1	0	0	1	1	0	1
24	1	0	1	1	1	0	1	0	0	1	0	1	0	1	0	1	0	1
25	1	1	0	0	0	0	0	1	1	1	1	0	1	1	0	1	0	1
26	1	1	0	0	1	0	0	1	0	1	1	0	1	1	0	1	0	1
27	1	1	0	1	0	0	0	1	1	0	1	0	1	1	0	0	1	1
28	1	1	0	1	1	0	0	1	0	0	1	0	1	1	0	0	1	1
29	1	1	1	0	0	0	0	0	1	1	0	1	1	1	0	1	0	1
30	1	1	1	0	1	0	0	0	0	1	0	1	1	1	0	1	0	1
31	1	1	1	1	0	0	0	0	1	0	0	1	1	1	0	0	1	1
32	1	1	1	1	1	0	0	0	0	0	0	1	1	1	0	0	1	1