Модуль 3. Элементы теории графов.

Основные понятия теории графов. Определения графов различного типа. Изоморфизм. 

Матричные и числовые характеристики графов. Части графа. Маршруты и связность. Вершинная связность и реберная связность. Деревья и циклы. Минимальные маршруты в нагруженных графах. Экстремальные графы.

Простейшие алгоритмы теории графов. Представления графов и деревьев в ЭВМ. Путь минимальной суммарной длины во взвешенном графе. Алгоритм Дейкстры. Гамильтоновы циклы.

Задача коммивояжера. Кратчайшее остовное дерево. Алгоритм Краскала. Венгерский алгоритм построения совершенного паросочетания. Задача об оптимальном назначении. Потоки в сетях. Теорема Форда – Фалкерсона; алгоритм Форда – Фалкерсона.

Последнее изменение: понедельник, 28 сентября 2026, 09:39