86364 (575067), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Фиксируем набор 000:

,

,

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

Фиксируем набор 100:

,

,

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

Фиксируем набор 010:

,

,

.

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

Фиксируем набор 001:

,

,

, .

Следовательно, функция (по нашему предположению) может быть представлена полиномом вида:

.

Если функция линейная, то на всех остальных наборах ее значение должно равняться 1. Но на наборе 111 . Значит, функция не является линейной, т.е. .

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

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

Вычисляем . Вычисляем значения функции на оставшихся наборах:

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

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

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

Из таблицы видно: 000 < 111 , но . Следовательно, .

Рассмотрим функцию .

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

.

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

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

.

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

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

Предполагаем, что

.

Фиксируем набор 000:

,

.

Фиксируем набор 100:

,

.

Фиксируем набор 010:

,

.

Фиксируем набор 001:

,

.

Окончательно получаем

.

Это равенство не соблюдается на наборе 011:

,

.

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

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

Вычислим значения функции на оставшихся наборах:

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

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

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

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

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

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

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

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

.

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

.

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

.

Задание 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. Составим множество вершин, непосредственно следующих за с временными метками: . Пересчитываем временные метки этих вершин: ,

.

Шаг 3. Одна из временных меток превращается в постоянную:

Шаг 4. Следовательно, возвращаемся на второй шаг.

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

Шаг 2.

Шаг 3.

Шаг 4. Переход на второй шаг.

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

Шаг 2.

Шаг 3.

Шаг 4.

Переход на второй шаг.

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

Шаг 2.

Шаг 3.

Шаг 4. Переход на второй шаг.

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

Шаг 2.

Шаг 3.

Шаг 4. Конец первого этапа.

Следовательно, длина кратчайшего пути равна .

Этап 2. Построение кратчайшего пути.

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

Шаг 5. Составим множество вершин, непосредственно предшествующих с постоянными метками : Проверим равенство

для этих вершин:

т.е.

т.е.

Включаем дугу в кратчайший путь,

Шаг 6. Возвращаемся на пятый шаг.

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

Шаг 5.

Включаем дугу в кратчайший путь, .

Шаг 6. . Завершение второго этапа.

Следовательно, кратчайший путь построен. Его образует последовательность дуг: .

Окончательно, кратчайший путь от вершины до вершины v₆ построен. Его длина (вес) равна . Сам путь образует последовательность дуг:

б) Определим максимальный поток через сеть G. Для этого используем алгоритм Форда-Фалкерсона.

Выбираем произвольно путь из вершины v₁ в вершину v₆ . Пусть это будет путь . Минимальную пропускную способность на этом пути, равную 10, имеет дуга , т.е. Увеличим на этом пути поток до 10 единиц. Дуга становится насыщенной. Дуга имеет на данный момент пропускную способность, равную 10.

Путь Следовательно, поток на этом пути можно увеличить на 9 единиц. Дуги становятся насыщенными.

Других маршрутов нет (другие маршруты проходят через насыщенные дуги). Поток максимален. Делаем разрез вокруг вершины v₁ по насыщенным дугам

и получаем его величину единиц.

8. Используя алгоритм Краскала, построить остов с наименьшим весом для неориентированного взвешенного графа , у которого , если заданы веса (длины) ребер:

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

1. Упорядочим ребра в порядке неубывания веса (длины):

2. Возьмем ребро u₁ и поместим его в строящийся остов.

Возьмем ребро u₂ и поместим его в строящийся остов (т.к. оно не образует с предыдущим ребром цикла).

Берем ребро u₃ и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).

Берем ребро u₄ и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).

Берем ребро u₅ и помещаем его в строящийся остов (т.к. оно не образует цикла с предыдущими ребрами).

Ребра не рассматриваем, т.к. они образуют циклы с предыдущими ребрами.

Проверим окончание алгоритма. Число входящих в остов ребер равно 5. Заданный граф имеет п = 6 вершин и . Таким образом, остов содержит все вершины заданного графа G .

Вес (длина) построенного остова

равен .

Литература

1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.

2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энерго атомиздат, 1987. – 496 с.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 480 с.

4. Шапорев С.Д. Дискретная математика. – СПб.: БХВ-Петербург, 2006. - 400 с.

5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2005. – 416 с.

6. Хаханов В.И., Чумаченко С.В. Дискретная математика ( конспект теоретического материала). – Харьков: ХНУРЭ, 2003. – 246 с.

7. Богданов А.Е. Курс лекций по дискретной математике.–Северодонецк: СТИ, 2006. – 190 с.

Характеристики

Список файлов ответов (шпаргалок)