11

Нахождение остова наименьшего веса

Алгоритм Краскала

Пусть задан связный взвешенный граф G = (V ; E; ) с n вершинами.

Определим P0 = ?. Повторим следующую процедуру для каждого k = 1; 2; : : : n 1:

Нахождение остова наименьшего веса

Алгоритм Краскала

Пусть задан связный взвешенный граф G = (V ; E; ) с n вершинами.

Определим P0 = ?. Повторим следующую процедуру для каждого k = 1; 2; : : : n 1:

I Пусть Pk 1 = fe1; e2; : : : ek 1g уже определено.

Нахождение остова наименьшего веса

Алгоритм Краскала

Пусть задан связный взвешенный граф G = (V ; E; ) с n вершинами.

Определим P0 = ?. Повторим следующую процедуру для каждого k = 1; 2; : : : n 1:

IПусть Pk 1 = fe1; e2; : : : ek 1g уже определено.

IНайдем ребро ek 2 E n Pk 1 наименьшего веса такое, что ребра e1; e2; : : : ek 1; ek не образуют циклов.

Нахождение остова наименьшего веса

Алгоритм Краскала

Пусть задан связный взвешенный граф G = (V ; E; ) с n вершинами.

Определим P0 = ?. Повторим следующую процедуру для каждого k = 1; 2; : : : n 1:

IПусть Pk 1 = fe1; e2; : : : ek 1g уже определено.

IНайдем ребро ek 2 E n Pk 1 наименьшего веса такое, что ребра e1; e2; : : : ek 1; ek не образуют циклов.

IОпределим Pk = fe1; e2; : : : ek 1; ek g.

Нахождение остова наименьшего веса

Алгоритм Краскала

Пусть задан связный взвешенный граф G = (V ; E; ) с n вершинами.

Определим P0 = ?. Повторим следующую процедуру для каждого k = 1; 2; : : : n 1:

IПусть Pk 1 = fe1; e2; : : : ek 1g уже определено.

IНайдем ребро ek 2 E n Pk 1 наименьшего веса такое, что ребра e1; e2; : : : ek 1; ek не образуют циклов.

IОпределим Pk = fe1; e2; : : : ek 1; ek g.

Дерево T = (V ; P), где P = Pn 1, является искомым остовом наименьшего веса.

Нахождение остова наименьшего веса

Обоснование алгоритма Краскала

Докажем, что (T ) (U) для прозвольного остова U = (V ; S) взвешенного графа G = (V ; E; ).

Нахождение остова наименьшего веса

Обоснование алгоритма Краскала

Докажем, что (T ) (U) для прозвольного остова

U = (V ; S) взвешенного графа G = (V ; E; ). Предположим, что для некоторых остовов указанное неравенство не выполняется.

Нахождение остова наименьшего веса

Обоснование алгоритма Краскала

Докажем, что (T ) (U) для прозвольного остова

U= (V ; S) взвешенного графа G = (V ; E; ). Предположим, что для некоторых остовов указанное неравенство не выполняется.

Назовем число k = 1; 2; : : : ; n 1 степенью близости остова

U= (V ; S), если k наибольшее число такое, что

e1; e2; : : : ek 2 S.

Нахождение остова наименьшего веса

Обоснование алгоритма Краскала

Докажем, что (T ) (U) для прозвольного остова

U= (V ; S) взвешенного графа G = (V ; E; ). Предположим, что для некоторых остовов указанное неравенство не выполняется.

Назовем число k = 1; 2; : : : ; n 1 степенью близости остова

U= (V ; S), если k наибольшее число такое, что

e1; e2; : : : ek 2 S.

Выберем остов U = (V ; S) наибольшей возможной степени близости k, что (T ) > (U).

Нахождение остова наименьшего веса

Обоснование алгоритма Краскала

Докажем, что (T ) (U) для прозвольного остова

U= (V ; S) взвешенного графа G = (V ; E; ). Предположим, что для некоторых остовов указанное неравенство не выполняется.

Назовем число k = 1; 2; : : : ; n 1 степенью близости остова

U= (V ; S), если k наибольшее число такое, что

e1; e2; : : : ek 2 S.

Выберем остов U = (V ; S) наибольшей возможной степени

близости k, что (T ) > (U). Имеем k < n 1, e1; : : : ; ek 2 S и ek+1 2= S.