Программа дисциплины Алгоритмы на графах
 Скачать 128.01 Kb.
|
|
Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «Новосибирский государственный университет» (НГУ) Факультет информационных технологий Кафедра Систем информатики ПРОГРАММА ДИСЦИПЛИНЫ « Алгоритмы на графах » ЦИКЛ*_____________СПЕЦИАЛЬНЫЕ ДИСЦИПЛИНЫ________________ СПЕЦИАЛЬНОСТЬ 230105.65 «ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ» Автор: к.ф.-м.н. Глебов Алексей Николаевич Новосибирск 2009 * Наименование цикла дисциплин в соответствии с ГОС ВПО Программа дисциплины «Алгоритмы на графах» составлена в соответствии с требованиями к обязательному минимуму содержания и уровню подготовки дипломированного специалиста по циклу «специальных дисциплин» Федеральных государственных образовательных стандартов высшего профессионального образования по специальности 230105.65 «Программное обеспечение вычислительной техники и автоматизированных систем». 1. Цели и задачи дисциплины (курса) Дисциплина (курс) «Алгоритмы на графах» имеет своей целью: изучение методов математического описания разнообразных объектов, связанных с графами, ознакомление с результатами анализа структурных свойств этих объектов, а также с алгоритмическими построениями, достигнутыми в этой области к настоящему времени. Для достижения поставленной цели выделяются задачи курса: 1) изучение теоретической части курса в соответствии с программой; 2) выполнение семестровых практических заданий; 2) сдача дифференцированного зачета и экзамена в соответствии с учебным планом. 2. Требования к уровню освоения содержания дисциплины В результате освоения дисциплины студент должен: Иметь представление о месте и роли изучаемой дисциплины среди других наук; Знать содержание программы курса; Уметь применять типовые алгоритмы на графах; Иметь навыки проведения структурного анализа графов. 3. Объем дисциплины и виды учебной работы Вид учебной работы Всего часов Семестры 1 2 Общая трудоемкость дисциплины 124 62 62 Аудиторные занятия, в том числе: Лекции 36 18 18 Семинары Лабораторные работы Самостоятельная работа, в том числе: 88 44 44 Курсовой проект Реферат Расчетные работы Другие виды самостоятельной работы задание задание Вид промежуточного контроля дифзачет экзамен Общая трудоемкость дисциплины составляет ________________ зачетных единиц (если применяется на факультете/кафедре). 4. Содержание дисциплины 4.1. Новизна курса. Курс "Алгоритмы на графах" активно изучается в российских и западных университетах (в рамках курсов по дискретной оптимизации либо в виде самостоятельной дисциплины), что обусловлено их значительной прикладной значимостью. Исследования по теории графов в России в значительной степени были развиты в Институте математики Сибирского отделения, благодаря таким корифеям в этой области как Зыков А.А., Визинг В.Г., Косточка А.В., Бородин О.В., чьи работы получили мировое признание, а сейчас эти исследования успешно продолжаются в лаборатории теории графов ИМ СО РАН им. С.Л. Соболева. Предлагаемый курс построен с учетом как традиционных знаний , так и современных достижений в области теории графов. 4.2. Тематический план курса (распределение часов по видам учебной работы). № п/п Наименование тем и разделов ВСЕГО (часов) Аудиторные занятия (часов), в том числе Самостоятел ьная работа (часов) Лекции Семинары Лаб. работы Введение в предмет 2 2 Основные алгоритмы на графах 66 18 48 Структурные свойства и раскраски графов 56 16 40 ИТОГО: 124 36 88 4.3. Содержание разделов и тем курса. Введение в предмет 1. Предмет теории графов. Исторический очерк развития теории графов. Алгоритмы на графах. 2. Основные определения и обозначения, связанные с графами, орграфами и мультиграфами. Способы задания графов. Матрицы смежности и инцидентности, их свойства. Основные алгоритмы на графах 1. Леса и деревья. Эквивалентные определения дерева. Корневые и остовные деревья. Алгоритмы Примы и Краскала нахождения минимального остова. 2. Поиск по графу в ширину и глубину. Свойства дерева поиска. Связь поиска в ширину с кратчайшими цепями графа. 3. Точки сочленения, мосты и блоки графа. Вершинная и реберная k-связность. Характеризация двусвязных графов. Взаимное расположение двух блоков в графе. Дерево блоков и точек сочленения. Алгоритм поиска блоков. 4. Кратчайшие пути во взвешенных орграфах. Алгоритмы Дейкстры и Флойда- Уоршелла. 5. Сети и потоки в сетях. Задача о максимальном потоке. Остаточные сети, дополняющие пути и разрезы. Теорема и обобщенный алгоритм Форда-Фалкерсона. Анализ работы алгоритма в случае целых и рациональных пропускных способностей. Метод кратчайших путей. 6. Обходы графов. Эйлеровы и гамильтоновы графы. Теорема Эйлера и алгоритм Флери. Достаточные условия гамильтоновости. Теоремы Дирака и Оре. Гамильтоновы циклы и задача коммивояжера. 7. Теоремы Кенига о числе реберной независимости двудольного графа и (0,1)-матрицах. Алгоритм нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольном графе. Задача о назначениях. Структурные свойства и раскраски графов 1. Двудольные графы. Критерий двудольности графа. 2. Наборы непересекающихся цепей, соединяющих два подмножества вершин графа (орграфа). Вершинная и реберная теоремы Менгера. Критерии вершинной и реберной k-связности графов (теорема Уитни). 10 Независимые множества вершин и ребер графа. Вершинные и реберные покрытия, факторы и паросочетания. Числовые параметры, связанные с независимостью и покрытиями, их свойства. Теорема Галлаи. 11 Наибольшие паросочетания и чередующиеся цепи. Характеризация наибольших паросочетаний в терминах чередующиеся цепей. Паросочетания, покрывающие долю двудольного графа. Связь с системами различных представителей и теоремой Холла. 12 Критерий Татта существования 1-фактора в произвольном графе. Теоремы Петерсена о 2-факторах. 13 Плоские и планарные графы. Нормальные карты и эйлеровы многогранники. Формула Эйлера и ее следствия. Критерий планарности Понтрягина-Куратовского. Понятие геометрически двойственного графа. 14 Раскраски вершин графов. Простейшие оценки хроматического числа. Теорема Брукса. 15 Раскраски планарных графов и карт. Теорема о четырех красках. Доказательство теоремы о пяти красках. Достаточные условия Грецша и Грюнбаума 3- раскрашиваемости плоских графов. 16 Раскраски ребер графов и мультиграфов. Теоремы Визинга и Шэннона. Хроматический индекс двудольного графа. Интервальные раскраски. Связь с задачами теории расписаний. 4.4. Перечень примерных контрольных вопросов и заданий для самостоятельной работы. 1. Построить (нарисовать) все неизоморфные между собой а) графы порядка 4; б) деревья порядка 6; в) ориентированные графы порядка 3 без параллельных дуг. 2. Существует ли граф порядка 15, имеющий одну вершину степени 1, две вершины степени 2, три вершины степени 3, четыре вершины степени 4 и пять вершин степени 5? 3. Доказать, что в любом графе найдутся две вершины одинаковой степени. Для каждого натурального N > 1 привести пример связного графа порядка N, степени вершин которого принимают N – 1 различных значений. 4. Граф называется самодополнительным, если он изоморфен своему дополнению. Доказать, что порядок любого самодополнительного графа сравним с 0 или 1 по модулю 4. Найти все самодополнительные графы с 4 и 5 вершинами. 5. Найти число всех простых цепей в дереве порядка N. 6. Применить алгоритмы (с начальной вершиной a): а) поиска в ширину; б) поиска в глубину; в) Примы; г) Краскала к взвешенному графу с множеством вершин V = {a,b,c,d,e,f,g,h} и множеством ребер E={ab(4),bc(1),cd(3),de(6),ef(2),fg(6),gh(1),ha(7),ad(2),be(5),cf(3),dg(4),eh(1),fa(3),gb(7), hc(8)} (в скобках указаны веса ребер). 7. Найти числа вершинной и реберной связности полного графа K n , полного двудольного графа K m,n , цепи P n , цикла C n 8. Построить граф c числом вершинной связности 2, числом реберной связности 3 и минимальной степенью 4. 9. Построить все вершинно 4-связные графы с не более чем 12 ребрами. 10. Доказать, что в любом графе порядка N с числом вершинной связности 1 минимальная степень и число реберной связности не превосходят (N – 1)/2. 11. Применить алгоритм поиска блоков c начальной вершиной b и построить граф блоков и точек сочленения для графа с множеством вершин V={a,b,c,d,e,f,g,h,i,j,k,l,m,n} и множеством ребер E={ab,bc,cd,de,ea,bd,ce,af,fg,fh,hi,hj,ij,dk,kl,lm,mn,nk}. 4.5. Примерная тематика рефератов, курсовых работ. 1. Бинарные деревья. Хранение и поиск информации в бинарных деревьях. Добавление и удаление элементов. Деревья, сбалансированные по высоте (AVL- деревья) и по весу. 2. Критерий Татта существования совершенного паросочетания. Алгоритм поиска наибольшего паросочетания в произвольном графе. 3. Жадные алгоритмы на графах. Условия оптимальности жадных алгоритмов. 4. Методы распознавания планарности графов: критерий Понтрягина-Куратовского, алгоритм Татта укладки графа на плоскости и др. Аналоги критерия Понтрягина- Куратовского для внешнепланарных графов а также для графов, вложимых в различные поверхности. 5. Вложимость графов в двумерные поверхности. Понятие рода графа. Теорема Хивуда о раскраске карт. Результаты Рингеля и Янгса. 6. Экстремальные графы. Теорема Турана, ее разновидности и аналоги (теоремы Эрдеша и др.). 7. Реберные графы и их свойства. Критерий реберности графа. 8. Ориентированные графы и турниры. 9. Обычные и предписанные раскраски вершин и ребер в графах и мультиграфах. 10. Совершенные графы, их свойства. Теорема о характеризации совершенных графов. Класс хордальных графов. 11. Хроматические полиномы и их свойства. 12. Элементы теории Рамсея для графов. Аналоги теоремы Рамсея для порожденных графов. 13. Потоки в графах со значениями в Z и Z n . Теоремы и гипотезы Татта о потоках. 14. Труднорешаемые задачи на графах. Классы P, NP и NPC. Методы доказательства NP-полноты. Примеры NP-полных задач на графах. 15. Вероятностные методы в теории графов. Утверждения, верные для «почти всех» графов. 16. Перечисление и кодирование графов и деревьев. Теорема Пойа и ее следствия. Коды Прюффера. Кодирование плоских корневых деревьев. 5. Учебно-методическое и информационное обеспечение дисциплины (курса) 5.1. Примерный перечень вопросов к зачету (экзамену) по всему курсу. 1. Основные определения и обозначения, связанные с графами (понятия графа, мультиграфа, орграфа, смежность и инцидентность вершин и ребер, степени вершин, порожденные и остовные подграфы, полные графы, k-дольные, r- регулярные графы и r-факторы, изоморфизм и автоморфизм графов, маршруты, цепи, пути и циклы, связность, расстояние между вершинами, диаметр графа и т. д.). Способы задания графов. Лемма о рукопожатиях. 2. Способы задания графов и орграфов. Теорема о числе маршрутов, соединяющих две вершины графа (орграфа). 3. Двудольные графы Критерий двудольности графа. 4. Леса и деревья. Эквивалентные определения дерева. Корневые деревья. 5. Точки сочленения и мосты. Понятия вершинной и реберной k-связности графа. Эквивалентные определения вершинно-двусвязного графа. Простейшие операции, сохраняющие двусвязность. 6. Точки сочленения и блоки. Взаимное расположение двух блоков в графе. Дерево блоков и точек сочленения. 7. Поиск по графу в глубину и в ширину. Дерево поиска. Связь поиска в ширину с нахождением кратчайших цепей в графе. 8. Алгоритм нахождения блоков в связном графе. 9. Теорема о существовании остовного дерева (остова) в связном графе. Поиск минимального остова во взвешенном графе. Алгоритм Краскала. 10. Поиск минимального остова во взвешенном графе. Алгоритм Примы. 11. Кратчайшие пути во взвешенных орграфах. Алгоритм Дейкстры. 12. Кратчайшие пути во взвешенных орграфах. Алгоритм Флойда-Уоршелла. 13. Определения сети и потока. Задача о максимальном потоке. Остаточные сети, дополняющие пути и разрезы. Лемма о величине потока через разрез. 14. Сети и потоки в сетях. Задача о максимальном потоке. Теорема Форда-Фалкерсона. 15. Обобщенный алгоритм Форда-Фалкерсона. Анализ работы алгоритма в случае целых и рациональных пропускных способностей. 16. Метод кратчайших путей в задаче о максимальном потоке. 17. Теорема о наименьшем числе дуг, разделяющих два подмножества вершин орграфа. 18. Теорема о наименьшем числе вершин, разделяющих два подмножества вершин орграфа. 19. Теоремы Менгера (вершинный и реберный варианты). 20. Критерии вершинной и реберной k-связности графа (теоремы Уитни). 21. Гамильтоновы циклы и цепи, необходимые условия их существования. Достаточные условия гамильтоновости графа (теоремы Дирака и Оре). 22. Понятия эйлерова цикла и цепи. Эйлеровы графы. Теорема Эйлера и алгоритм Флери. 23. Независимые множества вершин и ребер графа. Вершинные и реберные покрытия, факторы и паросочетания. Числовые характеристики, связанные с независимостью и покрытиями, их простейшие свойства. 24. Лемма о строении минимального реберного покрытия графа. Теорема Галлаи. 25. Характеризация наибольших паросочетаний в терминах чередующихся цепей. 26. Алгоритм поиска наибольшего паросочетания и наименьшего вершинного покрытия в двудольном графе. Задача о назначениях. 27. Паросочетание, покрывающее долю двудольного графа. Связь с системами различных представителей и теоремой Холла. 28. Теоремы Кенига о числе реберной независимости двудольного графа и о (0,1)- матрицах. 29. Совершенные паросочетания и r-факторы. Критерий Татта существования 1- фактора (доказательство необходимости). 30. Теоремы Петерсена о 2-факторах в кубических графах и о 2-факторизуемости регулярных графов четной степени (без доказательства). 31. Раскраски вершин графов, k-раскрашиваемые и k-хроматические графы Простейшие оценки хроматического числа. Хроматическое число k-вырожденного графа. Теорема Брукса (без доказательства). 32. Раскраски ребер графов и мультиграфов. Хроматический класс. Нижние оценки хроматического класса. Теоремы Визинга и Шэннона (без доказательства). Неулучшаемость оценок. Хроматический класс двудольного графа. 33. Плоские и планарные графы. Понятие грани, ранга грани. Формула Эйлера, ее различные представления. 34. Верхняя оценка для числа ребер планарного графа. Максимальные планарные и плоские графы, триангуляции, 5-вырожденность планарных графов. 35. Подразбиения графов и их гомеоморфизм. Критерий планарности Понтрягина- Куратовского. 5.2. Основная литература. 1. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов // М.: Наука, 1990. 2. Харари Ф. Теория графов // М.: Мир, 1973. 3. Косточка А. В. Дискретная математика. Часть 2 // Новосибирск: НГУ, 2001. 4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ // М.: МЦНМО, 2001. 5.3. Дополнительная литература. 1. Дистель Р. Теория графов // Новосибирск: ИМ СО РАН, 2002. 6. Методические рекомендации по организации изучения дисциплины Итоговая оценка по курсу выставляется на основе результатов этих проверок, а также итогового теоретического экзамена и работы над рефератами по выбранным темам. Обучение предусматривает установочные лекции по темам и учебным модулям, сквозные реальные примеры для закрепления теоретических знаний, а также выполнение практических заданий по применению изучаемых методов. Задания приведены в приложении к данной программе. Каждому студенту предлагается написать реферат, список тем рефератов приведен в п. 4.5. настоящей программы. Предусматривается самостоятельная работа с литературой, регулярный обзор публикаций в периодической прессе и Интернете. Аттестация знаний проводится в виде экзамена. Билеты содержат два вопроса. Знание предмета оценивается по пятибалльной шкале. Положительная оценка за сданное семестровое задание (пятибалльная) является условием допуска к экзамену. При выставлении итоговой оценки учитываются не только оценки по заданиям и рефератам, но и активность студента в обсуждениях на занятиях. |