zhChinese    enEnglish
  ПМ-ПУ  » Образование  » Программы курсов » Теория конечных графов и их приложения

Теория конечных графов и их приложения

Общий курс

Составитель: к.т.н., доцент Новожилова Л.М.

Введение. Топологические модели систем, процессов, сетей. Оптимизационные задачи на дискретных конечных структурах.
1. Задачи, алгоритмы и сложность. Дискретность и комбинаторность.
2. Решение с помощью ЭВМ. Интерактивные технологии.
3. Точные и приближенные решения.
4. Вычислительная сложность решений.
5. Теория графов как категория списка NP-полных задач.
Тема 1. Основные понятия и определения.
1. Теоретико-множественные, геометрические и матричные математические модели графов.
2. Представление графов в памяти ЭВМ матрицами и списками.
3. Морфизмы и изоморфизм графов.
4. Типы графов. Графы, подграфы.
5. Пути и циклы. Иерархия понятий. Эйлеровы обходы.
6. Простые пути и алгебраические процедуры их перечисления.
7. Взвешенные графы - сети.
Тема 2. Связность и достижимость.
1. Степени связности вершин графа.
2. Сильные компоненты графа. Конденсация графа.
3. Алгоритмы нахождение сильных компонент.
4. Базы и антибазы графа. Приложения для анализа корпоративных сетей.
Тема 3. Устойчивые множества.
1. Внешне устойчивые (доминирующие) множества и внутренне устойчивые (независимые) множества. Клика графа.
2. Шахматные аналогии.
3. Инварианты графов: числа доминирования и независимости, кликовое число.
4. Связь понятий: теорема Рамсея.
5. Алгоритмы перечисления максимальных независимых множеств графа.
6. Сводимость алгоритмов, оценки вычислительной сложности.
7. Приложения в теории информации.
Тема 4. Покрытия и разбиения.
1. Вершинное покрытие. Задача о наименьшем покрытии.
2. Приложения: оптимизация размещения информационных центров на данной территории.
3. Задача о назначениях.
4. Разбиение графа на клики.
5. Покрытие кликами. Покрытие полными двудольными подграфами.
Тема 5. Раскраски.
1. Раскраска и раскрашиваемость графа. Хроматическое число, оценки.
2. Задача об оптимальной раскраске. Точные и приближенные алгоритмы.
3. Решение методом динамического программирования. Метод сведения к задаче о наименьшем покрытии максимальными независимыми множествами.
4. Интерпретация задачи в терминах булева программирования.
5. Приложения: задачи оптимальной организации структуры банков данных, размещения элементов распределенных сложных систем, распределения ресурсов, слияния банков данных, календарного планирования профилактических ремонтов сложных систем.
Тема 6. Размещение центров и медиан в графах.
1. Абсолютные центр и медиана графа. Алгоритм нахождения абсолютного центра методом Хакими.
2. Приложения: территориальное размещение снабженческих и спасательных служб.
Тема 7. Деревья.
1. Остовное дерево графа. Граф остовов. Процедуры разборки и сборки графа.
2. Теорема Кэли. Матричная теорема о деревьях.
3. Полиномиальная лексико-графическая процедура перечисления остовных деревьев графа. Иерархические структуры данных информационных систем.
4. Кратчайший остов графа. Алгоритмы построения кратчайшего остова графа.
5. Евклидова задача Штейнера нахождения кратчайшего дерева, стягивающего данное множество точек. Точки Штейнера.
6. Приложения в радиоэлектронике, теории коммуникаций и логистике.
7. Потоковые алгоритмы. Сетевая модель комплекса операций.
Тема 8. Циклы, разрезы и задача Эйлера.
1. Фундаментальные циклы и фундаментальные разрезы графа, порождаемые данным остовом, как алгебраические объекты данных. Свойства матриц фундаментальных циклов и фундаментальных разрезов.
2. Эйлеровы циклы. Критерий Эйлера. Алгоритм построения эйлерова цикла в графе.
3. Задача китайского почтальона. Алгоритмы решения.
4. Приложения: сбор мусора в ЭВМ, доставка почты, оптимальные процедуры контроля коммуникаций.
5. Гамильтоновы цепи и циклы.
6. Задача коммивояжера. Связь с задачей о назначениях и с задачей о кратчайшем остове.
7. Алгоритмы решения.
Тема 9. Паросочетания.
1. Теорема Холла-Кенига. Задача о максимальном паросочетании.
2. Общая процедура построения остовного подграфа с предписанными степенями.
3. Применение теории потоков в теории паросочетаний.
4. Венгерский метод, матричная форма. Связь с задачей о покрытии.
5. Транспортная задача.
Тема 10. Кратчайшие пути на графах.
1. Варианты задач. Обзор методов решения. Алгоритм Дейкстры нахождения кратчайшего пути, связывающего две заданные вершины графа.
2. Алгоритм Флойда нахождения кратчайших путей между всеми парами вершин.
3. Алгоритмы Форда, Мура и Беллмана.
4. Задачи, близкие к задаче о кратчайшем пути. Наиболее надежный путь. Путь с наибольшей пропускной способностью.
5. Теорема о максимальном потоке и минимальном разрезе Форда и Фалкерсона.
6. Алгоритмы нахождения максимального потока и минимального разреза.

Список рекомендуемой литературы:

  1. Берж К. теория графов и ее применение. 1962.
  2. Горбатов В. А. Основы дискретной математики. 1986.
  3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. 1982.
  4. Гоппа В. Д. Введение в алгебраическую теорию информации. 1995.
  5. Кристофидес Н. Теория графов. Алгоритмический подход. 1978.
  6. Оре О. Теория графов. 1980.