Имеют ли минимальные остовные деревья взвешенного графа одинаковое количество ребер с заданным весом?

Если взвешенный граф $G$ имеет два разных минимальных остовных дерева $T_1 = (V_1, E_1)$ и $T_2 = (V_2, E_2)$ , то верно ли, что для любого ребра $e$ в $E_1$ число ребер в $E_1$ с таким же весом, что и $e$ (включая само $e$ ), равно числу ребер в $E_2$ с таким же весом, как и $e$? Если утверждение верно, то как мы можем доказать это?

Утверждение : Да, это утверждение верно.

Схема доказательства. Пусть $T_1,T_2$ - два минимальных остовных дерева с мультимножествами с ребристым весом $W_1,W_2$ . Предположим , $W_1 \neq W_2$ и обозначим их симметрическую разность с $W = W_1 \mathop{\Delta} W_2$ .

$e \in T_1 \mathop{\Delta} T_2$$w(e) = \min W$$e$$e \in T_1 \mathop{\Delta} T_2$$\min W$$\min W \notin W$$e \in T_1$$T_1$$\min W$$T_2$

Теперь рассмотрим все ребра в , которые также находятся в разрезе , индуцированном в . Если там есть ребро , имеющее тот же вес, что и , обновите , используя вместо ; обратите внимание, что новое дерево все еще является минимальным остовным деревом с тем же мультимножеством веса ребра, что и . Мы повторяем этот аргумент, сужая на два элемента и тем самым удаляя одно ребро из набора кандидатов в на каждом шаге. Таким образом, после конечного числа шагов мы получаем настройку, в которой все ребра в$T_2$$C_{T_1}(e)$$e$$T_1$$e'$$e$$T_1$$e'$$e$$T_1$$W$$e$$T_2 \cap C_{T_1}(e)$(где - обновленная версия) имеют веса, отличные от .$T_1$$w(e)$

Теперь мы всегда можем выбрать , чтобы мы могли поменять местами и ¹, то есть мы можем создать новое связующее дерево$e' \in C_{T_1}(e) \cap T_2$$e$$e'$

$\qquad \displaystyle T_3 = \begin{cases} (T_1 \setminus \{e\}) \cup \{e'\}, &w(e') \lt w(e) \\[.5em] (T_2 \setminus \{e'\}) \cup \{e\}, &w(e') \gt w(e) \end{cases}$

который имеет меньший вес, чем и ; это противоречит выбору качестве минимальных остовных деревьев. Следовательно, .$T_1$$T_2$$T_1,T_2$$W_1 = W_2$

1. Инциденты узла находятся в соединенном путем ; - это уникальное ребро в .$e$$T_2$$P$$e'$$P \cap C_{T_1}(e)$

Вот немного более простой аргумент, который также работает для других матроидов. (Я видел этот вопрос от другого .)

Предположим, что имеет ребер. Без ограничения общности предположим, что весовая функция принимает значения в , поэтому мы имеем разбиение на множества для . Мы можем сделать индукцию по числу непустых и числу вершин в ; для и любого утверждение очевидно.m w [ m ] E E i : = w - 1 ( i ) i ∈ [ m ] j E i n G j = 1 $G$$m$$w$$[m]$$E$$E_i := w^{-1}(i)$$i\in [m]$$j$$E_i$$n$$G$$j=1$$n$

Стандартный факт о том , что матроидах для каждого MST есть линейное продолжение упорядочения , индуцированного так , что жадный алгоритм производит .ш $T$$w$$T$

Чтобы закрыть индукцию, возьмите за наибольшее число, чтобы не было пустым. Установите . Заметьте, что любое линейное расширение помещает каждое ребро в перед любым ребром в . Согласно этому факту, любое MST состоит из остовного леса подграфа, индуцированного и некоторых ребер из . Согласно индуктивной гипотезе, каждая связная компонента имеет одинаковое количество ребер от каждого для . Так как все вариантыE t E ′ = E 1 ∪ ⋯ ∪ E t - 1 w E ′ E t F E ′ E t F E i i < t F E t F $t$$E_t$$E' = E_1 \cup \cdots \cup E_{t-1}$$w$$E'$$E_t$$F$$E'$$E_t$$F$$E_i$$i < t$$F$имеют одинаковый размер, число ребер от необходимое для завершения до связующего дерева, не зависит от выбора и все готово.$E_t$$F$$F$