Доказательство алгоритма обратного удаления
Правильно ли это доказательство, которое представлено на странице википедии https://en.wikipedia.org/wiki/Reverse-delete_algorithm (внизу страницы)?
ПСЕВДОКОД
1 function ReverseDelete(edges[] E)
2 sort E in decreasing order
3 Define an index i ← 0
4 while i < size(E)
5 Define edge ← E[i]
6 delete E[i]
7 if edge.v1 is not connected to edge.v2
8 E[i] ← edge
9 i ← i + 1
10 return edges[] E
Доказательство состоит из двух частей. Во-первых, доказано, что ребра, которые остаются после применения алгоритма, образуют остовное дерево. Во-вторых, доказано, что остовное дерево имеет минимальный вес.
Остовное дерево
Оставшийся подграф (g), созданный алгоритмом, не отключается, так как алгоритм проверяет это в строке 7. Реализуемый подграф не может содержать цикл, поскольку, если это произойдет, то при движении по краям мы встретим максимальное ребро в цикле, и мы удалили бы это ребро. Так что g должно быть остовным деревом основного графа G.
Минимальность
Покажем, что следующее утверждение P верно по индукции: если F - множество ребер, оставшихся в конце цикла while, то существует некоторое минимальное остовное дерево, которое (его ребра) является подмножеством F.
Очевидно, что P выполняется до начала цикла while. поскольку взвешенный связный граф всегда имеет минимальное остовное дерево, а поскольку F содержит все ребра графа, то это минимальное остовное дерево должно быть подмножеством F.
Теперь предположим, что P истинно для некоторого неконечного множества ребер F, и пусть T будет минимальным остовным деревом, которое содержится в F. мы должны показать, что после удаления ребра e в алгоритме существует некоторое (возможно, другое) остовное дерево T', которое является подмножеством F.
если следующее удаленное ребро e не принадлежит T, то T=T'является подмножеством F, и P имеет место.,
в противном случае, если e принадлежит T: сначала обратите внимание, что алгоритм удаляет только ребра, которые не вызывают несвязности в F. так что е не вызывает отключение. Но удаление e вызывает несвязность в дереве T (так как это член T) . предположим, что e разделяет T на подграфы t1 и t2 . Поскольку весь граф связывается после удаления e, тогда должен существовать путь между t1 и t2 (кроме e), поэтому в F должен существовать цикл C (до удаления e). теперь в этом цикле должно быть другое ребро (назовем его f), которого нет в T, но оно находится в F (поскольку, если бы все ребра цикла находились в дереве T, то это больше не было бы деревом). Теперь мы утверждаем, что T' = T - e + f - минимальное остовное дерево, которое является подмножеством F.
Сначала мы докажем, что T'является остовным деревом. мы знаем, удалив ребро в дереве и добавив другое ребро, которое не вызывает цикл, мы получаем другое дерево с такими же вершинами. Так как T был остовным деревом, значит, T'тоже должно быть остовным деревом. поскольку добавление " f " не вызывает циклов, так как "e" удаляется (обратите внимание, что дерево T содержит все вершины графа).
во-вторых, мы докажем, что T'- минимальное остовное дерево. у нас есть три случая для ребер "е" и " f ". вес - весовая функция.
wt (f) wt( f) > wt( e) это тоже невозможно. с тех пор, когда мы проходим ребра в порядке убывания веса ребер, мы должны сначала увидеть " f ". поскольку у нас есть цикл C, поэтому удаление " f " не приведет к разъединению в F., поэтому алгоритм удалил бы его из F раньше. поэтому " f " не существует в F, что невозможно (мы доказали, что f существует на шаге 4 . поэтому wt(f) = wt(e), поэтому T'также является минимальным остовным деревом. так что снова P держит. поэтому P выполняется, когда цикл while завершен (то есть, когда мы увидели все ребра), и мы доказали, что в конце F становится остовным деревом, и мы знаем, что F имеет минимальное остовное дерево в качестве своего подмножества. поэтому F должно быть само минимальным остовным деревом. РЕДАКТИРОВАТЬ на самом деле у меня есть проблема с параграфом "во-первых, мы докажем, что T'является остовным деревом", а часть ", которую мы доказали в конце F, становится остовным деревом, и мы знаем, что F имеет минимальное остовное дерево в качестве своего подмножества. поэтому F должно быть само минимальное остовное дерево