Инспектор
Практикум по теории графов
: Информация
Опубликована: 22.04.2015 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность:
Практикум по решению задач по теории графов и связанным с ними алгоритмам.
Даются основные понятия теории графов, решаются оптимизационные задачи на графах, рассказывается об алгоритмах поиска и матричных методах анализа графов.
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
Лекция 1 | Логика предикатов. Графы, общие определения
Кванторы всеобщности и существования. Связанные переменные. Область действия квантора. Эквивалентные соотношения в логике предикатов. Чистая логика предикатов и прикладные логики предикатов. Понятия графа. Классификация графов: по наличию ориентирования ребер (неориентированный и ориентированный графы), по наличию кратности ребер (простой граф и мультиграф). Отношение смежности между вершинами, матрица смежности.
Отношение инцидентности между вершинами и ребрами. Степень вершины. Изолированные вершины, висячие вершины. Пустой граф, полный граф.
Оглавление | - |
Лекция 2 | Теория графов. Основные понятия
Матрица смежности, степень вершины.
Подграф и часть графа. Звезда вершины графа. Полный граф. Клика. Максимальный и минимальный (относительно некторого свойства) подграф. Изоморфизм графов.
Неориентированные графы. Путь, цепь, простая цепь, цикл. Связанные вершины. Связный граф. Компоненты связности. Длина пути. Расстояние между вершинами в связном графе. Аксиомы метрики (расстояния).
Оглавление | - |
Лекция 3 | Теория графов. Основные понятия (продолжение)
Радиус графа, центры графа. Эйлеров обход. Задача о кенигсбергских мостах.
Алгоритм построения эйлерова цикла. Задача о гамильтоновом обходе (задача коммивояжера).
Ориентированные графы (орграфы). Ориентированный путь, ориентированный цикл. Достижимость. Виды связности: сильная связность, односторонняя связность, слабая связность.
Компонента сильной связности. Конденсация, граф конденсации.
Ациклический граф. Источники и стоки. Топологическая сортировка.
Оглавление | - |
Лекция 4 | Деревья. Оптимизационные задачи на графах. Задача о кратчайшем пути
Неориентированные деревья. Ориентированные деревья.
Применение деревьев: классификация, представление формул, бинарное дерево поиска.
Оптимизационные задачи на графах. Взвешенные (нагруженные) графы. Задача о кратчайшем пути в неориентированном графе без весов. Ранжирование вершин. Задача о кратчайшем пути в взвешенном графе. Алгоритм Дейкстры.
Оглавление | - |
Лекция 5 | Оптимизационные задачи на графах. Сетевое планирование. Потоки в сетях
Сетевой график. Задача поиска максимальных путей в графе.
Понятия раннего срока и позднего срока. Критический путь. Виды резерва: полный резерв, свободный резерв, независимый резерв. Потоки в сетях. Понятие потока, величина потока. Закон Кирхгофа. Увеличивающаяся цепь.
Оглавление | - |
Лекция 6 | Оптимизационные задачи на графах. Алгоритм поиска увеличивающей цепи
Алгоритм поиска увеличивающей цепи. Разрезы. Пропускная способность разреза.
Оглавление | - |
Лекция 7 | Матричные методы анализа графов. Графы и бинарные отношения
Матричные методы анализа графов. Степень матрицы смежности графа. Сумма степеней матрицы смежности, достижимость и связность. Транзитивное замыкание. Графы и бинарные отношения. Отношения эквивалентности и отношения порядка в терминах графов. Матричные методы анализа мультиграфов. Двудольные графы. Задача о раскраске графа.
Оглавление | - |
3 минуты | - |