Общее минимальное остовное дерево

Question

Я читаю о минимальных остовных деревьях в Кормене и т. Д.Ниже приводится общее минимальное остовное дерево.

Предположим, у нас есть связный неориентированный граф G = (V, E) с весовой функцией w: E-> R, и мы хотим найти минимальный остовдерево для Г. Здесь мы используем жадный подход.Эта жадная стратегия фиксируется следующим «универсальным» алгоритмом, который вырастает минимальное остовное дерево по одному ребру за раз.Алгоритм управляет набором ребер A, поддерживая следующий инвариант цикла.

Перед каждой итерацией A является подмножеством некоторого минимального остовного дерева.

GENERIC-MST(G,w) 
A = NULL
while A is not a spanning tree 
  do find an edge (u, v) that is safe for A 
  A = A ∪ {(u, v)}
end while

return A

Вопросы

1. Что означает автор в инварианте, что «A» является подмножеством некоторого минимального остовного дерева?Что такое «некоторые» в этом утверждении?я учил, что есть только один MST.

2. В вышеприведенном псевдокоде, что автор имеет в виду под "A не является связующим деревом"?то есть как и когда цикл while завершается?

3. В псевдокоде, где «некоторое» минимальное остовное дерево, здесь мое понимание только одно.я прав?

Может кто-нибудь объяснить, пожалуйста, с небольшим примером?

Спасибо!

Answer 1

1. Абсолютно нет.MST не обязательно уникален.Например:

Все ребра имеют одинаковый вес.

u --- v
|     |
|     |
w --- x

На приведенном выше графике есть 4 MST, путем удаления любого ребра.

2. Покрывающее дерево T = (V,e) в G = (V,E) таково, что |e| = |V|-1

3. Нет.

Answer 2

1. Это неверно. Граф может иметь много MST, даже если только два ребра равны.

2. A не является минимальным связующим деревом из-за:

   2.1 Прежде всего A не дерево - оно отключено.

   2.2 Он не охватывает график

   Цикл завершится, когда вышеуказанные условия будут выполнены

3. Правильно будет сказать, что оно находится в некотором MST, поскольку их много.

Answer 3

1. Неправильно согласно @ davin

2. Алгоритм поддерживает инвариант, что у вас есть лес, но лес не будет охватывать график, пока вы не добавите достаточно ребер. Таким образом, вы должны продолжать добавлять ребра, пока ни один из них не станет безопасным (в этот момент цикл прерывается).

3. см. 1.

Answer 4

1. Вы правы, когда говорите, что остовное дерево графа уникально.Но это тот случай, когда все длины ребер графа различны.Как объяснено в ответе выше, граф с равной длиной ребер может иметь много разных остовных деревьев (все они, конечно, имеют одинаковый общий вес)
2. Цикл while существует, когда вы включили все вершины графа в ваше связующее дерево.Для этого вы добавляете проверку в свой цикл while.