Теория графов о связности

Question

Учитывая любой связный и неориентированный граф G(V,E), показывают, что всегда существует вершина v в G которого удаление из графика не влияет на связность G, то есть, существует путь между каждой парой вершины. Покажите O(|E|+|V|) алгоритм времени, чтобы найти такую ​​вершину.

Итак, я начал думать о алгоритме, который бы разрешил эту проблему. Я решил, что хороший способ - использовать поиск по ширине (BFS). Затем вы сможете удалить вершину на уровне самого высокого уровня. Поскольку BFS выполняется с помощью слоев, удаление вершины с самого высокого уровня не должно отключать другие вершины от графика.

Есть ли я на правильном пути? И как мне это доказать?

Answer 1

Позвольте G быть связанным, неориентированным Графом.

Поскольку подключен G, рассмотрим остовное дерево M из G. Это остовное дерево M имеет хотя бы одну вершину, имеющую степень 1 (вершина листа). Поэтому, удалив такую ​​конкретную вершину из G, мы все еще имеем связанный граф, то есть существует путь между каждой парой вершин.

Answer 2

Что касается алгоритма, вы можете запустить DFS или BFS и найти первую вершину без детей. Если такой узел не существует, то у вас должен быть цикл, а затем вы можете вернуть любой узел.

Относительно доказательства. Возможно, по индукции? Вы можете доказать, что если вы добавите вершину с единственным ребром (вершиной листа) к любому связанному, неориентированному графу, вы всегда можете удалить его, не затрагивая возможности подключения.