Минимальное остовное дерево: что такое свойство обрезки?

Question

Я проводил много времени за чтением онлайн-презентаций и учебников о свойствах разреза минимального остовного дерева. На самом деле я не понимаю, что это должно иллюстрировать или даже почему это практично. Возможно, это помогает определить, какие ребра добавить к MST, но я не вижу, как это достигается. Мое понимание свойства cut до сих пор состоит в том, что вы разбиваете MST на два произвольных подмножества. Любая помощь здесь? Спасибо!

Answer 1

Разрез связного графа - это минимальный набор ребер, удаление которых разделяет граф на две составляющие (части). Свойство минимального среза говорит о том, что если один из краев среза имеет вес меньше, чем любой другой край среза, то он находится в MST. Чтобы увидеть это, предположим, что существует MST, не содержащий ребра. Если мы добавим ребро в MST, мы получим цикл, который пересекает разрез, по крайней мере, два раза, поэтому мы можем разорвать цикл, удалив другое ребро из MST, тем самым создав новое дерево с меньшим весом, что противоречит минимальности MST.

Answer 2

Есть еще одно свойство, на котором основано это объяснение.

«Для любого разреза, если четное число ребер пересекает разрез, должен быть цикл, пересекающий разрез»

Поскольку MST не содержит циклов, четного числа ребер, пересекающих разрез, не будет.

Доказательство от противного: Предположим, что есть MST, не содержащий ребро с минимальным весом «е». Если мы добавим ребро «e» в MST, мы получим цикл, пересекающий разрез по крайней мере дважды. Мы можем удалить другое ребро с большим весом и разорвать цикл, в результате чего ST будет содержать меньшее ребро взвешивания "e". Это противоречит предположению.

Answer 3

Я хотел бы поделиться тем, что я понимаю о Cut Property, чтобы помочь.Если в моем сообщении есть что улучшить, прокомментируйте ниже, чтобы я мог изменить свой ответ.

Background:

Для упрощения предположим, что в графе G (V, E) сформированы 2 отдельных MST (T1 и T2).Есть ребра, еще не связанные между T1 и T2.

Goal:

Мы хотим показать, что при соединении T1 и T2 вновь созданное дерево также является MST - оптимальным решением.

>> My Understanding of Cut Property:

Среди ребер, еще не соединенных междуT1 и T2, выберите самый легкий край.Добавление его для соединения T1 и T2 делает новый MST - оптимальным решением.

Примечание. При соединении ребра в том же дереве создается цикл.Но дерево не должно содержать цикл