Шпаргалка «Экзаменационная» по Дискретной математике (Зыков В. В.)

Кирилл Николоев пт, 15.04.2016 21:08

Оглавление 1. Граф. Ориентированный граф. Неориентированный граф. Смежность и инцидентность. Способы задания графа. Матрицы графа. 3 2. Степени вершины. Изолированные вершины. Подграф. Часть графа. Взвешенные графы. 3

3. Маршруты в ориентированных и неориентированных графах. Связность. Достижимость. 3 4. Представление графов с помощью динамических структур: списки смежности, ортогональные списки смежности, структуры Вирта. 3

5. Дерево. Основные свойства деревьев. Ориентированное дерево. Бинарные деревья. Остов. 3 6. Задача о построении кратчайшего остовного дерева. Алгоритм Прима. Проблема Штейнера. 3 7. Задача о построении дерева кратчайших расстояний. Алгоритм Дейкстры. 6

8. Задача о построении матрицы кратчайших расстояний. Алгоритм Флойда. 10 9. Сеть. Поток в сети. Задача о максимальном потоке в сети. Разрез. Теорема Форда – Фалкерсона. 17 10. Остаточная пропускная способность. Остаточная сеть. Алгоритм Форда – Фалкерсона нахождения максимального потока. 23

11. Геометрическая реализация графа. Теорема о реализации конечного графа в трёхмерном евклидовом пространстве. 29 12. Планарный граф. Грань графа. Доказать формулу Эйлера для планарных графов. 29 13. Доказать, что граф К5 не планарен. Доказать, что граф К33 не планарен. Теорема Понтрягина-Куратовского. 31

14. Независимое множество вершин графа. Вершинная раскраска. Правильная раскраска. Хроматическое число графа. Доказать теорему о 5 красках. 33 15. Эйлеров путь. Эйлеров граф. Алгоритм построения эйлерова пути в эйлеровом графе. Критерий эйлеровости графов. 33

16. Гамильтонов граф. Теорема Дирака. 35 17. Задача коммивояжёра. Метод ветвей и границ. 36 18. Обходы графов. 46 28. Теорема Холла. Трансверсали. Латинские треугольники и квадраты. 57 29. Конечные автоматы и регулярные выражения. Алфавит. Язык. 61

30. Недетерминированный конечный автомат. Функция переходов. Граф переходов. 63 31. Теорема о свойствах НКА. 69 32. Алгоритм моделирования НКА. 69 АЛГОРИТМ 1 (моделирование недетерминированного конечного автомата) 69

33. Детерминированный конечный автомат. Алгоритм моделирования ДКА. 72 34. Задача распознавания подцепочек. Машина идентификации цепочек. Функция отказов. Алгоритм вычисления функции отказов. 74 АЛГОРИТМ 2 Вычисление функции отказов 78

35. Двусторонний детерминированный магазинный автомат (2ДМА). Конфигурация автомата. Терминальная конфигурация. 79 36. Алгоритм моделирования 2ДМА. 90 АЛГОРИТМ 4 (моделирование 2ДМА): 90   1. Граф. Ориентированный граф. Неориентированный граф. Смежность и инцидентность. Способы задания графа. Матрицы графа.

2. Степени вершины. Изолированные вершины. Подграф. Часть графа. Взвешенные графы. 3. Маршруты в ориентированных и неориентированных графах. Связность. Достижимость. 4. Представление графов с помощью динамических структур: списки смежности, ортогональные списки смежности, структуры Вирта.

5. Дерево. Основные свойства деревьев. Ориентированное дерево. Бинарные деревья. Остов.   6. Задача о построении кратчайшего остовного дерева. Алгоритм Прима. Проблема Штейнера. Алгоритм Прима Определим расстояние между произвольной вершиной v взвешенного графа G=(V,E) и некоторым его подграфом G'G как минимальный вес ребра, одним из концов которого является v, а другой лежит в G':

d(v,G')=min(v,w)(G),wG'Weight(v,w). 1. SST '=; 2. если |E(SST ')|=n-1, то SST=SST '; КОНЕЦ; 3. среди множества I вершин графа G, не входящих в SST ', но инцидентных хотя бы одной вершине из SST' (I={u | uV(G), uSST', (u,v)E(G), vSST'}), найти вершину wI, расстояние которой до SST' минимально: d(w,SST')=minvId(v,SST');

4. добавить ребро (w,u), на котором достигается минимальное расстояние d(w,SST'), в SST '; 5. перейти на шаг 2. ПРИМЕР:С помощью алгоритма Прима построить минимальный покрывающий остов с корнем r.

Рис. П1. Начальная фаза. Минимальный покрывающий лес состоит из корня и пустого множества ребер. Рис. П2. Ребро с весом 6 является минимальным ребро, соединяющим корень с остальными вершинами. Добавляем его к минимальному остову.

Рис. П3. Следующее безопасное ребро с весом 11. Добавляем его. Рис. П4. Рис. П5. Рис. П6. Рис. П7. Рис. П8. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Скачать файлы

Похожие документы