| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > Связность |
| Автор: kl 03.07.02, 11:31 |
| Привет. Такой трабл... Есть сетевой граф. Известно, что он планарен. Я хочу к нему применить алгоритм, который требует, чтобы граф еще и был двусвязным. Следовательно надо добавить временные ребра, для обеспечения этого условия. Проблема в том, что граф должен остаться планарным. Самое простое, это добавить ребро, соединяющее начало и конец, но не хочется т.к. это нарушит некоторые важные свойства. Короче, как добавить минимальное кол-во ребер, для увеличения связности графа ??? |
| Автор: Demo_S 03.07.02, 19:52 |
| ы:) самый простой, это удвоить каждое ребро, чтобы было туда и обратно. раз можно расположить одно (тк граф планарный), то можно расположить и обратное, не нарушив планарности:) но это увы не самый оптимальный вариант. |
| Автор: kl 04.07.02, 05:36 |
| Послушай, если граф односвязный, то есть вершина, удаление которой приведет к несвязному графу. Удаление вершины, подразумевает удаление всех инцидентных ребер, неважно сколько их. Поэтому граф останется односвязным... |
| Автор: Demo_S 04.07.02, 12:35 |
| хе, наверное я чет не понял... что есть односвязный граф? я вспомнил насчет сильной, слабой связности, думал оно... |
| Автор: kl 04.07.02, 12:44 |
| Ну почти. Граф - неориентированный, поэтому есть просто связность (она же сильная и слабая). Граф - односвязный, если существует хотя бы одна вершина, удаление которой приведет к несвязному графу (точка сочленения) Просто сколько бы ты к точке сочленения ребер не припаял, её удаление все равно приведет к несвязному графу, т.к. все инцидентные ребра удаляются. Поэтому надо как-то строить "запасные" пути, т.е. ребра, которые будут связывать компоненты графа, при удалении таких вершин. Но как найти минимальное кол-во таких ребер ??? |
| Автор: iskander 25.07.02, 19:04 |
| А что если сделать из графа максимальный планарный граф? Т.е. превратить его в граф. целиком состоящий из "треугольных циклов"? В принципе, нам даже хватит условия, чтобы из каждой вершины исходило по два ребра, а не по три. Соотвествтенно, возникает вопрос: есть ли у тебя в графе вершины из которых исходит более трех ребер? Если нет, то всегда можно соеденить две вершины, смежных данной. А вот если да... Тогда нужно к каждой вершине где одно вход. ребро искать такую, где остается менее трех... Ведь тогда у нас получается что? Блин. Все равно лажа получается... В общем, в случае, когда кол-во ребер из каждой вершины неограничено еще подумать надо... Буду думать... Мультиграфы я в рассмотрение не брал... |
| Автор: iskander 25.07.02, 19:14 |
| А вот еще идейка: у тебя есть вершина с одним входящим ребром. Значит тебе нужно, условно говоряч, достроить треугольник с этим ребром. Как это сделать? По-моему, надежнее всего -- высчитать расстояния расстояния до всех ребере, смежных данному и образующих с ним острый угол. 1. Такие есть. Тогда просто ищешь ребро, кторое ближе и достраиваешь треугольник (по углу и двум сторонам) 2. Таких нет. Тогда наоборот берешь и достраиваешь его с тем ребром, до продолжения которого расстояние максимально. Надеюсь, смог помочь. И помощь не опоздала. :-) |
| Автор: kl 26.07.02, 05:46 |
| Дело в том, что мне то как раз и нужен максимально планарный граф. Для его получения используется метод канонической триангуляции. Этот термин часто встречается в Сети, найти описание не трудно. Проблема в том, что алгоритмы триангуляции уже предполагают наличие двусвязного графа. Кстати, есть известная теорема, которая утверждает, что граф планарен тогда и только тогда, когда все его компоненты двусвязности - планарны. Я написал программку, которая анализирует граф на двусвязность, находит точки сочленения и блоки. Алгоритм весьма прост, основывается на анализе DFS-дерева (DFS - Depth-First Search - Поиск в глубину). Вот я и думаю удастся ли потом по отдельности уложить все блоки на плоскости, а затем совместить по точкам сочленения так, чтобы получилось планарное изображение. |
| Автор: iskander 26.07.02, 06:29 |
| Ну так все верно. Я и предлагаю алгоритм, как устранить односвязнность... Или как там это называется. А раз уже нельзя нарушить связность удаление одной произвольной вершины, то, по-моему, и каноническая триангуляция применима... Или я что-то не так понимаю? Ведь в принципе для рассчета расстояний тебе и не нужна плосость -- есть два уравнения прямых по двум точкам, а что еще нужно? |