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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 16 промежуточных версий этого же участника)
Строка 1: Строка 1:
<big>Цыганова Светлана, 974 гр.</big>
 
 
Докажите корректность алгоритма Прима построения минимального остовного дерева взвешенного связного неориентированного графа.
 
Докажите корректность алгоритма Прима построения минимального остовного дерева взвешенного связного неориентированного графа.
  
'''Решение:'''
+
[[Категория:Решенные задачи]]
 
+
[[Категория:Теоретические задачи]]
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'' мы получаем поддерево минимального остовного дерева.
+
 
+
Все эти выкладки повторяются для каждой итерации алгоритма Прима, и на каждой итерации мы получаем поддерево минимального остовного, следовательно, в конце результатом работы алгоритма будет являться минимальное остовное дерево, ч.т.д.
+
+
[[Category:На проверку]]
+

Текущая версия на 06:50, 4 мая 2023

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