Теория графов и Теория кодирования

Дисциплина Дискретная математика

Заказчик	dmitry3431 ☆ 1 ✍ 2 ♥ 0
Вид работы	Контрольная
ВУЗ	Крымский инженерно-педагогический университет
Срок	05.06.2017
Преподаватель	Сейдаметова З.С.
Вариант	3
Бюджет	Не определен ₽

Теория графов
1.	Найти все попарно неизоморфные графы пятого порядка. Изобразить их диаграммой, а также записать с помощью матрицы смежности, матрицы инциденций, списком.
2.	Найти все попарно неизоморфные графы шестого порядка. Изобразить их диаграммой, а также записать с помощью матрицы смежности, матрицы инциденций, списком.
3.	Найти самодополнительный граф с минимальным отличным от 1 числом вершин.
4.	Докажите, что в связном графе любые две простые цепи максимальной длины имеют общую вершину.
5.	Задача Рамсея. Доказать, что среди 6 человек есть либо 3 попарно знакомых, либо 3 попарно незнакомых.
6.	Пусть Gn –– граф, множество вершин которого совпадает с отрезком натурального ряда {1, 2, …, n}, а множество ребер определяется следующим условием: несовпадающие вершины u и v смежны тогда, когда числа u и v взаимно просты. Запишите матрицу смежности графа G5, G7.
7.	Рассмотрим матрицу смежности ребер Q : array [1..q, 1..q] of 0..1, где
Q[i, j] =  
	Является ли матрица смежности ребер Q представлением в ЭВМ графа G.
