Взвешенный граф — Теория графов

Взвешенный граф — это граф, в котором каждое ребро обозначается числом. Это число — его вес:

Вес — это стоимость использования данного ребра. Например, приведенный выше граф может представлять дорожную сеть, где вершины — это города, ребра — дороги между ними, а вес — стоимость строительства этих дорог.

Предположим, что мы хотим построить дороги, чтобы добраться из одного города в другой. Нам нужно сделать это как можно дешевле. Так может выглядеть ответ:

В этом случае нам не нужны циклы, так как мы пытаемся сделать все как можно дешевле. Мы хотим добираться до любой вершины графа, поэтому нам нужно минимальное охватывающее дерево, в котором сумма весов всех ребер в дереве как можно меньше.

Существует несколько алгоритмов, чтобы найти минимальные прямые деревья. В этом уроке мы рассмотрим алгоритм Крускала.

Алгоритм Крускала строит охватывающее дерево графа по одному ребру за раз. На каждом шаге алгоритма мы берем ребро с таким весом, чтобы добавление этого ребра в строящееся дерево не создавало цикла.

Мы можем разрывать связи между весом ребер как угодно, или добавлять ребра до тех пор, пока это не станет невозможным. В графе с вершинами нам всегда потребуется добавить ровно ребро.

Так это выглядит (грани выделены в порядке их добавления):

С помощью алгоритма Крускала на каждом шаге выбирается самое дешевое доступное ребро. В этом случае не нужно задумываться о будущих последствиях этого выбора. Эта стратегия всегда дает минимальное остовное дерево.

Разберем несколько причин, почему граф , который строит алгоритм Крускала, действительно остовное дерево графа:

Теперь рассмотрим, почему у дерева Крускала — минимальный вес. Представим минимальное расходящееся дерево , которое не равно . Когда мы проходим через процесс Крускала и добавляем ребра, мы добавляем в ребро , которое не является частью .

Предположим, мы попытаемся добавить в . Это создаст цикл по основным свойствам деревьев. Вдоль этого цикла должно быть еще какое-то ребро , которого нет в . — это дерево, и оно не может содержать все ребра этого цикла.

В этом примере показана гипотетическая часть вместе с и :

Теперь удалим из и заменим его на — это дерево . Если просто менять одно ребро цикла на другое, все равно прямое дерево .

Процесс Крускала добавил ребро , а не . Это означает, что вес меньше или равен весу . Это делает минимальным прямым деревом , которое согласуется с на одно ребро больше, чем .

Мы можем повторять этот процесс, пока не получим минимальное остовное дерево, которое согласуется с по каждому ребру. Это означает, что должно быть минимальным остовным деревом.

Мы разобрались, что такое взвешенный граф и для чего он полезен. Также познакомились с алгоритмом Крускала, и поняли, почему он работает. Написать код, который реализует алгоритм Крускала, несложно. Самое сложное — проверить, не создает ли добавление ребра цикл. Например, это можно сделать с помощью структуры данных disjoint set.