Алгоритм для независимого множества графа?

Есть ли алгоритм для нахождения всех независимых множеств ориентированного графа? Из того, что я прочитал, независимый набор представляет собой набор, образованный узлами, которые не смежны. enter image description here Алгоритм для независимого множества графа?

Итак, для этого примера у меня было бы {1} {2} {1,3} Итак, как можно найти все из них, я думаю о чем-то рекурсивном, но я действительно не знаю алгоритма, если бы кто-то мог указать мне в правильном направлении, это было бы очень признательно!

Спасибо!

источник

2013-11-18 JackRobinson

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

источник

2013-11-18 17:01:03

Хорошая идея, но проблема в том, что я хочу ВСЕ наборы, и я не могу найти алгоритм для всех клик, только для максимальных, любых других идей? – JackRobinson

Идея такая же, что вы просто не оптимизируете. Как я уже упоминал в своем ответе, решение этой проблемы экспоненциально, поэтому почти любое решение должно быть примерно таким же хорошим, как вы можете. –

Если вы найдете все максимальные клики, вы нашли все клики. – saeedgnu

Помимо дополнения и поиска кликов, я также могу подумать о «Раскраске графов», вы как-то окрашиваете вершины, чтобы две соседние вершины не имели одинакового цвета (вы можете сделать это с помощью очень простого эвристического алгоритма, такого как SL = Smallest Last), а затем выберите вершины в каждом цвете как подмножество (как максимальное независимое подмножество).

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

источник

2013-11-18 18:26:20 saeedgnu

Алгоритм Брон-Кербоша обычно используется для этой проблемы, см. Wikipedia article для описания и псевдокода, которые могут быть превращены в полезную программу без особых проблем. Размер вывода в наихудшем случае является экспоненциальным по числу вершин, но грубая сила всегда будет экспоненциальной, а BK будет полиномиальной, если выход является многочленом. Другими словами, если вы знаете, что результат будет разумным, BK будет производить его в разумные сроки. Это активная область исследований, и есть ряд других алгоритмов, которые делают то же самое с различной эффективностью в зависимости от типа и размера графика. Существуют приложения в нескольких областях, в частности генетики.

источник

2013-11-29 02:04:33 RDBury

Хм, Wiki сказал: «Алгоритм Брон-Кербоша не является чувствительным к выходу алгоритмом», поэтому откуда вы получили свое утверждение о том, что «BK будет полиномиальным, если вывод является полиномиальным «? – justhalf

Вы правы, BK не является, в худшем случае, чувствительным к выходу и существуют другие алгоритмы. BK действительно хорошо работает на практике, особенно если вы реализуете оптимизацию, обсуждаемую в статье, и ее относительно легко реализовать. – RDBury

Алгоритм для независимого множества графа?

ответ

Смежные вопросы