Тема 2.4 Алгоритмы на графах

Методы хранения графов в памяти ЭВМ. Модели в виде графа. Задача о минимальном остове и метод её решения. Задача о нахождении кратчайшего пути в графе и метод её решения. Задача о максимальном потоке и алгоритм Форда-Фалкерсона. Транспортная задача в сетевой постановке. Признак оптимальности. Метод решения. Алгоритм Прима построения кратчайшей связной сети. Проблема Штейна. Задача о построении дерева кратчайших расстояний: сведение к транспортной задаче, метод Дейкстры. Задача коммивояжера.

Студент должен:

Знать:

основные понятия теории графов: граф, вершина, ребро, вес ребра;

методы хранения графов в памяти ЭВМ;

методы решения следующих задач: о нахождении минимального остова; о нахождении кратчайшего пути в графе; о максимальном потоке;

алгоритм Форда-Фалкерсона;

Уметь:

описывать реальные системы с помощью графов;

доказывать решаемость графовых задач;

находить минимальный остов;

находить кратчайшие пути в графе;

определять максимальный поток методом Форда-Фалкерсона;

решать задачу коммивояжера методом ветвей и границ.

Практическая работа № 2 «Решение задачи о построении дерева кратчайших расстояний» (1 ч)

Вопросы для самопроверки по теме 2.4:

Назовите основные элементы графа.

Перечислите методы хранения графов в памяти ЭВМ.

Что называют транспортной сетью?

Какие задачи решают с помощью графов?

Дайте определение разреза сети.

Как найти минимальный остов?

Сформулируйте алгоритм Форда-Фалкерсона.

Как решается транспортная задача в сетевой постановке?

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

В чем заключается проблема Штейна?

Перечислите методы построении дерева кратчайших расстояний.

В чем заключается сущность метода ветвей и границ?

Каким свойствам должна удовлетворять вершина в методе ветвей и границ?

Сформулируйте алгоритм решения задачи коммивояжера методом ветвей и границ.