Вопросы к экзамену по курсу "Алгоритмы на графах". 2004 г.
Бесконтурные ориентированные графы
Существование источника в бесконтурном ориентированном графе. Сложность алгоритмов поиска источников и стоков графа в зависимости от способа задания графа. Правильная нумерация вершин бесконтурного графа. Ярусная форма бесконтурного графа. Теорема о минимальном количестве ярусов в бесконтурном графе.
Алгоритм поиска в бесконтурном графе самого короткого пути. Алгоритм поиска в бесконтурном графе самого длинного пути. Алгоритм поиска в бесконтурном графе самого надежного пути. Алгоритм поиска в бесконтурном графе пути наибольшей пропускной способности.
Поиск в глубину в ориентированном графе [СДА]. Алгоритм построения правильной нумерации, основанный на поиске в глубину. Компоненты связности и сильной связности. Теорема о бесконтурности фактор-графа по компонентам сильной связности. Алгоритм нахождения компонент сильной связности, основанный на методе поиска в глубину.
Двусвязные компоненты. Теорема о двусвязных компонентах графа. [ПАВА, 5.3]
Поиск в глубину в неориентированном графе. Алгоритм нахождения двусвязных компонент и точек сочленения [СДА, ПАВА].
Расстояния на графах
Алгоритм Дейкстры. Алгоритм Флойда. Построение транзитивного замыкания. [СДА]
Алгоритм нахождения вершинного/абсолютного центра на графе. Задача нахождения медианы и k-медианы на графе. Теорема Хакими. Приближенный алгоритм нахождения k-медианы. [ln-master]
Остовные деревья. Алгоритмы Краскала и Прима [СДА]. Построение (a,b)-минимального дерева кратчайших путей, оценка качества решения (теорема). [ln-master]. Деревья Штейнера [ln-master].
Циклы
Эйлеровы циклы и цепи. Критерии существования и алгоритм поиска эйлерова цикла. Критерий полуэйлеровости. Гамильтоновы циклы. Теорема Дирака. NP-полнота задачи о гамильтоновом контуре/цикле. Задача коммивояжера. Метрическая задача коммивояжера, ее NP-полнота, эвристический алгоритм. [Носов]
Потоки и разрезы
Потоки в сетях. Связь потоков с разрезами, теорема Менгера. [ДМП]
Алгоритм Форда-Фалкерсона. [ДМП] Обоснование. Обобщение на случай нескольких источников и стоков, ограничений на пропускную способность вершин. Нахождение путей, реализующих поток. Потоки с ограничениями снизу и сверху. Теорема о существовании, алгоритм нахождения максимального потока.
Паросочетания
Двудольные графы. Теор. Кёнига о двудольных графах. [Носов]
Теорема Холла о совершенных паросочетаниях в двудольных графах (прямое доказательство для задачи о трансверсалях и док-во через теорему Менгера). Следствие для однородных графов. [Оре] Алгоритм нахождения максимального паросочетания на двудольном графе.
Алгоритм нахождения максимального паросочетания в произвольном неориентированном графе. [algnotes, с.123-128]
Планарные графы
Планарные графы. Сферическая проекция. Теорема Эйлера о плоских графах. [Оре]
Перечисление правильных многогранников. Перечисление мозаик. [Оре]
Непланарность графов K(3,3) и K(5). Критерий Понтрягина-Куратовского. Алгоритм плоской укладки графа. [algnotes, с.141-147]
Триангуляция выпуклых многоугольников. [СДА]
Раскраска плоских графов и карт. Теорема о сводимости задачи раскраски произвольных плоских карт к картам однородных графов степени 3. Теорема о существовании грани с 3,4 или 5 вершинами в плоском однородном степени 3 графе. Теорема о 5-ти красках. [Оре]
Алгоритмы решения трудных задач
Метод полного перебора. Алгоритм определения изоморфности графов.
Метод ветвей и границ. Точный и эвристический алгоритм построения минимальной раскраски.
Задача о наименьшем покрытии. Эвристический (жадный) и точный (древовидный перебор) алгоритм.
Алгоритм нахождения всех максимальных независимых множеств. Алгоритм поиска всех клик. Алгоритм минимальной раскраски вершин графа (на основе алгоритмов нахождения всех максимальных независимых множеств и наименьшего покрытия).
Алгоритмы поиска/проверки локального оптимума. Задачи о размыкании контуров, об оптимальной нумерации, об экспертных оценках: их эквивалентность, локально-оптимальная нумерация относительно транспозиций и сдвигов. Метод ветвей и границ для задачи об оптимальной нумерации.
Эвристические итерационные алгоритмы для задачи о размещении графа на прямой, задачи о разрезании графа, задачи коммивояжера.
Литература
| ДМП | Новиков Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2000. |
| СДА | Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. - М.: Вильямс, 2000. |
| ПАВА | Ахо А., Хопкрофт Д., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1978. |
| Оре | Оре О. Графы и их применения. — М.: Мир, 1969. |
| Носов | Носов В.А. "Комбинаторика и теория графов" http://intsys.msu.ru/staff/vnosov/combgraph.htm |
| ln-master | "Lecture Notes on Approximation Algorithms for Network Problems" (англ.) http://www.math.uwaterloo.ca/~jcheriya/lecnotes.html |
| algnotes | Johan Hastad "Notes for the course of advanced algorithms". (англ.) www.nada.kth.se/~johanh/algnotes.pdf |
Дополнительная литература