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

Версия 01:37, 26 декабря 2014

@@ Строка 1: / Строка 1: @@
-'''Цыганова Светлана, 974гр'''
 <latex>
 Докажите, что связный ненаправленный граф с ребрами попарно различной длины имеет только одно минимальное остовное дерево.
 </latex>
-'''Решение'''
-Докажем от противного: пусть у графа есть 2 минимальных остовных дерева - А и В. Тогда существует ребро ''ed<sub>1</sub>'', которое есть в одном из них, и нет в другом. Тогда из всех ребер, которые есть в А и нет в В и тех, которые есть в В и нет в А выберем ребро наименьшего веса. Оно единственно, так как все ребра попарно различной длины по условию задачи.
-Назовем выбранное ребро ''ed<sub>1</sub>'', и пусть оно принадлежит МОД А, иначе переименуем деревья.
-Рассмотрим граф B' = {ed<sub>1</sub>}U B. Так как В - МОД, и ''ed<sub>1</sub>'' не лежит в В, то В' содержит цикл (назовем его цикл С). Рассмотрим этот цикл. В этом цикле есть хотя бы одно ребро, которое не принадлежит МОД А, иначе МОД А имело бы цикл (что противоречит свойству МОД). Назовем это ребро ''ed<sub>2</sub>''. Тогда ''weight(ed<sub>2</sub>)'' > ''weight(ed<sub>1</sub>)'', так как ''ed<sub>1</sub>'' - ребро наименьшего веса, которое есть в одном графе и нет в другом.
-Итак, в цикле С есть ребра ''ed<sub>1</sub>'' и ''ed<sub>2</sub>'', причем второе большего веса, а первое не лежит в МОД В. Тогда заменим ребро ''ed<sub>2</sub>'' в МОД В на ребро ''ed<sub>1</sub>'' меньшего веса, которое МОД В не принадлежало. Получим МОД меньшего веса, чем МОД В. Тогда В - не МОД, противоречие.
-[[Category:На проверку]]
+[[Category:Решенные задачи]]

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

Версия 01:37, 26 декабря 2014

Навигация

Просмотры

Персональные инструменты

Навигация

Поиск

Инструменты