Найти набор разрезов на графике

Возможный дубликат:
Алгоритм: для G = (V,E), как определить, является ли набор ребер (e принадлежит E) допустимым набором разрезов графа

Подмножество S ребер графа G = (V,E), как можно проверить, является ли оно действительным набором разрезов графа или нет? Примечание. Разрез — это разбиение вершин графа на два непересекающихся подмножества. Итак, разрез-множество разреза — это множество ребер, конечные точки которых лежат в разных подмножествах разбиения. Мне интересно найти алгоритм для этой задачи


graph algorithm cut
person justin waugh    schedule 26.04.2011    source источник
comment
@Moron: этот предыдущий алгоритм работает не во всех случаях. В этом посте я объяснил, что алгоритм вернет 3 ребра квадрата как допустимый набор разрезов, когда это не так.   -  person justin waugh    schedule 26.04.2011
comment
Тогда почему вы приняли ответ там? Отмените его, отредактируйте вопрос, указав, почему ответы не работают, и прокомментируйте неверный ответ.   -  person    schedule 26.04.2011

Ответы (1)


arrow_upward
0
arrow_downward

Другими словами, вы хотите определить, существует ли маркировка V -> {0, 1} такая, что ребра в S имеют конечные точки с разными метками, а ребра в E - S имеют конечные точки с одинаковыми метками. Такая разметка, если она существует, всегда может быть построена с помощью следующей процедуры.

Траверс G (скажем, в глубину, но это не имеет большого значения). Пометьте корни обхода произвольно. Каждый раз, когда вы обрабатываете ребро e из помеченного узла u в какой-либо другой узел v, пометьте v меткой u, если e не в S, и меткой, противоположной метке u, если e в S. Если v уже имеет другую метку, то S не обрезанный набор. В противном случае, если обход завершается без инцидентов, то S является секущим множеством.

person qrqwe    schedule 26.04.2011