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

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

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