Java - Графические критические ссылки

Question

У меня есть график, в котором у меня есть два узла (0 и 6), и мне нужно разрезать наименьшие ребра, чтобы они не были связаны. К примеру, в этом графике

Будучи узлы 0 и 6 наименее края, которые я должен отрезать являются 2-7 и 3-7. Моя идея заключалась в поиске кратчайшего пути между использованием bfs, я нахожу один (0-2-7-6), но тогда я не знаю, как найти другого (0-3-7-6). Даже тогда я понятия не имею, как выбрать края для резки.

Было бы хорошо, если бы кто-нибудь мог дать мне несколько указаний по этому вопросу.

Answer 1

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

Открытие шарнирных узлов из графа в значительной степени решена проблема, и вы можете найти более подробную информацию об этом здесь: http://en.wikipedia.org/wiki/Biconnected_component

Мне кажется, что так, как вы хотели бы подойти к проблеме, как это в целом бы что-то вдоль этих линий:

1. Find all articulation points 
2. Do a bfs from each node and determine articulation points along the path 
3. Split graph at the articulation point, choosing the side with minimal edges 
4. Continue until the two nodes are not connected 

В приведенном выше примере, 7 является единственной точкой сочленения, и поэтому вы бы отсечь края от 7, 2 и 3, так как есть только два ребра между 7 и 0-4 графа и 3 ребра между 7 и 5,6,8 графа.

Существует более строгий алгоритм для этого (читайте: тот, который я не придумал), названный алгоритмом Каргера, который может решить вашу проблему, хотя и в n^2 раза.

Этот алгоритм работает путем эффективного соединения соседних узлов друг с другом до тех пор, пока не будет только два узла, а затем, подсчитав количество ребер, оставшихся между двумя узлами. Количество ребер - это минимальное количество разрезов, необходимых для разделения графика.

То, как вы реализуете алгоритм Каргера в своей проблеме, просто потребует оговорки, что вы всегда должны соединять узлы с двумя узлами, которые хотите разбить. Кроме того, чтобы иметь возможность вернуться назад к исходным краям, которые вам нужно отрезать, вы должны сохранить ссылку на то, к каким узлам принадлежали края.

Там отличная визуализация алгоритма Karger здесь: http://en.wikipedia.org/wiki/Karger%27s_algorithm

Answer 2

То, что вы хотите является мин s-т вырезать. Обычный способ найти один в общем графике - запустить такой алгоритм, как push relabel с источником 0 и приемником 6, который вычисляет min s-t cut как побочный результат вычисления максимального потока.

Алгоритм Каргера находит минимальный разрез, т. Е. Минимизирует по s и t, а также разрезы. Поскольку s и t фиксированы для вас, Карджер не подходит. Вершина сочленения - это вершина, удаление которой отключает график. Вы заинтересованы в удалении ребер, а не в вершинах.