Уникальность минимального остовного дерева — различия между версиями
StasFomin (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
| Строка 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: | + | [[Category:На проверку]] |
Версия 10:35, 8 октября 2014
Цыганова Светлана, 974гр
Решение Докажем от противного: пусть у графа есть 2 минимальных остовных дерева - А и В. Тогда существует ребро ed1, которое есть в одном из них, и нет в другом. Тогда из всех ребер, которые есть в А и нет в В и тех, которые есть в В и нет в А выберем ребро наименьшего веса. Оно единственно, так как все ребра попарно различной длины по условию задачи.
Назовем выбранное ребро ed1, и пусть оно принадлежит МОД А, иначе переименуем деревья.
Рассмотрим граф B' = {ed1}U B. Так как В - МОД, и ed1 не лежит в В, то В' содержит цикл (назовем его цикл С). Рассмотрим этот цикл. В этом цикле есть хотя бы одно ребро, которое не принадлежит МОД А, иначе МОД А имело бы цикл (что противоречит свойству МОД). Назовем это ребро ed2. Тогда weight(ed2) > weight(ed1), так как ed1 - ребро наименьшего веса, которое есть в одном графе и нет в другом.
Итак, в цикле С есть ребра ed1 и ed2, причем второе большего веса, а первое не лежит в МОД В. Тогда заменим ребро ed2 в МОД В на ребро ed1 меньшего веса, которое МОД В не принадлежало. Получим МОД меньшего веса, чем МОД В. Тогда В - не МОД, противоречие.