Корректность алгоритма Прима — различия между версиями

Версия 16:10, 8 октября 2014

Цыганова Светлана, 974 гр. Докажите корректность алгоритма Прима построения минимального остовного дерева взвешенного связного неориентированного графа.

Решение:

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

2) Докажем, что получившееся дерево - минимальный остов графа. Будем рассматривать алгоритм поитерационно, доказывая, что на каждой итерации мы присоединяем к построенному поддереву ребро из действительно минимального остовного дерева.

Итак, пусть дерево T - результат работы алгоритма Прима, а T1 - действительно минимальное остовное дерево, и пусть T1 и T не совпадают.

Пусть e - первое ребро в строящемся дереве Y по алгоритму Прима, такое, что оно не лежит в T1. Но тогда в минимальном остовном дереве T1 есть ребро f, такое что оно соединяет какую-либо из вершин из Y\{e}, с одной из оставшихся вершин. Тогда на той итерации, на которой мы хотели добавить ребро e был и вариант добавить ребро f, но f не было добавлено, следовательно, его вес больше или равен весу ребра e. Пусть T2 - минимальное остовное дерево T1, из которого удалено ребро f и добавлено ребро e. Тогда T2 - минимальное остовное дерево с суммарным весом, меньшим, или равным весу T1. Тогда либо T1 не было минимальным остовным деревом (что ведет к противоречию), либо существует равносильное минимальное остовное дерево, у которого построенное алгоритмом Прима дерево Y является поддеревом. Тогда при добавлении ребра e мы получаем поддерево минимального остовного дерева.

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