Я потратил много времени на чтение онлайн-презентаций и учебников о свойствах разреза минимального остовного дерева. Я действительно не понимаю, что он может проиллюстрировать или даже почему это практично. Предположительно, это помогает определить, какие края добавить в MST, но я не вижу, как это достигается. Мое понимание свойства разреза пока что вы разделили MST на два произвольных подмножества. Любая помощь здесь? Спасибо!
Минимальное связующее дерево: что такое свойство Cut?
Ответ 1
Разрез связанного графа является минимальным множеством ребер, удаление которых отделяет граф от двух компонентов (частей). Свойство минимального разреза говорит, что если один из краев разреза имеет вес, меньший любого другого ребра в разрезе, то он находится в MST. Чтобы убедиться в этом, предположим, что MST не содержит ребра. Если мы добавим ребро в MST, мы получим цикл, который пересекает разрез не менее двух раз, поэтому мы можем разбить цикл, удалив другой край из MST, тем самым создавая новое дерево с меньшим весом, тем самым противореча его минимальности MST.
Ответ 2
Я хотел бы поделиться тем, что я понимаю о 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 - оптимальным решением.
Примечание. Соединение ребра в том же дереве создает цикл. Но дерево не должно содержать цикл
Ответ 3
Есть еще одно свойство, на котором основано это объяснение.
"Для любого разреза, если имеется четное количество ребер, пересекающих разрез, должен быть цикл, пересекающий разрез"
Поскольку MST не содержит никакого цикла, не будет четного числа ребер, пересекающих разрез.
Доказательство от противного. Предположим, что существует MST, не содержащее ребро с минимальным весом "е". Если мы добавим ребро "e" в MST, мы получим цикл, пересекающий разрез по крайней мере дважды. Мы можем удалить другое ребро с большим весом и разорвать цикл, в результате чего ST будет содержать меньшее ребро взвешивания "e". Это противоречит предположению.