Показать полный граф с n вершинами, вес MST меньше или равен минимальному весу цикла, который проходит через все вершины
Я действительно борюсь с этим доказательством и буду очень признателен за подробное объяснение:
Покажите полный граф с n вершинами, вес MST меньше или равен минимальному весу цикла, который проходит через все вершины (также называемый гамильтоновым циклом)?
2 ответа
Поскольку каждая вершина связана со всеми остальными, все перестановки узлов могут составлять действительный гамильтонов цикл. Среди возможных гамильтоновых циклов полного графа давайте выберем один с наименьшей стоимостью.
Для графа N-узлов предположим, что перестановка P узлов v1 v2... vN и множества ребер E, как определено ниже, составляют гамильтонов цикл с наименьшей стоимостью. E = {(v1, v2), (v2, v3),..., (v(N-1), vN), (vN, v1)}
Давайте докажем спорную лемму от противного.
Предположим, что существует MST T с суммой весов, превышающей сумму стоимости всех ребер в E. Назовем эту сумму затрат как cE. Если бы это было так, существовало бы другое дерево T', такое, что сумма его краевых затрат будет равна cE - c(vi, v(i + 1)). По сути, мы могли бы сократить границу между vN и v1 и рассматривать оставшуюся часть гамильтонова цикла с наименьшей стоимостью как дерево. Пока ребро (vN, v1) имеет неотрицательную стоимость, cE - c(vi, v(i + 1)) будет меньше или равно стоимости T, стоимость которой была выше, чем сE. Следовательно, существует конфликт, и наше предположение о существовании такого MST T должно быть неверным.
Обратите внимание, что приведенное выше доказательство будет действительным независимо от того, какое ребро вы отрежете, если оно имеет неотрицательную стоимость.
Предположим, что вес минимального остовного дерева больше, чем гамильтонов цикл, выберите любое ребро в цикле и удалите его, оно станет новым остовным деревом (охватывающим все вершины), которое имеет меньший вес, чем минимальное остовное дерево, поэтому противоречие.