Код Прюфера

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ» (ФГБОУ ВПО МГГУ)

Факультет физико-математического образования, информатики и программирования

Кафедра прикладной математики и математических методов в экономике

Контрольная работа

По Дискретной математике

На тему: Код Прюфера

Выполнил студент: Ежов А.В.

Группы ББИ 1-го курса Заочной формы обучения

Преподаватель: Большакова Наталья Сергеевна

Ст. преподаватель кф. ПМ и ММэ

Мурманск

Задание №1

Создать псевдоорграф  с множеством вершин  и 15 рёбрами, построить диаграмму графа, матрицу инцидентности и матрицу соседства вершин. Для соотнесенного псевдографа построить матрицу соседства вершин.

Список рёбер:

е1=(1, 2); е2=(2, 3); е3=(3, 3); е4=(3, 4); е5=(4, 5); е6=(5, 5); е7=(5, 6); е8=(6, 7); е9=(7, 1); е10=(1, 1); е11=(5, 4); е12=(1, 6); е13=(3, 6); е14=(6, 3); е15=(2, 7).

Матрица инцидентности:

       е    1      2     3    4    5    6    7   8    9   10  11  12   13  14 15

Матрица соседства вершин:

                                     1    2     3     4    5    6   7

Для соотнесенного псевдографа построить матрицу соседства вершин:

                                     1     2    3    4    5    6    7

Задание № 2

С помощью алгоритма Прюфера восстановить по вектору дерево:

Код Прюфера:

(5,1,3,5,7,8,9,10).

V={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Вершины {2, 4, 6} являются висячими.

(5, 2) - первое ребро; укоротим код на один элемент

(1,3,5,7,8,9,10).

V={1, 3, 4, 5, 6, 7, 8, 9, 10}

Вершины 1, 3 есть в коде, они отмечены красным. Поэтому вершину 1 соединяем с вершиной 4.

(1, 4)

(3,5,7,8,9,10).

V={1, 3, 5, 6, 7, 8, 9, 10}

(3, 1), (5, 3), (7, 5), (8, 6), (9, 7), (10, 8), (9, 10)

Проверка

Закодируем существующее дерево в код Прюфера. Если решение правильно, то коды должны совпасть.

. Найти висячую вершину с минимальным номером i.

. Записать в код Прюфера вершину, смежную с i.

. Удалить вершину i из дерева. Если дерево не пустое, то перейти к п.1.

Находим висячую вершину с минимальным номером. Минимальный номер 2, удаляем ребро соединяющую вершины 2 и 5, записываем в код 5.

 (5)

Теперь, висячая вершина с минимальным номером 4. Удаляем ребро между вершинами 4 и 1. Добавляем в код 1.

(5, 1)

убираем, 3 добавляем. Получается (5, 1, 3). Действие повторяем до тех пор, пока останется одно ребро с конечной вершиной. Результат кода сравним с первоначальным кодом.

 (5, 1, 3)

(5, 1, 3, 5)

(5, 1, 3, 5, 7)

(5, 1, 3, 5, 7, 8)

(5, 1, 3, 5, 7, 8, 9)

(5, 1, 3, 5, 7, 8, 9, 10)

Сравним:

(5, 1, 3, 5, 7, 8, 9, 10) = (5,1,3,5,7,8,9,10)

Коды равны, следовательно, решение было правильным.

Задание № 3

псевдограф матрица диаграмма прюфер

Для функции  построить таблицу истинности, СДНФ и СКНФ.

Таблица истинности:

Для построения СКНФ необходимо произвести следующие действия:

1.      Выбрать все строки из таблицы истинности, в которых значение функции равняется 0.

2.      Построить ЭД для каждой строки следующим образом: если значение переменной равно 1, то берется ее отрицание, иначе - сама переменная.

.        Объединить получившиеся ЭД конъюнкцией.

Строим СКНФ:

1. Выбираем 7 строку таблицы истинности, т.к. значение функции в этой строке равно 0.

. По правилам, получаем следующую ЭД: ¬x V ¬y V z

3. Т.к. ЭД всего одна, то она и будет СКНФ

Итак, для функции  получили следующую СКНФ: . ¬x V ¬y V z

Для построения СДНФ необходимо произвести следующие действия:

1.      Выбрать все строки из таблицы истинности, в которых значение функции равняется 1.

2.      Построить ЭК для каждой строки следующим образом: если значение переменной равно 0, то берется ее отрицание, иначе - сама переменная.

.        Объединить получившиеся ЭК дизъюнкцией.

Строим СДНФ.

1.      Выбираем 1, 2 , 3, 4, 5, 6 и 8 строки таблицы, т.к. значение функции в этих строках равно 1.

2.      По правилам получаем следующие ЭК:

¬x & ¬y & ¬z - для первой строки;

 ¬x & ¬y & z - для второй строки;

 ¬x & y & ¬z - для третьей строки;

 ¬x & y & z - для четвёртой строки;

 x & ¬y & ¬z - для пятой строки;

 x & ¬y & z - для шестой строки;

 x & y & z - для восьмой строки.

3.      Объединяем получившиеся конъюнкции дизъюнкцией и получаем СДНФ:

Итак, для функции  получили следующую СДНФ:

(¬x & ¬y & ¬z)V(¬x & ¬y & z)V(¬x & y & ¬z)V(¬x & y & z)V(x & ¬y & ¬z)(x & ¬y & z)V(x & y & z)