Вопросы

1. Основные определения. Основные понятия теории графов. Связь теории графов с предметной областью. . Способы задания графов. Матрицы смежности и инцидентности, их свойства.
2. Связность графов. Связность. Деревья. Свойства деревьев. Матричная теорема Кирхгофа о деревьях. Поиск минимального (максимального) остовного леса в графе.
3. Цикломатика графов. Эйлеровы графы. Критерий эйлеровости связного графа. Пространство четных подграфов и множество фундаментальных циклов. Цикломатическое число. Гамильтоновы графы. Признак гамильтоновости графа.
4. Потоки в сетях Бесконтурные графы, топологическая сортировка. Определение сети. Сетевые графики. Потоки в сетях, алгоритм построения потока. Теорема Форда–Фолкерсона и алгоритм построения максимального потока. Построение потока минимальной стоимости: алгоритм Форда-Фалкерсона, алгоритмы, основанные на выделении циклов отрицательного веса и на поиске минимального пути.
5. Метрические характеристики графов и экстремальные задачи. Расстояния в графе: вершина-вершина, вершина ребро, точка-вершина, точка-ребро. Центры и медианы графа, главные и абсолютные центры и медианы, методы их поиска. Обобщение задач размещения: задачи с усилениями, поиск кратных центров и медиан. Независимые и покрывающие множества. Теорема о числах независимости и покрытий. Максимальные независимые множества вершин, их поиск. Кратчайшее вершинное покрытие, алгоритмы его поиска. Доминирующие множества. Паросочетание. Поиск паросочетания максимальной мощности. Поиск паросочетания максимального веса. Определение двудольного графа. Совершенное паросочетание. Задача о свадьбах, теорема Холла. Задача о назначениях и алгоритм ее решения. Транспортная задача и алгоритм ее решения.
6. Задачи раскраски вершин и ребер графа Постановка задачи раскраски графа. Хроматическое число произвольных графов. Теорема Брукса. Хроматическое число планарных графов. Теоремы о шести и о пяти красках, гипотеза о четырех красках. Точный и приближенные алгоритмы раскрашивания графа.
7. Алгоритмы. Поиск в глубину и в ширину в графе. Топологическая сортировка вершин бесконтурного орграфа. Задача о кратчайшем пути. Алгоритмы Форда-Беллмана и Дейкстры. Задача о расстояниях между всеми парами вершин графа. Алгоритм Флойда. Транзитивное замыкание. Алгоритм Уоршалла. Алгоритм построения наибольшего паросочетания и наименьшего вершинного покрытия.
8. Применение графов для задач программирования. Описание графового представления моделей и решения задач с применением графов в среде объектно-ориентированного программирования.

Вопросы