8.	Постройте граф, центр которого:
А) состоит ровно из одной вершины;
Б) состоит из трех вершин и не совпадает с множеством всех вершин;
В) совпадает с множеством всех вершин.
9.	Постройте граф, центр которого:
А) состоит ровно из двух вершин;
Б) состоит из трех вершин и не совпадает с множеством всех вершин;
В) совпадает с множеством всех вершин.
10.	Приведите пример графа, диаметр и радиус которого равны.
11.	Изобразите произвольный связный граф одиннадцатого порядка. 
А) С помощью алгоритма определения двудольности графа выяснить является ли данный граф двудольным.
Б) Выберите в графе две вершины u и v, и найдите расстояние d((u, v).
12.	Изобразите с помощью диаграммы все попарно неизоморфные деревья седьмого порядка.
13.	Какой вид будут иметь дерево сортировки после того, как в него последовательно добавили следующие текстовые элементы 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 ?
14.	Изобразите граф 15-го порядка, содержащего не менее двух простых циклов. С помощью алгоритма поиска в ширину постройте остов данного графа.
15.	Доказать следующее утверждение. При uv всякий (u, v)-маршрут содержит простую (u, v)-цепь.
16.	Доказать следующее утверждение. Всякий цикл содержит простой цикл.
17.	Доказать следующее утверждение. Объединение двух несовпадающих простых (u, v)-цепей содержит простой цикл.
18.	Доказать следующее утверждение. Если C и D –– два несовпадающих простых цикла, имеющих общее ребро e, то граф (C  D) –– e также содержит простой цикл.
19.	Доказать следующее утверждение. Для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существует (u, v)-маршрут.
20.	Доказать следующее утверждение. Каждый граф представляется в виде дизъюнктного объединения своих связных компонент. Разложение графа на связные компоненты определено однозначно.
21.	Доказать следующее утверждение. Для любого связного графа либо он сам, либо его дополнение является связным.
22.	Доказать следующее утверждение. Пусть G –– связный граф, eEG. Тогда:
1)	если ребро e принадлежит какому-либо циклу графа G, то граф G –– е связен;
2)	если ребро e не входит ни в какой цикл, то граф G –– е имеет ровно две компоненты.
23.	Доказать следующее утверждение. Если k(G)=k для n-вершинного графа G, то 
n-k  m(G)  (n-k)(n-k+1)/2,
причем обе эти оценки для m(G) достижимы.
24.	Доказать теорему Кёнига. Для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины.
25.	На любом известном Вам алгоритмическом языке или на условном алгоритмическом языке описать алгоритм поиска в ширину. Обосновать алгоритм поиска в ширину с помощью теоремы Кёнига.
26.	Построить остов для К5, К3, 3 и в графе Петерсена. 
27.	Записать алгоритм построения остова графа с помощью поиска в ширину.
28.	Доказать, что для любого графа G верны неравенства (G)  (G)  (G).
29.	Доказать, что для любых натуральных чисел p, q, r, таких, что p  q  r, существует граф G, у которого (G)= p, (G)= q, (G)= r.
30.	С помощью алгоритма  укладки графа на плоскости, покажите, что граф К5 не планарный.
31.	С помощью алгоритма  постройте плоские укладки или установите непланарность графов, изображенных на рисунке.
32.	Являются ли плоскими графы, изображенные на рисунке.
33.	Покажите, что граф Петерсена негамильтонов.
34.	доказать теорему Эйлера. Связный граф является эйлеровым тогда и только, когда степени всех его вершин четны.
35.	Как найти хотя бы один эйлеров цикл в эйлеровом графе (алгоритм Флёри). Обосновать алгоритм Флёри.
36.	Какое максимальное число висячих вершин может иметь дерево 9-го порядка. Какое минимальное число висячих вершин оно может иметь. Нарисуйте эти деревья.
37.	Докажите, что лес, состоящий из k деревьев и содержащий в вершин, имеет b-k ребер.
38.	Построить плоский граф G с минимальным числом вершин, такой, что (G)=4.
39.	Являются ли плоскими графы, изображенные на рисунке 1?
40.	Доказать, что в графе Петерсена (рис. 1 в) нет гамильтонова цикла, но в графе, полученном из него удалением одной вершины, имеется гамильтонов цикл.
41.	доказать, что в каждом из графов Kn, Kn,n  имеется гамильтонов цикл.
Теория кодирования
1.	Построить оптимальный код Хаффмена для n = 7 (подробно провести «ручную» прокрутку алгоритма Хаффмена). Определить цену кодирования. Распределение вероятностей задано следующим массивом Р = {0.20, 0.20, 0.19, 0.15, 0.11, 0.09, 0.06}
2.	С помощью алгоритма Фано построить коды для заданного распределения вероятностей Р = {0.21, 0.20, 0.19, 0.15, 0.10, 0.09, 0.06}. Подробно провести «ручную» прокрутку этого алгоритма. Определить цену кодирования.
3.	Построить оптимальный код Хаффмена для n = 5 (подробно провести «ручную» прокрутку алгоритма Хаффмена). Определить цену кодирования. Распределение вероятностей задано следующим массивом Р = {0.30, 0.24, 0.20, 0.15, 0.11}
4.	С помощью алгоритма Фано построить коды для заданного распределения вероятностей Р = {0.30, 0.24, 0.20, 0.15, 0.11}. Подробно провести «ручную» прокрутку этого алгоритма. Определить цену кодирования.
5.	С помощью алгоритма Фано построить коды для заданного распределения вероятностей Р = {0.27, 0.24, 0.23, 0.14, 0.12}. Подробно провести «ручную» прокрутку этого алгоритма. Определить цену кодирования.
6.	Построить оптимальный код Хаффмена для n = 5 (подробно провести «ручную» прокрутку алгоритма Хаффмена). Определить цену кодирования. Распределение вероятностей задано следующим массивом Р = {0.27, 0.24, 0.23, 0.14, 0.12}
7.	Построить все самокорректирующиеся коды Хэмминга при m=4.
8.	Построить все самокорректирующиеся коды Хэмминга при m=5.
9.	Построить все самокорректирующиеся коды Хэмминга при m=6.
10.	Напишите программу шифрования текста с использованием следующего алгоритма: каждая буква в тексте заменяется на букву, расположенную на n позиций вправо от искомой в русском алфавите. Причем последним символом алфавита является пробел, а далее алфавит продолжается циклически. Напишите также программу расшифровки зашифрованного текста.
11.	С помощью алгоритма Лемпела-Зива сжать строку «aabaaccabc» (подробно расписать выполнение алгоритма). Оценить коэффициент сжатия, а затем приступить к распаковке (также подробно описав выполнение алгоритма).
12.	С помощью алгоритма Лемпела-Зива сжать строку «aaabbaabccabcа» (подробно расписать выполнение алгоритма). Оценить коэффициент сжатия, а затем приступить к распаковке (также подробно описав выполнение алгоритма).
13.	По заданному неразделимому коду (А)={aa,ab,cc,cca,bcca} и слову w в кодирующем алфавите В={a,b,c} выяснить, является ли слово w кодом некоторого сообщения. Если да, то выяснить, является ли слово w кодом ровно одного сообщения.
1)	w=ccabccabccabcc;
2)	w=bccaccabccabccacabcca;
3)	w=abbccaccabccaabab.
14.	Пусть числа 1,2,4,17,98 кодируются своими двоичными разложениями минимально возможной длины. Например, код единицы есть1, код двойки 10, код четверки есть 100. Является ли это кодирование разделимым?
15.	Для заданных распределений вероятностей появления букв построить оптимальные коды по методу Хаффмена.
1)	Р=(0,34;0,18;0,17;0,16;0,15);
2)	Р=(0,6;0,1;0,09;0,08;0,07;0,06);
3)	Р=(0,4;0,4;0,1;0,03;0,02;0,02);
4)	Р=(0,3;0,2;0,2;0,1;0,1;0,05;0,05).
16.	Для заданных распределений вероятностей появления букв построить коды по методу Фано.
1)	Р=(0,34;0,18;0,17;0,16;0,15);
2)	Р=(0,6;0,1;0,09;0,08;0,07;0,06);
3)	Р=(0,4;0,4;0,1;0,03;0,02;0,02);
4)	Р=(0,3;0,2;0,2;0,1;0,1;0,05;0,05).