Вопрос 12. Корректность алгоритма Краскала.
Теор.: (Корректность алгоритма Краскала): При i<n-1 алгоритм Краскала обеспечивает построение графа Ti+1. построенный граф Ti+1 яв-ся минимальным остовным деревом исходного графа.
Док-во:
1) При i<n-1 граф Ti несвязный, т.к. граф G связный то в нем найдется по крайней мере одно ребро добавление которого в граф Ti не порождает цикл. Следовательно граф Ti+1 можно построить.
2) Предположим что Ti-1 остовное дерево графа G но не минимальное по весу. Из мн-ва всех остовных деревьев минимального веса графа G выбираем остов T имеющий с деревом Ti-1 набольшее количество общих ребер.
Т.к. на каждом шаге алгоритма Краскала каждое ребро помечается индексом то пусть ei-ребро дерева Ti-1 не принадлежащее T и не имеющее наименьший индекс среди таких ребер, т.е. ребра e1, e2, …, ei-1 принадлежат как Ti-1 так и T. Пусть ei=(u,v), тогда в остове T существует (u,v)-цепь. Очевидно объединение этой (u,v)-цепи и ребра ei образует цикл. Пусть e-некоторое ребро цикла принадлежащее T и не принадлежащее Ti-1. Строим остовное дерево T’=T-e+ei Очевидно что w(T’)=w(T)-w(e)+w(ei). Следовательно т.к. T-остов минимального веса w(T’)>=w(T) следовательно w(e)<=w(ei).
Т.к. первые i-1 ребра деревьев T и Ti-1 общие то при добавлении к ребрам e1, …,ei-1 ребра ei не получаем цикл и если бы w(ei)>w(e) при построении дерева Ti-1 выбрали бы ребро e (согласно алгоритму Краскала). Следовательно w(ei)=w(e). Т.о. w(T’)=w(T), т.е. T’-остовное дерево минимального веса. Т.о. построенное T’ минимальное остовное дерево имеет больше общих ребер с Ti-1 чем с T, что противоречит выбору минимального остовного дерева T. Т.о. доказано что построенный по алгоритму Краскала граф Ti-1 яв-ся минимальным остовным деревом графа G.