уникальное минимальное остовное дерево, достаточные и необходимые условия

Question

Для получения графа G, которые являются достаточными и необходимыми условиями, так что этот граф имеет уникальное минимальное остовное дерево? Кроме того, как я могу проделать эти условия?

До сих пор я нашел, что эти условия являются:

1) Для каждого раздела V (G) на два подмножества, минимальный вес край с одной конечной точки в каждом подмножестве является уникальным.

2) Край максимального веса в любом цикле G уникален.

Но я не уверен, что это правильно. Даже если это правильно, я не могу доказать его правильность.

Answer 1

Это неверно, потому что по крайней мере первое условие не требуется. Доказательство проводится контрпримером (source).

Take G быть любое дерево, где все краевые веса 1. Тогда G имеет уникальный MST (сам по себе), но любой раздел с более чем одним ребром пересечения имеет несколько минимальных ребер веса.

---

EDIT:

В ответ на ваш вопрос модифицированном ...

Существует хорошо известная достаточно (но не обязательно) условие единственности MST:

Если вес каждого ребра в связанном графе различен, то граф содержит ровно одно (единственное) минимальное остовное дерево.

Доказательство следующим образом (source):

Ради противоречия, предположим, что существуют два различных MSTS из G, скажем T1 и T2. Пусть e = v-w - край минимального веса G, который находится в , один из T1 или T2, но не тот и другой. Предположим, что e находится в T1. Добавление e к T2 создает цикл C. В C есть, по крайней мере, один ребро, скажем f, то есть не в T1 (в противном случае T1 будет циклическим). По нашему выбору e, w (e) ≤ w (f). Поскольку все веса ребер различны, w (e) < w (f). Теперь , заменяющий f на e в T2, дает новое остовное дерево с весом менее , чем у T2 (что противоречит минимальности T2).

Однако, в отношении «достаточные и необходимые» условия единственности MST, я не верю, как известно, существуют.