Минимальное связующее дерево. уникальный мин край против не уникального доказательства
Итак, у меня есть упражнение, которое я должен доказать или опровергнуть:
1) Если e-минимальное весовое ребро в Связном графе G такое, что не все ребра обязательно различны, то каждое минимальное остовное дерево G содержит e
2) то же, что и 1), но теперь все веса ребер различны.
Итак, интуитивно я понимаю, что для 1) поскольку не все веса ребер различны, то возможно, что вершина имеет путь с ребром e, но также и другое ребро e_1 такое, что если weight (e) = weight (e_1), то существует связующее дерево, которое не содержит ребра e, так как граф связан. В противном случае, если e_1 и e находятся в минимальном остовном дереве, то существует цикл
И для 2) поскольку все веса ребер различны, то, конечно, минимальное остовное дерево будет содержать ребро e, поскольку любой алгоритм всегда будет выбирать меньший путь.
Есть какие-нибудь предложения о том, как доказать эти два факта? индукция? Не знаю, как подойти.
1 ответ:
На самом деле в вашем первом доказательстве, когда вы говорите, что если e и e_1 находятся в G, то есть цикл, это не верно, потому что они минимальные ребра, поэтому не должно быть цикла, и вам нужно включить их обоих в MST, потому что если |E| > 1 и |V| > 2, то они оба должны быть там.
В любом случае, встречный пример для первого-это полный граф со всеми ребрами того же веса, что и e, MST будет содержать только|V / -1 ребер, но вы не включили все остальные ребра того же веса, следовательно, у вас есть противоречие.
Что касается второго, если все ребра различны, то если вы удаляете минимальное ребро и хотите восстановить MST, единственный способ сделать это-добавить ребро, соединяющее 2 непересекающихся набора, которые были разбиты этим ребром с минимальным весом.
Теперь предположим, что вы не удалили это ребро минимального веса, а добавили другое ребро, теперь вы создали цикл, и поскольку все ребра различны, цикл-создание ребро будет больше, чем все они, следовательно, если вы удалите любое предыдущее ребро MST из этого цикла, оно только увеличит размер MST. Это означает, что практически все бывшие ребра MST критичны, когда все ребра имеют различные веса.
Comments