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