Графы и их приложения — различия между версиями

Версия 14:03, 7 декабря 2021

Спецкурс для аспирантов.

Лектор - Селезнева Светлана Николаевна

Аннотация. В курсе рассматриваются основные структурные свойства графов и показывается их применение при решении подходящих задач. Разбираются простейшие свойства графов, связность и k-связность, деревья и остовные деревья, вершинные и реберные раскраски графов, наследственные свойства графов и экстремальные графы, числа Рамсея, статистические свойства графов и потоки в сетях. Кроме того, уделяется внимание алгоритмическим вопросам, связанным с графами, в частности, труднорешаемым графовым задачам. Приводятся как классические, так и достаточно новые результаты, относящиеся к свойствам графов.

Объявления

Экзамен состоится в субботу, 25 декабря, в 10 ч 30 мин (по московскому времени) удаленно.

Лекции

Лекция 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.