Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

во-первых, известны "расстояния" между каждой парой объектов (это может быть геометрическое расстояние или стоимость прокладки коммуникаций между ними),
во-вторых, объекты могут быть связаны как непосредственно, так и с участием произвольного количества промежуточных объектов.
При допущении, что разветвления возможны только в этих же n объектах, задача сводится к нахождению кратчайшего остовного дерева (SST - shortest spanning tree, или MST - minimal spanning tree) во взвешенном графе, вершины которого соответствуют заданным объектам, а веса ребер равны "расстояниям" между ними.
Определение. Вес остовного дерева взвешенного графа G равен сумме весов, приписанных ребрам остовного дерева. Будем обозначать (T).
Минимальным остовным деревом (МОД) называется такое остовное дерево графа G, что вес T меньше или равен весу любого другого остовного дерева графа G. Вес минимального остовного дерева будем обозначать _min(T).
Задача: найти кратчайшее остовное дерево (минимальный покрывающий остов) взвешенного графа.
Пусть дан неориентированный связный граф со взвешенными ребрами. Вес ребра (x_i,x_j) обозначим c_ij. Из всех остовов графа необходимо найти один, у которого сумма весов на ребрах наименьшая.
Стоимость остовного дерева вычисляется как сумма стоимостей всех рёбер, входящих в это дерево.



Построение остова графа G, имеющего наименьший вес, имеет широкое применение при решении некоторого класса задач прикладного характера.
НаПример.
Пусть, например, G=(V, E, ) служит моделью железнодорожной сети, соединяющей пункты v₁, v₂, …, v_nV, а (v_i, v_j) – расстояние между пунктами v_i и v_j.
Требуется проложить сеть телеграфных линий вдоль железнодорожной сети так, чтобы все пункты v₁, v₂, …, v_n были связаны между собой телеграфной сетью, протяженность которой была бы наименьшей.
Рассмотрим два способа построения минимального остовного дерева взвешенного графа: алгоритм Крускала и алгоритм Прима.