Rivalry2

HTML Diff

14 added 14 removed

Original 2026-01-01

Modified 2026-02-26

1 В этом уроке разберем, что такое взвешенный граф и для чего он полезен. Также познакомимся с алгоритмом Крускала, и рассмотрим, как и почему он работает.

2 <h2>Что такое взвешенный граф</h2>

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

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

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

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

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

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

8 <h2>Что такое алгоритм Крускала</h2>

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

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

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

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

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

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

13 <h2>Почему алгоритм Крускала работает</h2>

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

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

15 - <ol><li>У $T$ нет циклов, поскольку алгоритм Крускала не может их создать</li>

15 + <ol><li>У T нет циклов, поскольку алгоритм Крускала не может их создать</li>

16 - <li>$T$ - связной граф, иначе мы могли бы добавить ребро между компонентами $T$ без цикла</li>

16 + <li>T - связной граф, иначе мы могли бы добавить ребро между компонентами T без цикла</li>

17 - <li>$T$ - охватывающий граф, который включает каждую вершину. Иначе мы могли бы добавить ребро из $T$ в вершину, которая не входит в $T$, не вызывая цикла</li>

17 + <li>T - охватывающий граф, который включает каждую вершину. Иначе мы могли бы добавить ребро из T в вершину, которая не входит в T, не вызывая цикла</li>

18 - <li>Мы знаем, что у деревьев на $n$ вершинах всегда $n-1$ ребро, поэтому нам нужно добавить ровно $n - 1$ ребро</li>

18 + <li>Мы знаем, что у деревьев на n вершинах всегда n-1 ребро, поэтому нам нужно добавить ровно n - 1 ребро</li>

19 - </ol>Теперь рассмотрим, почему у дерева Крускала $T$ - минимальный вес. Представим минимальное расходящееся дерево $S$, которое не равно $T$. Когда мы проходим через процесс Крускала и добавляем ребра, мы добавляем в $T$ ребро $e$, которое не является частью $S$.

19 + </ol>Теперь рассмотрим, почему у дерева Крускала T - минимальный вес. Представим минимальное расходящееся дерево S, которое не равно T. Когда мы проходим через процесс Крускала и добавляем ребра, мы добавляем в T ребро e, которое не является частью S.

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

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

21 - В этом примере показана гипотетическая часть $S$ вместе с $d$ и $e$:

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

22 - Теперь удалим $d$ из $S$ и заменим его на $e$ - это дерево $S - d + e$. Если просто менять одно ребро цикла на другое, $S - d + e$ все равно прямое дерево $G$.

22 + Теперь удалим d из S и заменим его на e - это дерево S - d + e. Если просто менять одно ребро цикла на другое, S - d + e все равно прямое дерево G.

23 - Процесс Крускала добавил ребро $e$, а не $d$. Это означает, что вес $e$ меньше или равен весу $d$. Это делает $S - d + e$ минимальным прямым деревом $G$, которое согласуется с $T$ на одно ребро больше, чем $S$.

23 + Процесс Крускала добавил ребро e, а не d. Это означает, что вес e меньше или равен весу d. Это делает S - d + e минимальным прямым деревом G, которое согласуется с T на одно ребро больше, чем S.

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

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

25 <h2>Выводы</h2>

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