Минимальное остовное дерево. уникальное минимальное ребро против неуникального доказательства

Итак, у меня есть упражнение, которое я должен доказать или опровергнуть:

1) если e - ребро минимального веса в связном графе G такое, что не все ребра обязательно различны, то каждое минимальное остовное дерево графа G содержит e

2) То же, что и 1), но теперь веса всех ребер различны.

Хорошо, так интуитивно я понимаю, что для 1), поскольку не все веса ребер различны, тогда возможно, что у вершины есть путь с ребром e, но также есть другое ребро e_1 такое, что если weight (e) = weight (e_1), то существует остовное дерево, которое не содержит ребра e, поскольку граф связен. В противном случае, если и e_1, и e находятся в минимальном остовном дереве, то существует цикл

и для 2) поскольку веса всех ребер различны, то, конечно, минимальное остовное дерево будет содержать ребро e, поскольку любой алгоритм всегда будет выбирать меньший путь.

Есть какие-нибудь предложения о том, как доказать эти два? индукция? Не знаю, как подойти.


graph algorithm tree minimum-spanning-tree proof
person john    schedule 01.10.2015    source источник
comment
Чтобы что-то опровергнуть, достаточно привести контрпример. Найти его для (1) должно быть достаточно легко. Доказательство (2) более сложное. Я считаю, что хороший способ заключается в доказательстве от противного: предположим, что существует некоторый граф G, единственное ребро минимального веса которого не входит ни в один MST (помните, что их может быть больше одного (если вы не докажете иное)). Если вы можете показать, как преобразовать каждое из этих минимальных остовных деревьев в остовные деревья еще меньшего веса, то вы показали противоречие, то есть уникальное ребро с минимальным весом должно быть в каждом MST каждого графа.   -  person j_random_hacker    schedule 01.10.2015
comment
@j_random_hacker теперь, когда я думаю об этом, не будет ли 1) опровергнут только в том случае, если граф не содержит такую ​​вершину, что единственный путь, соединяющий его с другой вершиной, - это e?   -  person john    schedule 01.10.2015
comment
Когда в исходном вопросе вы говорите, что не все ребра обязательно различны, вы имеете в виду, что не все ребра обязательно имеют разные веса, верно? Конечно, каждое ребро имеет отличную идентичность от любого другого ребра.   -  person j_random_hacker    schedule 02.10.2015
comment
@j_random_hacker, неважно, я неправильно подумал об этом вопросе ... поэтому утверждалось, что, как правило, все минимальные остовные деревья с минимальным ребром e * (не обязательно разные) будут содержать e, и я просто опровергаю это дерево с 3 вершинами, все связанные друг с другом с таким же весом.   -  person john    schedule 02.10.2015

Ответы (1)


arrow_upward
0
arrow_downward

На самом деле в вашем первом доказательстве, когда вы говорите, что если и e, и e_1 находятся в G, то есть цикл, это неверно, потому что они минимальные ребра, поэтому цикла не должно быть, и вам нужно включить их обоих в MST, потому что если | E | > 1 и | V | > 2 тогда они оба должны быть там.

В любом случае, контрпример для первого - это полный граф со всеми ребрами того же веса, что и e, MST будет содержать только | V | -1 ребер, но вы не включили все остальные ребра того же веса, следовательно, вы пришли к противоречию.

Что касается второго, если все ребра различны, то если вы удалите минимальное ребро и захотите восстановить MST, единственный способ сделать это - добавить ребро, соединяющее 2 непересекающихся набора, которые были разбиты этим кромка минимального веса.

Теперь предположим, что вы не удалили это ребро с минимальным весом и добавили другое ребро, теперь вы создали цикл, и, поскольку все ребра различны, ребро, создающее цикл, будет больше, чем все они, следовательно, если вы Удалите из этого цикла любое бывшее ребро MST, это только увеличит размер MST. Это означает, что почти все бывшие ребра MST критичны, когда все ребра имеют разные веса.

person Pavel    schedule 02.10.2015