Реферат: Знать содержание программы курса; иметь навыки структурного моделирования типовых объектов; иметь навыки проведения структурного анализа типовых графов. Формы контроля

Аннотация курса “Графы и алгоритмы”

лектор к.ф.-м.н. А. Н. Глебов

Название курса.
Теория графов (Графы и алгоритмы)

Направление - математика

Раздел - общие математические и естественно-научные дисциплины

Семестр(ы) — 7
Цели и задачи курса.
Дисциплина "Теория графов" предназначена для студентов механико-математиче­ских факультетов университетов.

Основной целью освоения студентами данной дисциплины является изучение методов математического описания структуры разнообразных объектов, ознакомление с результатами анализа структурных свойств этих объектов, а также с алгоритмическими построениями, достигнутыми в этой области к настоящему времени.

Для достижения поставленной цели выделяются задачи курса:

1) изучение теоретической части курса в соответствии с программой

2) сдача экзамена в соответствии с учебным планом.
^ Требования к уровню освоения содержания курса.
По окончании изучения указанной дисциплины студент должен

иметь представление о месте и роли изучаемой дисциплины среди других наук;

знать содержание программы курса;

иметь навыки структурного моделирования типовых объектов;

иметь навыки проведения структурного анализа типовых графов.
^ Формы контроля
Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрен экзамен.

Текущий контроль. Фиксация посещаемости, проверка выполнения самостоятельных заданий.


Содержание дисциплины.
Новизна.
Курс "Теория графов" активно изучается в западных университетах (в рамках курсов по дискретной оптимизации либо в виде самостоятельной дисциплины), что обусловлено его значительной прикладной значимостью. В то же время исследования по теории графов в России в значительной степени были развиты в Институте математики Сибирского отделения, благодаря таким корифеям в этой области как Зыков А.А., Визинг В.Г., Косточка А.В., чьи работы получили мировое признание, а сейчас эти исследования успешно продолжаются в лаборатории теории графов ИМ им. С.Л. Соболева СО РАН. Предлагаемый курс построен с учетом как традиционных знаний , так и современных достижений в области теории графов.
^ Тематический план курса.

Наименование разделов и тем

К о л и ч е с т в о ч а с о в


Лекции


Семинары

Лаборатор-

ные работы

Самостоятель-ная работа

Всего

часов

Определения и способы задания графов

4

2




2

8

Основные алгоритмы на графах

14

6




8

28

Связность, независимость, покрытия и обходы графов

8

4




4

16

Раскраски вершин и ребер

4

2




2

8

Планарность

4

2




2

8

Итого по курсу:

34

16




18

68
^ Содержание отдельных разделов и тем.



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

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

Леса и деревья. Эквивалентные определения дерева. Корневые и остовные деревья. Алгоритмы Примы и Краскала нахождения минимального остова.

Бинарные деревья. Хранение и поиск информации в бинарных деревьях. Добавление и удаление элементов. Деревья, сбалансированные по высоте (AVL-деревья) и по весу

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

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

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

Сети и потоки в сетях. Задача о максимальном потоке. Остаточные сети, дополняющие пути и разрезы. Теорема и обобщенный алгоритм Форда-Фалкерсона. Анализ работы алгоритма в случае целых и рациональных пропускных способностей. Метод кратчайших путей.

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

Обходы графов. Эйлеровы и гамильтоновы графы. Теорема Эйлера и алгоритм Флери. Достаточные условия гамильтоновости. Теоремы Дирака и Оре. Гамильтоновы циклы и задача коммивояжера.

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

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

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

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

Плоские и планарные графы. Нормальные карты и эйлеровы многогранники. Формула Эйлера и ее следствия. Критерий планарности Понтрягина-Куратовского. Алгоритм укладки графа на плоскости. Понятие геометрически двойственного графа.

Раскраски вершин графов. Простейшие оценки хроматического числа. Теорема Брукса.

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

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

Раскраски ребер графов и мультиграфов. Теоремы Визинга и Шэннона. Хроматический индекс двудольного графа. Интервальные раскраски. Связь с задачами теории расписаний.

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

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

Труднорешаемые задачи на графах. Классы P, NP, NPC. Связь между задачами “Клика” и “Выполнимость”. Некоторые NP-полные задачи на графах (“Изоморфный подграф”, “Независимость’’, “Вершинное покрытие’’, “Гамильтонов цикл”, “3-раскрашиваемость” и другие).



Литература



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




Харари Ф. Теория графов // М.: Мир, 1973.




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




Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ //

М.: МЦНМО, 2001.