Программа курса “Графы и алгоритмы”



жүктеу 37.97 Kb.
Дата07.02.2019
өлшемі37.97 Kb.
түріПрограмма спецкурса

Программа спецкурса “Теория графов”

лектор А. Н. Глебов


  1. Основные определения и обозначения, связанные с графами, орграфами и мультиграфами.

  2. Способы задания графов. Матрицы смежности и инцидентности, их свойства. Связь между матрицей смежности и числом маршрутов заданной длины.

  3. Графы пересечений множеств. Представление произвольного графа в виде графа пересечений.

  4. Степенные последовательности графов, мультиграфов и псевдографов, их характеризация.

  5. Двудольные графы. Критерий двудольности графа. Однозначность разбиения связного графа на доли.

  6. Экстремальные по числу ребер графы. Экстремальные графы без треугольников. Теорема Турана и граф Турана.

  7. Леса и деревья. Теорема о характеризации деревьев. Корневые и остовные деревья.

  8. Вершинная и реберная древесность графов. Теорема Нэш-Уильямса о реберной древесности. Понятие линейной древесности.

  9. Перечисление и кодирование деревьев. Код Прюффера. Теорема Кэли о числе помеченных деревьев.

  10. Проблема изоморфизма графов. Гипотеза Улама. Полные системы инвариантов для деревьев.

  11. Вершинная и реберная k-связность графов, числа вершинной и реберной связности, их свойства.

  12. Точки сочленения, мосты и блоки графа. Теорема о характеризации вершинно двусвязных графов. Взаимное расположение двух блоков в графе. Дерево блоков и точек сочленения.

  13. Сети и потоки в сетях. Задача о максимальном потоке. Остаточные сети, дополняющие пути и разрезы. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе.

  14. Наборы непересекающихся цепей, соединяющих два подмножества вершин графа (орграфа). Вершинная и реберная теоремы Менгера. Критерии вершинной и реберной k-связности графа (теоремы Уитни).

  15. Обходы графов. Гамильтоновы циклы и цепи. Простейшие необходимые условия гамильтоновости графа. Достаточные условия: теоремы Оре и Дирака. Задача коммивояжера.

  16. Эйлеровы циклы и цепи. Критерий эйлеровости графа. Алгоритм Флери.

  17. Независимые множества вершин и ребер графа. Вершинные и реберные покрытия, факторы и паросочетания. Числовые параметры, связанные с независимостью и покрытиями, их свойства. Теорема Галлаи.

  18. Наибольшие паросочетания и чередующиеся цепи. Характеризация наибольших паросочетаний в терминах чередующиеся цепей.

  19. Паросочетания, покрывающие долю двудольного графа. Связь с системами различных представителей. Теоремы Холла, Кенига-Холла и Кенига-Оре.

  20. Теоремы Кенига о числе реберной независимости двудольного графа и (0,1)-матрицах. Связь между задачами о наибольшем паросочетании, о наименьшем вершинном покрытии и о максимальном потоке. Задача о назначениях.

  21. Критерий Татта существования 1-фактора в произвольном графе. Теоремы Петерсена о 2-факторах. Теоремы об 1-факторизуемости и 2-факторизуемости полных графов.

  22. Плоские и планарные графы. Грани плоского графа. Нормальные карты и эйлеровы многогранники.

  23. Формула Эйлера и ее следствия. Оценки для числа ребер планарных графов. Максимальные планарные графы, плоские триангуляции и четыреангуляции.

  24. Понятие k-вырожденного графа. Оценки для числа вырожденности планарных графов.

  25. Критерий планарности Понтрягина-Куратовского.

  26. Геометрическая двойственность плоских графов. Двойственность платоновых многогранников.

  27. Укладки графов на двумерных поверхностях. Эйлерова характеристика поверхности. Род, крупность, толщина и число скрещиваний графа.

  28. Раскраски вершин графов, k-раскрашиваемые, k-хроматические и критические графы. Хроматическое числа графа, его простейшие оценки. Раскраска k-вырожденных графов. Теорема Брукса.

  29. Вершинные раскраски графов без треугольников. Графы Мцельского. Хроматическое число графа с большим обхватом.

  30. Совершенные графы. Теорема о дополнении совершенного графа (малая гипотеза Бержа). Теорема о характеризации совершенных графов (большая гипотеза Бержа). Хордальные графы, их характеризация и совершенство.

  31. Хроматические полиномы, их свойства. Нерешенные задачи, связанные с хроматическими полиномами.

  32. Раскраски планарных графов и карт. Теорема о четырех красках, ее эквивалентные формулировки: теорема Тейта и гипотеза Хадвигера.

  33. Доказательство теоремы о пяти красках. Достаточные условия Грецша и Грюнбаума 3-раскрашиваемости плоских графов.

  34. Раскраски графов, уложенных на двумерных поверхностях. Хроматическое число поверхности. Теорема Хивуда о раскраске карт.

  35. Раскраски ребер графов и мультиграфов. Понятие хроматического индекса. Теоремы Визинга и Шэннона, неулучшаемость их оценок. Хроматический индекс двудольного графа.

  36. Предписанные раскраски вершин и ребер графов. Связь между обычными и предписанными раскрасками. Оценка предписанного хроматического числа через число вырожденности графа.

  37. Предписанное хроматическое число полного двудольного графа. Критерий предписанной 2-раскрашиваемости.

  38. Теорема Томассена о предписанной 5-раскрашиваемости плоских графов.

  39. Предписанный хроматический индекс двудольного графа. Гипотеза о предписанном хроматическом индексе.

  40. Теорема Рамсея для множеств и графов. Оценки для чисел Рамсея. Обобщения чисел Рамсея.

  41. Вероятностные методы в теории графов. Моделирование случайных графов. Некоторые свойства "почти всех” графов.



Литература





  1. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов // М.: Наука, 1990.

  2. Харари Ф. Теория графов // М.: УРСС, 2003.

  3. Дистель Р. Теория графов // Новосибирск: Изд-во ИМ СО РАН, 2002.

  4. Косточка А. В. Дискретная математика. Часть 2 // Новосибирск: НГУ, 2001.


Достарыңызбен бөлісу:


©kzref.org 2017
әкімшілігінің қараңыз

    Басты бет