Избранные вопросы теории графов

Обязательный курс для студентов 418 группы

Лекции 3 ч в неделю, отчетность - экзамен.

Лекторы - Романов Дмитрий Сергеевич, Селезнева Светлана Николаевна.

Список вопросов по курсу "Избранные вопросы теории графов". ^{Список в формате .doc}

Часть 1

Алгебраические свойства графов

Лектор - Романов Дмитрий Сергеевич

Часть 2

Перечисления графов

Лектор - Романов Дмитрий Сергеевич

Часть 3

Структурные свойства графов

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

Лекция 1. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.

Лекция 2. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.

Лекция 3. Деревья. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.

Лекция 4. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом.

Лекция 5. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.

Лекция 6. Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.

Лекция 7. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.

Лекция 8. Сеть. Поток в сети. Теорема о величине максимального потока в сети. Построение максимального потока в сети.

Лекция 9. Труднорешаемые графовые задачи распознавания. NP-полнота задачи k-раскраски графов при каждом заданном числе k \ge 3.

Литература к части 3

Основная:

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

2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.

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

4. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.

Дополнительная:

6. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.

7. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМК МГУ имени М.В. Ломоносова, 2002.

8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

9. Оре О. Теория графов. М.: Наука, 1980.

10. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.

11. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.

12. Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического ф-та МГУ имени М.В. Ломоносова, 2007.

13. Diestel R. Graph Theory. Springer, 2010.