Xreferat.com » Рефераты по математике » Решение практических заданий по дискретной математике

Решение практических заданий по дискретной математике

математике" width="191" height="24" align="BOTTOM" border="0" />,

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


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


Решение практических заданий по дискретной математике,

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

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


Решение практических заданий по дискретной математике,

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


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


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


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


Решение практических заданий по дискретной математике,

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


Следовательно, Решение практических заданий по дискретной математике.

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-кубы :


Решение практических заданий по дискретной математике


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


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


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


Решение практических заданий по дискретной математике


Выполняем разбиение всех Решение практических заданий по дискретной математике-кубов в зависимости от расположения независимой переменной Х :


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


Выполняем сравнение кубов внутри каждой подгруппы с целью построения Решение практических заданий по дискретной математике-кубов (значок (*) указывает на участие данной импликанты в склеивании):


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


Выполняем сравнение кубов внутри каждой подгруппы с целью построения Решение практических заданий по дискретной математике-кубов (значок (*) указывает на участие данной импликанты в склеивании):


Решение практических заданий по дискретной математике или

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


Так как они одинаковы, то Решение практических заданий по дискретной математике.

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


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


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


Для заданной сети Решение практических заданий по дискретной математике:

а) найти величину минимального пути и сам путь от вершины Решение практических заданий по дискретной математике Решение практических заданий по дискретной математике до вершины Решение практических заданий по дискретной математике по алгоритму Дейкстры ;

б) используя алгоритм Форда-Фалкерсона, определить максимальный поток Решение практических заданий по дискретной математике ( v1 – вход , v6 – выход сети ) и указать минимальный разрез, отделяющий v1 от v6 ,

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


v1 v2 v3 v4 v5 v6

Решение практических заданий по дискретной математике


Решение:

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


Решение практических заданий по дискретной математике


а) Найдем величину минимального пути и сам путь сети 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. Решение практических заданий по дискретной математике. Завершение второго этапа.

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

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


Решение практических заданий по дискретной математике


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


Решение практических заданий по дискретной математикеРешение практических заданий по дискретной математике

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: