Учитывая подмножество ребер графа G = (V,E), как мы можем проверить, является ли оно допустимым набором разрезов графа или нет? Примечание. Разрез — это разбиение вершин графа на два непересекающихся подмножества. Итак, разрез-множество разреза — это множество ребер, конечные точки которых лежат в разных подмножествах разбиения. Мне интересно найти алгоритм для этой задачи
Алгоритм: для G = (V, E), как определить, является ли набор ребер (e принадлежит E) допустимым набором разрезов графа
Ответы (2)
Простой алгоритм состоит в том, чтобы удалить подозреваемые ребра из графа и посмотреть, можете ли вы все еще добраться от узла удаленного ребра до его аналога. Если еще можно, то это был не полный разрез. Поэтому, если вы удалите E2, у которого были узлы A и D, вы можете использовать поиск в ширину от A и посмотреть, доберетесь ли вы когда-нибудь до D. Он должен быть линейным по требованиям к пространству и сложности, поскольку мы сохраняем все узлы, которые мы посетили, поэтому мы не возвращайтесь и не посещайте любой узел дважды. На этой вики-странице есть несколько хороших изображений, которые могут помочь: http://en.wikipedia.org/wiki/Cut_%28graph_theory%29
person
Josh
schedule
24.04.2011
@Josh Спасибо, одно сомнение, на квадратном графике, могу ли я иметь разрез размером 3 (3 ребра)?
- person justin waugh; 24.04.2011
Я так не думаю. Для этого нужно дважды обрезать одну и ту же кромку.
- person Josh; 24.04.2011
@Josh Работает ли упомянутый вами алгоритм в вышеупомянутом наборе разрезов размера 3, я думаю, он вернет это как действительный набор разрезов, поскольку BFS не может добраться до A от D в ребре E2.
- person justin waugh; 24.04.2011
@Justin: Думаю, ты прав. Вы должны генерировать подозреваемые грани, фактически рисуя «линию» через график, а не пробуя случайное подмножество.
- person Josh; 25.04.2011
@ Джош извините, мне нужно было обсудить с вами, причина была в том, что когда я работал с вашим алгоритмом для случая в квадратном графе, когда я проверял набор разрезов с любыми 3 ребрами, я получаю ответ как эти 3 ребра являются допустимым набором разрезов, когда это не так, например, после удаления этих 3 ребер, если я хочу пройти через bfs к узлу-партнеру, я не могу предположить, что это допустимый набор разрезов в соответствии с алгоритмом.
- person justin waugh; 28.04.2011
Это допустимый набор разрезов, если после удаления этого подмножества ребер он больше не является связным графом.
Если вы запрашиваете алгоритмы, вы должны иметь возможность начать с любого узла и посмотреть, сможете ли вы достичь всех других узлов с помощью поиска в глубину. Если это так, это недопустимый набор разрезов, если нет, то это допустимый набор разрезов.
person
Chris A.
schedule
24.04.2011
Я думаю, что определение набора разрезов не имеет ничего общего со связностью, например, рассмотрим треугольный граф с V = {a, b, c} и E = {ab, bc, ca}. Если удалить подмножество ребер S = {ab,bc}, то мы получим ac left, который все еще связан, но S по-прежнему является допустимым набором разрезов, поскольку он разбивает G на два подмножества вершин {b} и {a,c}.
- person justin waugh; 24.04.2011
@Justin: На самом деле это неправильно. Он не делит G на два подмножества вершин. Вы можете добраться из {b} в {a} через {ab} (который все еще находится в подмножестве). Вы также можете добраться из {b} в {c} через {ac}. Кроме того, посмотрите здесь, и вы увидите, что определение действительно включает разбиение на непересекающиеся подмножества.
- person Chris A.; 24.04.2011
