11

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

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

Докажем, что (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.

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

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

Докажем, что (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 , имеющее общий конец с одним из 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 , имеющее общий конец с одним из e1; : : : ; ek . По алгоритму имеем

(ek ) (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 , имеющее

общий конец с одним из e1; : : : ; ek . По алгоритму имеем

(ek ) (e): Тогда U0 = (V ; S0), S0 = (S [ fek+1g) n feg

имеет степень близости> k, но (T ) > (U) (U0):