Разделение планарного графа на 2 связных компоненты

[www.ru]

Здравствуйте.

Есть вопрос. Задан планарный граф, со всеми известными характеристиками. Необходимо выяснить, сколькими способами его можно разделить (разрезать) ровно на 2 связных компоненты и как организовать обход этих резов без полного перебора множества разбиений точек на 2 множества.

Спасибо.

[Null]

Определите способ задания графа и определение разреза(чем оно отличается от случая произвольного графа)

[www.ru]

Способ задания графа - обычный: матрица смежности. Насчет разрезов - непонятно, как их задавать. Самый простой путь - расставить на ребрах атрибут "недоступно" для ребер, входящих в рез.

[ИСН]

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

-- Ср, 2013-05-29, 23:15 --

Например, если граф - дерево, то искомых резов ровно столько же, сколько рёбер. Хорошую я оценку нашёл? Нравится? Нет? Почему?

[Sender]

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

[nikvic]

У планарного графа есть планарный же ко-граф, вершины которого суть грани исходного, а рёбра "режут" рёбра исходного.
Если не ошибаюсь, Вам нужно искать все циклы этого ко-графа.