Решение практических заданий по дискретной математике (стр. 3 из 4)

Строим таблицу :

(000)0	(001)1	(010)2	(011)3	(100)4	(101)5	(110)6	(111)7
1	1	1	0	0	0	0	0

Из таблицы видно, что на наборах 3 и 4 функция принимает одинаковые значения. Следовательно,

.

5. Принадлежность функции к классу

.

Из таблицы видно, что 111 > 000 , но

. Следовательно, .

Строим критериальную таблицу:

К0	К1	КЛ	КС	КМ
f1	-	-	-	-	-
f2	-	-	-	-	-

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

является полной .

Найдем все возможные базисы. По критериальной таблице составим КНФ :

.

Приведем КНФ к ДНФ :

.

По полученной ДНФ выписываем искомые базисы:

.

Задание 5

Минимизировать булеву функцию

по методу Квайна – Мак-Класки.

Решение:

1 этап. Определение сокращенной ДНФ.

По десятичным эквивалентам запишем 0-кубы :

Выполним разбиение на подгруппы:

.

Строим

-кубы, сравнивая соседние группы (значок (*) указывает на участие данной импликанты в склеивании):

Выполняем разбиение всех

-кубов в зависимости от расположения независимой переменной Х :

.

Выполняем сравнение кубов внутри каждой подгруппы с целью построения

-кубов (значок (*) указывает на участие данной импликанты в склеивании):

.

Выполняем сравнение кубов внутри каждой подгруппы с целью построения

-кубов (значок (*) указывает на участие данной импликанты в склеивании):

или

.

Так как они одинаковы, то

.

Запишем сокращенную ДНФ, в которую должны быть включены им-пликанта из К ³ и импликанты, не участвовавшие в склеивании (в нашем случае таких импликант нет) :

.

2 этап. Определение тупиковой ДНФ.

Так как все импликанты участвовали в склеивании, и сокращенная ДНФ состоит из одной простой импликанты, то строить таблицу покрытий нет необходимости, т.е.

.

Задание 6

Для неориентированного графа

, у которого ,

а) вычислить числа

;

б) определить хроматическое число

.

Решение:

Построим граф:

а) Вычислим числа

.

1)

:

Используя алгоритм выделения пустых подграфов, построим дерево:

Согласно определению

:

.

2)

:

Используя алгоритм выделения полных подграфов, построим дерево:

Здесь

- полные подграфы. Видно, что мощность носителей всех подграфов равна трем, т.е.

.

3)

:

Построим модифицированную матрицу смежности

заданного графа G :

1 2 3 4 5 6

.

Находим минимальное число строк, покрывающих все столбцы модифи-цированной матрицы . Таких строк – одна. Следовательно,

.

б) Определим хроматическое число

.

Согласно алгоритму минимальной раскраски вершин графа, выделим все пустые подграфы графа G , т.е. построим дерево (оно построено в пункте а) ):

Построим таблицу:

1 2 3 4 5 6

1. {1,4,6} 1 1 1

2. {1,5} 1 1

3. {2,5} 1 1

4. {2,6} 1 1

5. {3} 1

Определяем минимальное число строк, покрывающих все столбцы таблицы. Такими строками могут быть строки 1, 3, 5. Значит,

.

Зададимся красками: для множества вершин

- краска синяя (С ), для множества вершин - краска красная ( К ), для множества вершин - краска зеленая ( З ).

Раскрасим вершины графа G :

Задание 7

Для заданной сети

:

а) найти величину минимального пути и сам путь от вершины

до вершины по алгоритму Дейкстры ;

б) используя алгоритм Форда-Фалкерсона, определить максимальный поток

( v₁ – вход , v₆ – выход сети ) и указать минимальный разрез, отделяющий v₁ от v₆ ,

если задана матрица весов (длин, пропускных способностей) Р :

v₁v₂v₃ v₄v₅ v₆

Решение:

Построим сеть:

а) Найдем величину минимального пути и сам путь сети G . Используем для этого алгоритм Дейкстры.

Этап 1. Нахождение длины кратчайшего пути.

.

Шаг 1. Полагаем

1-я итерация.

Шаг 2. Составим множество вершин, непосредственно следующих за

с временными метками: . Пересчитываем временные метки этих вершин: ,