Минимизация количества мостов в графе
Я пытался решить проблему, которая в основном сводится к этому:
Дать набор N узлы пронумерованы от 1 до N и M края где N<10000 а также M<100000,
найти край (и, V) который при добавлении в график — Минимизирует количество мостов в графе.
Если таких ребер много — выведите тот, который имеет низшая лексикографическая ценность.
Что было бы эффективное подход к этой проблеме?
Решение
Я считаю, что эта проблема очень сложная. Вот схема решения, которое я могу придумать:
1) Найти все мосты в графе.
2) Теперь представьте, что мосты — это единственные ребра, которые вы хотите видеть в своем графике. Вы только держите мосты и соединяете все узлы между мостами в больших узлах.
3) Теперь у вас есть дерево. Края — это мосты, узлы — это «большие узлы», которые объединяют узлы из предыдущего графа.
4) Назовем этот лесной граф Т.
5) Соединение любых двух узлов в графе T создает цикл. Любое ребро в цикле не является мостом.
6) Точка 5 подразумевает, что решение найдено путем создания максимально возможного цикла. Вы можете сделать это, просто найдя два узла, которые имеют наибольшее расстояние между ними.
7) Вы можете найти узлы с самым длинным расстоянием на графике. Как обсуждается здесь:
Алгоритм линейного времени для нахождения наибольшего расстояния между двумя узлами в свободном дереве?
Дайте мне знать, если какой-либо пункт требует дальнейшего объяснения.
Другие решения