|
|
| Строка 1: |
Строка 1: |
| − | <big>Цыганова Светлана, 974 гр.</big>
| |
| | Докажите корректность алгоритма Прима построения минимального остовного дерева взвешенного связного неориентированного графа. | | Докажите корректность алгоритма Прима построения минимального остовного дерева взвешенного связного неориентированного графа. |
| | | | |
| − | '''Решение:'''
| + | [[Category:Решенные задачи]] |
| − | | + | |
| − | 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:На проверку]] | + | |
Докажите корректность алгоритма Прима построения минимального остовного дерева взвешенного связного неориентированного графа.