Минимальное связующее дерево: что такое свойство Cut?

Question

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

Answer 1

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