найти все связные подграфы

 
0
 
Алгоритмы
ava
mrgloom | 11.02.2013, 16:14
Необходимо найти все связные подграфы графа.

как это делается? убирается по 1 ребру и проверяется на связность?
Ответы (10)
ava
Фантом | 11.02.2013, 16:11 #
Вы уверены, что нужно найти именно все? А не максимально возможные? А то ведь даже в графе- "треугольнике" из трех попарно связанных вершин искомых подграфов будет 7, а при большем числе вершин для большинства графов рост будет факториальным.
ava
mrgloom | 11.02.2013, 16:23 #
да, это я и имел ввиду, что все максимальные подграфы которые включают все вершины исходного графа.
ava
Фантом | 11.02.2013, 16:31 #
Тогда схема действий такая.
1) Берем какую-то одну вершину графа и добавляем ее в список.
2) Выясняем, какие вершины связаны с ней, добавляем их в тот же список.
3) Для каждой из добавленных в п.2. вершин повторяем ту же процедуру, начиная с п.1. Если новые вершины не обнаруживаются - мы выделили один максимальный подграф.
4) Выкидываем все вершины выделенного подграфа из рассмотрения, берем какую-то вершину графа из оставшихся и снова повторяем все, начиная с п.1. Если вершин графа не осталось - работа закончена, все подграфы выделены.

 
ava
mrgloom | 11.02.2013, 17:32 #
вы не поняли, там 1 связный подграф должен быть, просто разное кол-во рёбер.
ava
Фантом | 11.02.2013, 18:18 #
Цитата (mrgloom @  11.2.2013,  18:32 findReferencedText)
вы не поняли, там 1 связный подграф должен быть, просто разное кол-во рёбер.

Т.е. надо найти минимальное охватывающее дерево? М-да, с терминологией у Вас все как-то совсем печально.

Давайте-ка сделаем так. Перепишите сюда условие задачи, которую Вы пытаетесь решить, дословно. Без сокращений и прочей отсебятины. А там посмотрим, что именно Вам на самом деле нужно.
ava
mrgloom | 12.02.2013, 09:02 #
да, с графами я пока что не работал.


http://forum.vingrad.ru/forum/topic-361629.html
вот тут я пытаюсь сшить панораму.

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

затем я хочу найти подграфы как я описал выше.
и как раз мне надо не минимальное охватывающее дерево, а все варианты подграфов содержащие все вершины и имеющие связность.
затем я планирую каждый граф проверить на геометрические коллизии и затем посчитать сумму корреляций\ кол-во связей и выбрать лучший вариант.
ava
Фантом | 12.02.2013, 09:49 #
Цитата (mrgloom @  12.2.2013,  10:02 findReferencedText)


http://forum.vingrad.ru/forum/topic-361629.html

вот тут я пытаюсь сшить панораму.


Прочитал. Ничего не понял (кроме того, что писал Akina). По-видимому, Вам следует прочитать то, что он написал, и реализовать. 
ava
mrgloom | 12.02.2013, 10:40 #
Я уже написал, что тот метод по ряду причин не подходит.

Сейчас есть метод который работает, но не всегда и поэтому я хочу использовать доп. эвристики чтобы в некоторых случаях можно было улучшить ситуацию.
ava
mrgloom | 17.05.2013, 11:09 #
и (если это будет быстрее) то задачу можно поставить как найти лучшие k остовов в графе.
ava
mrgloom | 17.05.2013, 12:13 #
http://www.boost.org/doc/libs/1_46_1/libs/...nning_tree.html

есть вариант брать несколько раз рэндомно, только непонятно данная реализация будет давать повторы или нет?
Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
advanced
Отправить