Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.142.12.240] |
|
Сообщ.
#1
,
|
|
|
Привет.
Такой трабл... Есть сетевой граф. Известно, что он планарен. Я хочу к нему применить алгоритм, который требует, чтобы граф еще и был двусвязным. Следовательно надо добавить временные ребра, для обеспечения этого условия. Проблема в том, что граф должен остаться планарным. Самое простое, это добавить ребро, соединяющее начало и конец, но не хочется т.к. это нарушит некоторые важные свойства. Короче, как добавить минимальное кол-во ребер, для увеличения связности графа ??? |
Сообщ.
#2
,
|
|
|
ы:) самый простой, это удвоить каждое ребро, чтобы было туда и обратно. раз можно расположить одно (тк граф планарный), то можно расположить и обратное, не нарушив планарности:)
но это увы не самый оптимальный вариант. |
Сообщ.
#3
,
|
|
|
Послушай, если граф односвязный, то есть вершина, удаление которой приведет к несвязному графу. Удаление вершины, подразумевает удаление всех инцидентных ребер, неважно сколько их. Поэтому граф останется односвязным...
|
Сообщ.
#4
,
|
|
|
хе, наверное я чет не понял...
что есть односвязный граф? я вспомнил насчет сильной, слабой связности, думал оно... |
Сообщ.
#5
,
|
|
|
Ну почти. Граф - неориентированный, поэтому есть просто связность (она же сильная и слабая).
Граф - односвязный, если существует хотя бы одна вершина, удаление которой приведет к несвязному графу (точка сочленения) Просто сколько бы ты к точке сочленения ребер не припаял, её удаление все равно приведет к несвязному графу, т.к. все инцидентные ребра удаляются. Поэтому надо как-то строить "запасные" пути, т.е. ребра, которые будут связывать компоненты графа, при удалении таких вершин. Но как найти минимальное кол-во таких ребер ??? |
Сообщ.
#6
,
|
|
|
А что если сделать из графа максимальный планарный граф? Т.е. превратить его в граф. целиком состоящий из "треугольных циклов"? В принципе, нам даже хватит условия, чтобы из каждой вершины исходило по два ребра, а не по три. Соотвествтенно, возникает вопрос: есть ли у тебя в графе вершины из которых исходит более трех ребер? Если нет, то всегда можно соеденить две вершины, смежных данной. А вот если да... Тогда нужно к каждой вершине где одно вход. ребро искать такую, где остается менее трех... Ведь тогда у нас получается что? Блин. Все равно лажа получается... В общем, в случае, когда кол-во ребер из каждой вершины неограничено еще подумать надо... Буду думать...
Мультиграфы я в рассмотрение не брал... |
Сообщ.
#7
,
|
|
|
А вот еще идейка:
у тебя есть вершина с одним входящим ребром. Значит тебе нужно, условно говоряч, достроить треугольник с этим ребром. Как это сделать? По-моему, надежнее всего -- высчитать расстояния расстояния до всех ребере, смежных данному и образующих с ним острый угол. 1. Такие есть. Тогда просто ищешь ребро, кторое ближе и достраиваешь треугольник (по углу и двум сторонам) 2. Таких нет. Тогда наоборот берешь и достраиваешь его с тем ребром, до продолжения которого расстояние максимально. Надеюсь, смог помочь. И помощь не опоздала. :-) |
Сообщ.
#8
,
|
|
|
Дело в том, что мне то как раз и нужен максимально планарный граф. Для его получения используется метод канонической триангуляции. Этот термин часто встречается в Сети, найти описание не трудно. Проблема в том, что алгоритмы триангуляции уже предполагают наличие двусвязного графа.
Кстати, есть известная теорема, которая утверждает, что граф планарен тогда и только тогда, когда все его компоненты двусвязности - планарны. Я написал программку, которая анализирует граф на двусвязность, находит точки сочленения и блоки. Алгоритм весьма прост, основывается на анализе DFS-дерева (DFS - Depth-First Search - Поиск в глубину). Вот я и думаю удастся ли потом по отдельности уложить все блоки на плоскости, а затем совместить по точкам сочленения так, чтобы получилось планарное изображение. |
Сообщ.
#9
,
|
|
|
Ну так все верно. Я и предлагаю алгоритм, как устранить односвязнность... Или как там это называется. А раз уже нельзя нарушить связность удаление одной произвольной вершины, то, по-моему, и каноническая триангуляция применима...
Или я что-то не так понимаю? Ведь в принципе для рассчета расстояний тебе и не нужна плосость -- есть два уравнения прямых по двум точкам, а что еще нужно? |