Минимальное остовное дерево

Если дугам приписаны стоимости d_ij, то стоимость остовного дерева определяется как сумма d_ij по всем дугам дерева. Остовное дерево с наименьшей стоимостью среди всех остовных деревьев называется минимальным остовным деревом.

Замечание 3. В общем случае минимальное остовное дерево отличается от дерева кратчайших путей.

Следующие две леммы кажутся очевидными, однако их доказательства требуют внимательного изучения.

Лемма 1. Пусть V_a — произвольный узел и е_ах — кратчайшая дуга среди всех дуг, смежных с V_a. Тогда существует минимальное остовное дерево Т*, содержащее дугу е_ах.

Доказательство. Пусть Т — минимальное остовное дерево, а, А — подмножество дуг, смежных с V_a, например, А = {e_ab, e_ac, e_ad, e_ax}. Предположим, что дуга е_ах является кратчайшей дугой, смежной с V_a, но не принадлежит Т. Поскольку Т — остовное дерево, то в Т должен быть путь из V_x в V_a, содержащий одну из дуг А, например, e_ad. Обозначим этот путь через (P_xd, e_da), где P_xd — путь из V_x в V_d. Заменяя e_ad на е_ах, получим Т*. Если е_ах короче, чем e_ad, то заключаем, что Т* — остовное дерево с меньшей стоимостью.

Во-первых, в дереве Т* V_a соединяется с V_x дугой е_ах, а с узлом V_d – путем (e_ax,P_xd). Оставшиеся узлы V_b, V_c по-прежнему связаны с V_a и, следовательно, с остальными узлами сети, значит, Т* является остовным деревом.

Во-вторых, стоимость Т* меньше, чем Т, так как е_ах короче, чем e_ad. Это противоречит предположению о том, что Т — минимальное остовное дерево. Если дуги e_ad и е_ах имеют одинаковые длины, то также можно заменить е_аd на е_ах и получить минимальное остовное дерево Т*, содержащее е_ах.

Лемма 2. Если известно, что подмножество ребер, образующих поддерево F, является частью минимального остовного дерева, то существует минимальное остовное дерево, содержащее F, и минимальное ребро, соединяющее F u N-F.

Доказательство. Доказательство в точности совпадает с доказательством леммы 1, если заменить V_a на F.

По лемме 1 можно начать из произвольной вершины и выбрать наименьшую смежную дугу. Так как известно, что только что выбранная дуга является частью минимального остовного дерева, то можно в лемме 2 взять ее в качестве F и выбрать наименьшую дугу, инцидентную F.

Можно продолжить выбор наименьшего ребра, инцидентного уже выбранной компоненте. Это алгоритм Прима для нахождения минимального остовного дерева.

Идея алгоритма следующая. Алгоритм создает последовательные связные поддеревья, путем присоединения на каждом шаге одной смежной дуги так, чтобы на каждой стадии была выбрана инциндентная дуга с самой маленькой стоимостью. Пример реализации идеи алгоритма Прима представлен на рис. 12. Если начальный узел V ₀, то последовательность присоединяемых дуг следующая: дуга со стоимостью 1, смежная (вертикальная) дуга со стоимостью 2, дуга (горизонтальная) со стоимостью 2, дуга со стоимостью 4, дуга со стоимостью 3. Стоимость минимального остовного дерева 12.

Рис. 12. Пример минимального остовного дерева

Замечание 4. Алгоритм Прима для минимального остовного дерева сходен с алгоритмом Дейкстры для нахождения кратчайших путей.