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