1. Основные определения и обозначения, связанные с графами, орграфами и мультиграфами. Способы задания графов. Матрицы смежности и инцидентности, их свойства.
2. Двудольные графы. Критерий двудольности графа.
3. Леса и деревья. Эквивалентные определения дерева. Корневые и остовные деревья. Алгоритмы Примы и Краскала нахождения минимального остова.
4. Бинарные деревья. Хранение и поиск информации в бинарных деревьях. Добавление и удаление элементов. Деревья, сбалансированные по высоте (AVL-деревья) и по весу
5. Поиск по графу в ширину и глубину. Свойства дерева поиска. Связь поиска в ширину с кратчайшими цепями графа.
6. Точки сочленения, мосты и блоки графа. Вершинная и реберная k-связность. Характеризация двусвязных графов. Взаимное расположение двух блоков в графе. Дерево блоков и точек сочленения. Алгоритм поиска блоков.
7. Кратчайшие пути во взвешенных орграфах. Алгоритмы Дейкстры и Флойда-Уоршелла.
8. Сети и потоки в сетях. Задача о максимальном потоке. Остаточные сети, дополняющие пути и разрезы. Теорема и обобщенный алгоритм Форда-Фалкерсона. Анализ работы алгоритма в случае целых и рациональных пропускных способностей. Метод кратчайших путей.
9. Наборы непересекающихся цепей, соединяющих два подмножества вершин графа (орграфа). Вершинная и реберная теоремы Менгера. Критерии вершинной и реберной k-связности графов (теорема Уитни).
10. Обходы графов. Эйлеровы и гамильтоновы графы. Теорема Эйлера и алгоритм Флери. Достаточные условия гамильтоновости. Теоремы Дирака и Оре. Гамильтоновы циклы и задача коммивояжера.
11. Независимые множества вершин и ребер графа. Вершинные и реберные покрытия, факторы и паросочетания. Числовые параметры, связанные с независимостью и покрытиями, их свойства. Теорема Галлаи.
12. Наибольшие паросочетания и чередующиеся цепи. Характеризация наибольших паросочетаний в терминах чередующиеся цепей. Паросочетания, покрывающие долю двудольного графа. Связь с системами различных представителей и теоремой Холла.
13. Теоремы Кенига о числе реберной независимости двудольного графа и (0,1)-матрицах. Алгоритм нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольном графе. Задача о назначениях.
14. Плоские и планарные графы. Нормальные карты и эйлеровы многогранники. Формула Эйлера и ее следствия. Критерий планарности Понтрягина-Куратовского. Алгоритм укладки графа на плоскости. Понятие геометрически двойственного графа.
15. Раскраски вершин графов. Простейшие оценки хроматического числа. Теорема Брукса.
16. Раскраски планарных графов и карт. Теорема о четырех красках. Доказательство теоремы о пяти красках. Достаточные условия Грецша и Грюнбаума 3-раскрашиваемости плоских графов.
17. Хроматические полиномы, их свойства. Нерешенные задачи, связанные с хроматическими полиномами.
18. Раскраски ребер графов и мультиграфов. Теоремы Визинга и Шэннона. Хроматический индекс двудольного графа. Интервальные раскраски. Связь с задачами теории расписаний.
19. Предписанные раскраски вершин и ребер графов. Теорема Томассена о предписанной 5-раскрашиваемости плоских графов.
20. Перечисление и кодирование графов Проблема изоморфизма. Кодирование деревьев. Код Прюфера. Теорема Кэли о числе помеченных деревьев.
21. Труднорешаемые задачи на графах. Классы P, NP, NPC. Связь между задачами “Клика” и “Выполнимость”. Некоторые NP-полные задачи на графах (“Изоморфный подграф”, “Независимость’’, “Вершинное покрытие’’, “Гамильтонов цикл”, “3-раскрашиваемость” и другие).
22. 1. Оценки числа ребер в обыкновенных графах.
    2. Матрица Кирхгофа и ее свойства.
    3. Число остовов в обыкновенном связном графе.
    4. Эйлеровы графы.
    5. Произвольно вычерчиваемые графы.
    6. Конечномерные геометрические решетки и матроиды.
    7. Теорема Биркгофа-Уитни.
    8. Аксиомы независимости.
    9. Аксиомы баз.
    10. Ранговые аксиомы.
    11. Аксиомы циклов.
    12. Жадный алгоритм.
    13. Пространство циклов бинарного матроида.
    14. Пространство разрезов графа.
    15. Монотонные полумодулярные функции.
    16. Теорема Эдмондса.
    17. Теорема Нэш-Вильямса о числе древовидности.
    18. Формула Эйлера для плоских графов
    19. Формула Эйлера для многогранников.
    20. Следствия формулы Эйлера.
    21. Критерий планарности Понтрягина-Куратовского.
    22. Критерий планарности Вагнера-Харари-Татта.
    23. Теорема Брукса.
    24. Лемма о перекрашивании двуцветных компонент. 
    25. Теорема Хивуда о пяти красках.
    26. Теорема о хроматической редукции.
    27. Теорема Зыкова о коэффициентах хроматического многочлена.
    28. Теорема Уитни о коэффициентах хроматического многочлена. 

Основная литература:

1. Э. Майника. Оптимизационные задачи на сетях и графах.
2. А.А.Новиков. Дискретная математика для программистов. – Питер, 2001.
3. Р. Уилсон. Введение в теорию графов. – М.: Мир, 1977.
4. Н.Кристофидес. Теория графов. Алгоритмический подход. – М.: Мир, 1977.
5. Миронов В., Башмаков И. А. Прикладные задачи теории графов. – М: Наука, 1981.
6. Ф. Харари. Теория графов. – М.:Мир, 1973.
7. К. Берж. Теория графов.
8. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
9. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.Н. Лекции по теории графов. - М.: Наука, 1990.  

Дополнительная литература:

1. В.Н. Нефедов, В.А. Осипова. Курс дискретной математики. – М.: МАИ, 1992.
2. С.М. Окулов. Программирование в алгоритмах. – М.: БИНОМ, Лаборатория знаний, 2002.
3. А.И.Белоусов, С.В.Ткачев. Дискретная математика. – М., изд-во МГТУ им. Баумана, 2002.
4. Б.Н. Иванов. Дискретная математика: алгоритмы и программы. – М.: Лаборатория базовых знаний, 2002.