Связность

[kl]

Привет.
Такой трабл... Есть сетевой граф. Известно, что он планарен. Я хочу к нему применить алгоритм, который требует, чтобы граф еще и был двусвязным. Следовательно надо добавить временные ребра, для обеспечения этого условия. Проблема в том, что граф должен остаться планарным.
Самое простое, это добавить ребро, соединяющее начало и конец, но не хочется т.к. это нарушит некоторые важные свойства.
Короче, как добавить минимальное кол-во ребер, для увеличения связности графа ???

[Demo_S]

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

[kl]

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

[Demo_S]

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

[kl]

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

[iskander]

А что если сделать из графа максимальный планарный граф? Т.е. превратить его в граф. целиком состоящий из "треугольных циклов"? В принципе, нам даже хватит условия, чтобы из каждой вершины исходило по два ребра, а не по три. Соотвествтенно, возникает вопрос: есть ли у тебя в графе вершины из которых исходит более трех ребер? Если нет, то всегда можно соеденить две вершины, смежных данной. А вот если да... Тогда нужно к каждой вершине где одно вход. ребро искать такую, где остается менее трех... Ведь тогда у нас получается что? Блин. Все равно лажа получается... В общем, в случае, когда кол-во ребер из каждой вершины неограничено еще подумать надо... Буду думать...
Мультиграфы я в рассмотрение не брал...

[iskander]

А вот еще идейка:
у тебя есть вершина с одним входящим ребром. Значит тебе нужно, условно говоряч, достроить треугольник с этим ребром. Как это сделать? По-моему, надежнее всего -- высчитать расстояния расстояния до всех ребере, смежных данному и образующих с ним острый угол.
1. Такие есть. Тогда просто ищешь ребро, кторое ближе и достраиваешь треугольник (по углу и двум сторонам)
2. Таких нет. Тогда наоборот берешь и достраиваешь его с тем ребром, до продолжения которого расстояние максимально.
Надеюсь, смог помочь. И помощь не опоздала. :-)

[kl]

Дело в том, что мне то как раз и нужен максимально планарный граф. Для его получения используется метод канонической триангуляции. Этот термин часто встречается в Сети, найти описание не трудно. Проблема в том, что алгоритмы триангуляции уже предполагают наличие двусвязного графа.
Кстати, есть известная теорема, которая утверждает, что граф планарен тогда и только тогда, когда все его компоненты двусвязности - планарны. Я написал программку, которая анализирует граф на двусвязность, находит точки сочленения и блоки. Алгоритм весьма прост, основывается на анализе DFS-дерева (DFS - Depth-First Search - Поиск в глубину). Вот я и думаю удастся ли потом по отдельности уложить все блоки на плоскости, а затем совместить по точкам сочленения так, чтобы получилось планарное изображение.

[iskander]

Ну так все верно. Я и предлагаю алгоритм, как устранить односвязнность... Или как там это называется. А раз уже нельзя нарушить связность удаление одной произвольной вершины, то, по-моему, и каноническая триангуляция применима...
Или я что-то не так понимаю? Ведь в принципе для рассчета расстояний тебе и не нужна плосость -- есть два уравнения прямых по двум точкам, а что еще нужно?