Подсказки по доказательству узкого места узлы существуют в неориентированном графе во время поиска кратчайшего пути

Question

Учитывая, что у меня есть граф G = (V, E), если расстояние от s до t строго больше, чем | V |/2, должно быть узел узкого места на графике. Узлом узкого места является узел, который определяется как: при удалении s и t больше не будут связаны.

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

Любые намеки на то, чтобы доказать это, используя прямое доказательство, докажите противоречие или принцип с голубями?

Answer 1

Доказательство от противного:

Пусть s и т иметь минимальный путь P1 длины | P1 | > | v |/2. Предполагая, что в P1 нет узла узкого места, означает, что существует альтернативный, непересекающийся путь P2 между s и t (разделяющий только узлы s и t). Поскольку P1 имеет кратчайшую длину, мы знаем, что | P2 |> = | P1 |.

Теперь, общее число узлов в графе должно быть по крайней мере, количество узлов в объединении P1 и P2:

| V | > = | P1 | -1 + | P2 | -1 + 2 = | P1 | + | P2 | > = 2 | P1 | > | v |

И это противоречие.