Графы и их приложения
Спецкурс для аспирантов.
Лектор - Селезнева Светлана Николаевна
Аннотация. В курсе рассматриваются основные структурные свойства графов и показывается их применение при решении подходящих задач. Разбираются простейшие свойства графов, связность и k-связность, деревья и остовные деревья, вершинные и реберные раскраски графов, наследственные свойства графов и экстремальные графы, числа Рамсея, статистические свойства графов и потоки в сетях. Кроме того, уделяется внимание алгоритмическим вопросам, связанным с графами, в частности, труднорешаемым графовым задачам. Приводятся как классические, так и достаточно новые результаты, относящиеся к свойствам графов.
Лекции
Лекция 1. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.
Лекция 2. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.
Лекция 3. Деревья. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.
Лекция 4. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом.
Лекция 5. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.
Лекция 6. Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.
Лекция 7. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.
Лекция 8. Сеть. Поток в сети. Теорема о величине максимального потока в сети. Нахождение максимального потока в сети.
Лекция 9. Труднорешаемые графовые задачи распознавания. NP-полнота задачи k-раскраски графов при каждом заданном числе k \ge 3.
Литература
Основная:
1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
Дополнительная:
3. Diestel R. Graph Theory. Springer, 2010.
4. Карпов Д.В. Теория графов
5. Харари Ф. Теория графов. М.: Мир, 1973.
6. Оре О. Теория графов. М.: Наука, 1980.
7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
8. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
9. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2014.
10. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
11. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
Экзамен
Экзамен письменный. Продолжительность экзамена – 1,5 астрономических часа (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно».
Вопросы для подготовки к экзамену
1. Точки сочленения и мосты в графе. Теорема о равносильных определениях точки сочленения. Связность, k-связность. Двусвязные графы. Теорема о равносильных определениях двусвязного графа.
2. Компоненты двусвязности (блоки) в графе. Критерий принадлежности двух вершин графа одной компоненте двусвязности. Свойства компонент двусвязности графа. Теорема о дереве блоков и точек сочленения графа.
3. Остовные деревья в графе. Теорема Кэли о числе остовных деревьев помеченного полного графа.
4. Остовные деревья в графе. Теорема о достижимости промежуточного числа висячих вершин в остовном дереве графа.
5. Остовные деревья в графе. Теорема об оценке числа висячих вершин в остовном дереве графа.
6. Хроматическое число графа. Критерий Кенига двуцветности графа. Верхние оценки хроматического числа графа.
7. Хроматическое число графа. Теорема Брукса о верхней оценке хроматического числа графа.
8. Хроматическое число графа. Теорема Зыкова о существовании графов без треугольников с произвольно большим хроматическим числом.
9. Хроматический индекс графа. Теорема о хроматическом индексе полного графа.
10. Хроматический индекс графа. Теорема Кенига о хроматическом индексе двудольного графа.
11. Хроматический индекс графа. Теорема Визинга о верхней оценке хроматического индекса графа.
12. Наследственные свойства графов. Теорема об оценке наибольшего числа ребер в графе с наследственным свойством.
13. Наследственные свойства графов. Планарные графы, теорема о наибольшем числе ребер в планарном графе.
14. Наследственные свойства графов. Теорема о наибольшем числе ребер в графе без треугольников.
15. Наследственные свойства графов. Теорема Турана о наибольшем числе ребер в графе без полного подграфа с n вершинами.
16. Числа Рамсея. Теорема о верхней оценке числа Рамсея.
17. Числа Рамсея. Теорема Эрдеша о нижней оценке числа Рамсея.
18. Обходы графов. Алгоритмы построения остовных деревьев на основе обходов графа.
19. Компоненты двусвязности графа. Алгоритм построения компонент двусвязности графа на основе обхода в глубину.
20. Потоки в сетях. Теорема Форда и Фалкерсона о величине максимального потока в сети.
21. Потоки в сетях. Алгоритм расстановки пометок для построения максимального потока в сети.
22. Паросочетания в графах. Алгоритм построения наибольшего паросочетания в двудольном графе на основе построения максимального потока в сети.
23. Труднорешаемые графовые задачи. NP-полнота задачи k-раскраски графа при каждом заданном числе k \ge 3.
