11
.pdf
Нахождение остова наименьшего веса
Обоснование алгоритма Краскала
Докажем, что (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. Тогда среди ребер S [ fek+1g можно выбрать цикл, содержащий также ребро e 2 S; e 6= e1; : : : ; ek .
Нахождение остова наименьшего веса
Обоснование алгоритма Краскала
Докажем, что (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. Тогда среди ребер S [ fek+1g можно выбрать цикл, содержащий также ребро e 2 S; e 6= e1; : : : ; ek . По алгоритму имеем (ek+1) (e):
Нахождение остова наименьшего веса
Обоснование алгоритма Краскала
Докажем, что (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. Тогда среди ребер S [ fek+1g можно выбрать цикл, содержащий также ребро e 2 S; e 6= e1; : : : ; ek . По алгоритму имеем (ek+1) (e): Тогда U0 = (V ; S0),
S0 = (S [ fek+1g) n feg имеет степень близости > k, но
(T ) > (U) (U0):
Нахождение остова наименьшего веса
Алгоритм Прима
Пусть задан связный взвешенный граф G = (V ; E; ) с n вершинами.
Нахождение остова наименьшего веса
Алгоритм Прима
Пусть задан связный взвешенный граф 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; : : : ek 1; ek не образуют циклов, и ek имеет общий конец с одним из e1; : : : ek 1 .
Нахождение остова наименьшего веса
Алгоритм Прима
Пусть задан связный взвешенный граф 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; : : : ek 1; ek не образуют циклов, и ek имеет общий конец с одним из e1; : : : ek 1 .
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; : : : ek 1; ek не образуют циклов, и ek имеет общий конец с одним из e1; : : : ek 1 .
IОпределим Pk = fe1; e2; : : : ek 1; ek g.
Дерево T = (V ; P), где P = Pn 1, является искомым остовом наименьшего веса.
Нахождение остова наименьшего веса
Обоснование алгоритма Прима
Докажем, что (T ) (U) для прозвольного остова U = (V ; S) взвешенного графа G = (V ; E; ).