|
www.ru |
|
|
|
Здравствуйте.
Есть вопрос. Задан планарный граф, со всеми известными характеристиками. Необходимо выяснить, сколькими способами его можно разделить (разрезать) ровно на 2 связных компоненты и как организовать обход этих резов без полного перебора множества разбиений точек на 2 множества.
Спасибо.
|
|
|
|
 |
|
Null |
|
|
|
Определите способ задания графа и определение разреза(чем оно отличается от случая произвольного графа)
|
|
|
|
|
|
www.ru |
|
|
|
Способ задания графа - обычный: матрица смежности. Насчет разрезов - непонятно, как их задавать. Самый простой путь - расставить на ребрах атрибут "недоступно" для ребер, входящих в рез.
|
|
|
|
|
|
ИСН |
|
|
|
Последний раз редактировалось ИСН 29.05.2013, 22:15, всего редактировалось 1 раз.
Теперь - чего Вы хотите. Решение, которое гарантированно короче полного перебора множества разбиений точек на 2 множества? - такого не будет, потому что для полного графа, например, этот перебор как раз и является ответом. Вероятно, Вы хотите решения с какой-то (какой?) верхней оценкой сложности не для всех графов, а хотя бы только для относительно тощих в каком-то (каком?) смысле.
-- Ср, 2013-05-29, 23:15 --
Например, если граф - дерево, то искомых резов ровно столько же, сколько рёбер. Хорошую я оценку нашёл? Нравится? Нет? Почему?
|
|
|
|
|
|
Sender |
|
|
|
Последний раз редактировалось Sender 30.05.2013, 08:04, всего редактировалось 1 раз.
В условии сказано, что решить требуется лишь для планарных графов, так что пример с полным графом не совсем подходит.
Впрочем, можно придумать и планарный граф с экспоненциально большим числом разбиений.
|
|
|
|
|
|
nikvic |
|
|
|
У планарного графа есть планарный же ко-граф, вершины которого суть грани исходного, а рёбра "режут" рёбра исходного.
Если не ошибаюсь, Вам нужно искать все циклы этого ко-графа.
|
|
|
|
|
