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



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

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

2013-14 уч. год, лектор: А.Н. Глебов


  1. Основные определения и обозначения, связанные с графами (понятия графа, мультиграфа, псевдографа, орграфа, смежность и инцидентность вершин и ребер, степени вершин, порожденные и остовные подграфы, дополнение графа, полные и пустые графы, двудольные и k-дольные графы, r-регулярные графы, r-факторы, изоморфизм и автоморфизм графов, маршруты, цепи, пути и циклы, связность, компоненты связности, расстояние между вершинами, диаметр графа и т.д.). Лемма о рукопожатиях.

  2. Способы задания графов и орграфов. Теорема о числе маршрутов, соединяющих две вершины графа (орграфа).

  3. Двудольные графы. Критерий двудольности графа.

  4. Леса и деревья. Теорема об эквивалентных определениях дерева. Корневые деревья и связанные с ними понятия.

  5. Вершинно и реберно k-связные графы. Числа вершинной и реберной связности, неравенство между ними. Простейшие операции, сохраняющие k-связность графов.

  6. Вершинно и реберно-двусвязные графы Точки сочленения и мосты в графе. Теорема об эквивалентных определениях вершинно-двусвязного графа.

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

  8. Поиск по графу в глубину и в ширину. Дерево поиска. Связь поиска в ширину с кратчайшими цепями в графе.

  9. Основное свойство обратных ребер при поиске в глубину, ранговая функция вершин, ее свойства.

  10. Алгоритм нахождения блоков в связном графе.

  11. Остовные деревья (остовы) в графах. Характеризация связных графов в терминах остовных деревьев.

  12. Поиск минимального остова во взвешенном графе. Алгоритм Краскала.

  13. Поиск минимального остова во взвешенном графе. Алгоритм Примы.

  14. Кратчайшие пути во взвешенных орграфах. Алгоритм Дейкстры.

  15. Кратчайшие пути во взвешенных орграфах. Алгоритм Флойда-Уоршелла.

  16. Гамильтоновы циклы и цепи, необходимые условия их существования. Достаточные условия гамильтоновости графа (теоремы Дирака и Оре).

  17. Понятия эйлерова цикла и цепи. Эйлеровы графы. Критерий эйлеровости графа и алгоритм Флери.

  18. Определения сети и потока. Задача о максимальном потоке. Понятие разреза в сети, пропускная способность разреза, минимальный разрез. Лемма о величине потока через разрез.

  19. Остаточные сети и дополняющие пути для потоков в сетях.

  20. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе.

  21. Метод Форда-Фалкерсона посторения максимального потока и минимального разреза. Анализ работы метода в случае целых и рациональных пропускных способностей дуг.

  22. Анализ работы метода Форда-Фалкерсона в случае иррациональных пропускных способностей дуг. Пример Форда-Фалкерсона.

  23. Метод кратчайших путей для нахождения максимального потока в сети.

  24. Реберная теорема Менгера для орграфов (о наименьшем числе дуг, разделяющих два подмножества вершин орграфа).

  25. Вершинная теорема Менгера для орграфов (о наименьшем числе вершин, разделяющих два подмножества вершин орграфа).

  26. Теоремы Менгера для неориентированных графов (вершинный и реберный варианты).

  27. Критерии вершинной и реберной k-связности графа (теоремы Уитни).

  28. Независимые множества вершин и ребер (мульти)графа, паросочетания, совершенные паросочетания, r-факторы и r-факторизации.

  29. Вершинные и реберные покрытия (мульти)графа, доминирующие множества. Числовые характеристики независимости и покрытия, их простейшие свойства, связь с плотностью(кликовым числом) графа.

  30. Лемма о строении минимального реберного покрытия (мульти)графа. Теорема Галлаи.

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

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

  33. Теоремы Кенига о числе реберной независимости двудольного графа и о (0,1)-матрицах.

  34. Алгоритм поиска наибольшего паросочетания и наименьшего вершинного покрытия двудольного графа. Задача о назначениях.

  35. Критерий Татта существования 1-фактора в произвольном графе.

  36. Теоремы Петерсена о 2-факторах в кубических графах и о 2-факторизуемости регулярных графов четной степени.

  37. Раскраски вершин графов, k-раскрашиваемые, k-хроматические и критические графы. Понятие хроматического числа графа, его простейшие нижние оценки.

  38. Верхняя оценка хроматического числа k-вырожденного графа. Теорема Брукса.

  39. Раскраски ребер графов и мультиграфов. Хроматический класс мультиграфа. Нижние оценки хроматического класса. Верхние оценки Визинга и Шэннона для графов и мультиграфов. Неулучшаемость оценок. Хроматический класс двудольного (мульти)графа.

  40. Плоские и планарные графы. Грани плоского графа, понятие ранга грани в связном плоском графе. Характеризация графов выпуклых многогранников.

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

  42. Подразбиения и гомеоморфизм графов. Непланарность графов K5 и K3,3 и их подразбиений. Критерий планарности Понтрягина-Куратовского.

  43. Раскраски планарных графов и карт. Теорема о четырех красках, ее эквивалентные формы. Достаточные условия Грецша и Грюнбаума 3-раскрашиваемости планарных графов.


Литература





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

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

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

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


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


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

    Басты бет