MST – Вопрос с циклом длиной 6 или меньше

Во-первых, критика вашей попытки (ваша работа выделена курсивом; мои комментарии выделены жирным шрифтом):

Предположим, от противного, что существует MST группы G, не содержащий ребра e4. Пусть T — MST группы G, не содержащий e4. Учитывая, что существует ровно 3 ребра с весом меньше веса e4, обозначим эти ребра как e1, e2 и e3 в порядке неубывания веса. Рассмотрим удаление e4 из T. Поскольку T — дерево, удаление e4 разъединяет T на два поддерева, обозначаемых как T1 и T2, где e4 изначально соединяло вершины в T1 и T2. Поскольку T является MST, оно должно иметь минимальный общий вес среди всех остовных деревьев G.

Вы не можете удалить e4 из T, поскольку вы уже предположили, что T не содержит e4.

Таким образом, удаление e4 и замена его ребрами e1, e2 и e3 (которые легче, чем e4) должно привести к получению остовного дерева с общим весом меньшим, чем у T.

Это не верно. Каждое остовное дерево с n вершинами имеет n-1 ребер. Если вы замените одно ребро тремя, связующего дерева больше не будет.

Теперь я перестану рассматривать ваш подход и покажу способ доказать это.

• Пусть G имеет определение выше, и пусть T — MST группы G.
• Пусть e1, e2, e3, e4, ... — ребра в порядке возрастания веса.
• Пусть (a, b) — концы e4.
• Предположим, e4 не принадлежит T.
• Рассмотрим T U {e4}, граф (не дерево), образованный включением e4 в ребра T. Поскольку T является MST, T содержит путь между каждой парой вершин, в частности, он должен иметь путь между a и б. Этот путь вместе с e4 образует цикл в T U {e4}. Поскольку все ребра находятся в E, этот цикл также должен существовать в G и, следовательно, иметь длину >= 6.
• Это означает, что в этом цикле есть как минимум 5 других ребер. Поскольку в E только три ребра меньше e4, то хотя бы два из них должны быть больше.
• Сформируйте T' из T U {e4}, удалив из цикла одно из более тяжелых ребер.
• Тогда T' — остовное дерево с меньшим общим весом, что является противоречием.

Вы потеряли меня в разделе «Рассмотрим возможность удаления e4 из T», потому что вы уже сказали: «Пусть T будет MST G, который не содержит e4», поэтому вы не можете удалить e4 из T.

Доказательство в этом направлении будет выглядеть следующим образом:

Предположим, что существует MST T группы G, не содержащий e4.

Если бы мы добавили к этому дереву e4, это обязательно создало бы цикл.

Этот цикл не должен содержать ребер с весом > e4, потому что если бы это было так, мы могли бы удалить одно из этих ребер, чтобы создать дерево с меньшим весом, и T не было бы MST.

Значит, цикл должен содержать только ребра веса < e4, но таких ребер всего 3, а известно, что в G нет циклов длины < 6, поэтому и этот цикл не может существовать.

Следовательно, MST, не содержащий e4, подразумевает противоречие и не может существовать. Каждый MST содержит e4.