|
|
| Строка 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:Решенные задачи]] |