Минимизация количества мостов в графе

Я пытался решить проблему, которая в основном сводится к этому:
Дать набор N узлы пронумерованы от 1 до N и M края где N<10000 а также M<100000,
найти край (и, V) который при добавлении в график — Минимизирует количество мостов в графе.
Если таких ребер много — выведите тот, который имеет низшая лексикографическая ценность.
Что было бы эффективное подход к этой проблеме?

4

Решение

Я считаю, что эта проблема очень сложная. Вот схема решения, которое я могу придумать:

1) Найти все мосты в графе.

2) Теперь представьте, что мосты — это единственные ребра, которые вы хотите видеть в своем графике. Вы только держите мосты и соединяете все узлы между мостами в больших узлах.

3) Теперь у вас есть дерево. Края — это мосты, узлы — это «большие узлы», которые объединяют узлы из предыдущего графа.

4) Назовем этот лесной граф Т.

5) Соединение любых двух узлов в графе T создает цикл. Любое ребро в цикле не является мостом.

6) Точка 5 подразумевает, что решение найдено путем создания максимально возможного цикла. Вы можете сделать это, просто найдя два узла, которые имеют наибольшее расстояние между ними.

7) Вы можете найти узлы с самым длинным расстоянием на графике. Как обсуждается здесь:
Алгоритм линейного времени для нахождения наибольшего расстояния между двумя узлами в свободном дереве?

Дайте мне знать, если какой-либо пункт требует дальнейшего объяснения.

8

Другие решения