Дискретная математика (часть 4)

Комментарии преподавателя

Радиус графа, центры графа. Эйлеров обход. Задача о кенигсбергских мостах. Алгоритм построения эйлерова цикла. Задача о гамильтоновом обходе (задача коммивояжера). Ориентированные графы (орграфы). Ориентированный путь, ориентированный цикл. Достижимость. Виды связности: сильная связность, односторонняя связность, слабая связность. Компонента сильной связности. Конденсация, граф конденсации. Ациклический граф. Источники и стоки. Топологическая сортировка.

Неориентированные деревья. Ориентированные деревья. Применение деревьев: классификация, представление формул, бинарное дерево поиска. Оптимизационные задачи на графах. Взвешенные (нагруженные) графы. Задача о кратчайшем пути в неориентированном графе без весов. Ранжирование вершин. Задача о кратчайшем пути в взвешенном графе. Алгоритм Дейкстры.

Сетевой график. Задача поиска максимальных путей в графе. Понятия раннего срока и позднего срока. Критический путь. Виды резерва: полный резерв, свободный резерв, независимый резерв. Потоки в сетях. Понятие потока, величина потока. Закон Кирхгофа. Увеличивающаяся цепь.

Алгоритм поиска увеличивающей цепи. Разрезы. Пропускная способность разреза.

Матричные методы анализа графов. Степень матрицы смежности графа. Сумма степеней матрицы смежности, достижимость и связность. Транзитивное замыкание. Графы и бинарные отношения. Отношения эквивалентности и отношения порядка в терминах графов. Матричные методы анализа мультиграфов. Двудольные графы. Задача о раскраске графа.

Файлы

Нет дополнительных материалов для этого занятия.