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




НазваниеАннотация курса “Графы и алгоритмы” лектор к ф. м н. А. Н. Глебов
Дата03.02.2016
Размер8.98 Kb.
ТипТематический план
Аннотация курса “Графы и алгоритмы”

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

Название курса.


Теория графов (Графы и алгоритмы)

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

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

Семестр(ы) — 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

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





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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



Литература





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




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




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




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

М.: МЦНМО, 2001.

Похожие:

Аннотация курса “Графы и алгоритмы” лектор к ф. м н. А. Н. Глебов iconПрограмма обязательного курса «Вариационное исчисление и оптимальное управление» 4 курс 1 поток (лектор А. В. Фурсиков, декабрь 2012г.)

Аннотация курса “Графы и алгоритмы” лектор к ф. м н. А. Н. Глебов iconПрограмма курса «Политология» Лектор: Валерий Георгиевич Ледяев Преподаватель практических занятий: Валерий Георгиевич Ледяев
В заключительной части рассматриваются политические режимы и проблемы перехода к демократии. На протяжении всего курса обсуждаются...
Аннотация курса “Графы и алгоритмы” лектор к ф. м н. А. Н. Глебов iconПрограммах в аннотация. В
Далее переходим к обсуждению как его искать, какие модели или представления программ полезны и ка­кие алгоритмы на них используются....
Аннотация курса “Графы и алгоритмы” лектор к ф. м н. А. Н. Глебов iconАннотация курса «Современная политология в контексте новейшего гуманитарного знания» Цели и задачи курса
Аннотация курса «Современная политология в контексте новейшего гуманитарного знания»
Аннотация курса “Графы и алгоритмы” лектор к ф. м н. А. Н. Глебов iconУчебного курса численные методы для студентов факультета Прикладной математики и информатики Филиала мгу им. М. В. Ломоносова в г. Ташкенте
Обязательный курс для студентов 3 курса, кафедры ио, мс, мк, оу, чи­тается в 6 семестре. Лекции 64 часа. Экзамен в 6 семестре. За...
Аннотация курса “Графы и алгоритмы” лектор к ф. м н. А. Н. Глебов iconАдаптивные алгоритмы индентирования и царапанья сзм наноскан
Разработаны алгоритмы адаптивного индентирования и царапанья, позволяющие повысить точность измерения механических характеристик...
Аннотация курса “Графы и алгоритмы” лектор к ф. м н. А. Н. Глебов iconИ. Т. Глебов
Цель работы: освоение методики и приобретение практических навыков определения класса точности станка
Аннотация курса “Графы и алгоритмы” лектор к ф. м н. А. Н. Глебов iconМетодические алгоритмы проектов, направленных на формирование устойчивых привязанностей к семье, городу, стране
«устойчивых привязанностей к семье, дому, школе, классу, малой родине, городу, региону, России». Этому посвящен цикл проектов, реализация...
Аннотация курса “Графы и алгоритмы” лектор к ф. м н. А. Н. Глебов icon2 место Шаповалова Е. В. II. Победители и призеры гимназической олимпиады
Торбогошев Артур Адинарович, Глебов Антон Александрович, Тайтова Карина Владленовна
Аннотация курса “Графы и алгоритмы” лектор к ф. м н. А. Н. Глебов iconИ. Т. Глебов (углту, г. Екатеринбург, рф)
Качество механической обработки изделий на станках характеризуется точностью размеров и формы деталей и шероховатостью обработанных...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib2.znate.ru 2012
обратиться к администрации
Библиотека
Главная страница