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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 17.10.2010, 10:26
Новичок

Отправить личное сообщение для Bonus Посмотреть профиль Найти все сообщения от Bonus
 
Регистрация: 17.10.2010
Сообщений: 10

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

Ближайший аналог - это разбиение стекла. Представьте, что рисунок трещин на стекле - это граф. Нужно разбить это стекло на осколки (минимальные циклы).

Эту операцию придется выполнять несколько раз в секунду, поэтому алгоритм требователен ко времени выполнения.
  #2  
Старый 17.10.2010, 12:32
гость

 
Сообщений: n/a

что значит минимальный цикл? это из какой-то статьи/книжки (какой?) или вы сами придумали?

> Ближайший аналог - это разбиение стекла. Представьте, что рисунок трещин на стекле - это граф. Нужно разбить это стекло на осколки (минимальные циклы).
Ну, дык, нарисуйте граф на плоскости и его грани (faces) и будут этими осколками. А если граф не планарен, я не вижу как ваша аналогия тогда работает.
  #3  
Старый 17.10.2010, 12:34
гость

 
Сообщений: n/a

>Эту операцию придется выполнять несколько раз в секунду, поэтому алгоритм требователен ко времени выполнения.

без указания примерных характеристик графов это ваше требование про несколько QPS ровным счетом ничего не значит
  #4  
Старый 17.10.2010, 12:42
Новичок

Отправить личное сообщение для Bonus Посмотреть профиль Найти все сообщения от Bonus
 
Регистрация: 17.10.2010
Сообщений: 10

Сообщение от гость Посмотреть сообщение
что значит минимальный цикл? это из какой-то статьи/книжки (какой?) или вы сами придумали?

Я имею ввиду цикл, с минимальной длиной (кратчайший путь). Или если хотите - цикл, в котором нет внутренних ребер.

> Ближайший аналог - это разбиение стекла. Представьте, что рисунок трещин на стекле - это граф. Нужно разбить это стекло на осколки (минимальные циклы).
Ну, дык, нарисуйте граф на плоскости и его грани (faces) и будут этими осколками. А если граф не планарен, я не вижу как ваша аналогия тогда работает.
И что? Как мне разделить этот граф на отдельные графы?

Сообщение от гость Посмотреть сообщение
>Эту операцию придется выполнять несколько раз в секунду, поэтому алгоритм требователен ко времени выполнения.

без указания примерных характеристик графов это ваше требование про несколько QPS ровным счетом ничего не значит
Исходный граф имеет в среднем 40 ребер. Макс. 80-90, но таких не много.
Ребра гарантировано не пересекаются. Граф планарен. Также гарантировано, что исходный граф замкнут, а внутренние ребра ВСЕГДА делят его как минимум на 2 цикла.
  #5  
Старый 17.10.2010, 12:45
гость

 
Сообщений: n/a

Сообщение от Bonus Посмотреть сообщение
И что? Как мне разделить этот граф на отдельные графы?
каждая грань и будет отдельным подграфом.
  #6  
Старый 17.10.2010, 12:48
Новичок

Отправить личное сообщение для Bonus Посмотреть профиль Найти все сообщения от Bonus
 
Регистрация: 17.10.2010
Сообщений: 10

Сообщение от гость Посмотреть сообщение
каждая грань и будет отдельным подграфом.
"грань" - это внешнее ребро? а дальше что? искать минимальный путь от одной точки этой грани до другой? насколько быстро это будет работать если каждый раз придется искать кратчайший путь?
  #7  
Старый 17.10.2010, 12:51
гость

 
Сообщений: n/a

грань - это список ребер, замкнутый путь в графе.

мы вообще об одном и том же с вами щас говорим??? я про faces в graph planar embedding'ах.
  #8  
Старый 17.10.2010, 12:53
гость

 
Сообщений: n/a

Сообщение от Bonus Посмотреть сообщение
насколько быстро это будет работать
я бы не переживал. граф на плоскости рисуется где-то за квадрат от числа не ребер даже, а вершин. будете их тыщями решать
  #9  
Старый 17.10.2010, 12:57
Новичок

Отправить личное сообщение для Bonus Посмотреть профиль Найти все сообщения от Bonus
 
Регистрация: 17.10.2010
Сообщений: 10

Сообщение от гость Посмотреть сообщение
грань - это список ребер, замкнутый путь в графе.

мы вообще об одном и том же с вами щас говорим??? я про faces в graph planar embedding'ах.
сори, я не спец в графах. теперь понял - грань - это область, ограниченная рёбрами в плоском графе, и не содержащая внутри себя вершин и рёбер графа (wikipedia).

видимо мне нужно найти все грани и разделить на них исходный граф?
как это сделать за мин. время?
  #10  
Старый 17.10.2010, 13:05
гость

 
Сообщений: n/a

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

Цитата:
как это сделать за мин. время?
Каким-нибудь алгоритмом для рисования графов на плоскости. С нуля писать категорически не советую, я как-то смотрел на один алгоритм - гемор еще тот. Самому как-то мне не приходилось рисовать графы (ну не считая старых добрых пружинок), так что... ищите в гугле. Ключевое слово: planar graph embedding. (а то graph drawing уж больно общее, включает и другие, "эстетические" виды рисования, например, пружинки, где могут пересекаться ребра - это вам совсем не надо). Возможно в библиотеках boost graph library, CGAL и LEDA есть готовые реализации, посмотрите.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Конкурс для программистов - предгамильтоновы циклы Zealint Новости 5 31.10.2010 17:48
граф в win32 гость Графы 11 08.04.2009 03:07
Непересекающиеся циклы гость Графы 1 18.09.2008 15:50
все циклы в неоринтированном графе гость Графы 1 26.02.2008 13:40
минимальные циклы графа Alx Графы 2 03.12.2007 15:08