выделить из графа все независимые подграфы

kosh538

Есть связный ориентированный граф. Известно, что из одной вершины (назовем ее корнем) есть путь в любую другую. Нужно выделить из графа все "независимые" подграфы. (независимые - ни из одной вершины одного подграфа нет пути ни в одну вершину другого). Можно даже не все, главное, чтобы эти подграфы покрывали как можно большую часть исходного большого графа. (весь большой граф покрыть не удастся, т.к. из корня есть путь в любую вершину). Кто нибудь знает, существует ли алгоритм для этого?(прямой перебор не считается)

Приветствуются любые комменатрии и предложения.

stat8907907

Есть тривиальное (и по данному условию задачи - правильное) решение. Все вершины загоняем в "первый" "незавимый" подграф. Теперь смотрим: подграфы покрывают весь граф (т.е. условие максимальности есть) и т.к. число подграфов меньше 2, то основное требование независимости тоже выполнено.
Уточни условие, плз.

afony

Если хочется найти нетривиальное решение, то может быть тебе поможет такая идея. Запишем матрицу смежности для этого графа (при этом считаем, что на диагонали стоят 1 - из вершины можно пройти в саму себя). Для каждого из векторов вида (1,0,0,...,0 (0,1,0,...,0..., (0,0,0,...,1) проделываем следующую операцию: применяем к нему матрицу смежности (один или несколько раз) до тех пор, пока количесво ненулевых координат в нем возрастает. Получаем n векторов, по крайней мере один из которых имеет все ненулевые координаты (тот, который соответствует вершине из которой можно пройти во все другие так вот такие векторы не рассматриваем . Теперь наша задача выбрать среди оставшихся систему попарно ортогональных векторов с максимальной суммой количества ненулевых координат в них. Это можно сделать, например, рекурсией: берем какой-нибудь вектор и из нашего набора оставляем лишь те векторы, которые ему ортогональны (т.е. имеют нули на тех местах, где выбранный вектор их не имеет) и с этим поднабором проводим ту же операцию; перебрав все допустимые наборы, находим тот из них, который имеет максимальную сумму количества ненулевых координат. Когда такой набор найден, по нему строим искомые подграфы: k-ый подграф содержит те вершины, которые имеют номера ненулевых координат в k-ом векторе найденного набора.
Надеюсь, мне удалось объяснить алгоритм достаточно внятно, если нет - извини и задавай вопросы. Может, конечно, он тебя не устроит.

FieryRush

Какая-то двусмысленная формулировка у задачи. То ли максимальную площадь покрытия нужно, то ли максимальное количество подграфов. Ты уж определись сначала с целью-то.

kosh538

Скажем так, нужно выделить Р подграфов(независимых, где Р - заданно так, чтобы площадь покрытия была максимальна

kosh538

Спасибо. Похоже, почти то , что нужно.

afony

Пожалуйста. Надеюсь, что помогло.

kosh538

Хочу вернуться опять к этому вопросу. Предложенный алгоритм, конечно, хорош, но он не всегда работает.

На этом рисунке приведен пример графа. Алгоритм, описанный тобой не найдет здесь независимых подграфов, хотя они есть. Это, например, два подграфа (3,6) и (7,8). Минус этого алгоритма в том, что он находит "абсолютно независимые подграфы". То есть, требование, чтобы ни из одной вершины одного подграфа нельзя было попасть ни в одну вершину другого, ПЕРЕВЫПОЛНЕНО Алгоритм находит подграфы, такие, что не существует вершины, такой, в которую можно попасть из обоих подграфов. В данном случае, в вершину 9 можно попасть из обоих подграфов (3,6) и (7,8 хотя они и независимы.
Если есть еще какие-нибудь предложения - буду рад их услышать. Может быть, автор предыдущего алгоритма предложит его модернизацию Или кто-нибудь другой предложит свой способ решения задачи.... Спасибо заранее

stat8907907

Делаем транзитивное замыкание.
2. Забываем про ориентированность.
Опр. Множество вершин графа называется внутренне устойчивым, если ни одна из этих
вершин не связана ребром ни с одной другой.
Опр. Максимальным внутренним устойчивым множеством называется внутренне устойчивое множество максимального размера.
Опр. Числом внутренней устойчивости называется размер максимального внутренне устойчивого множества.
Теперь смотрим на твою задачу. Если мы нашли P независимых подграфов, где P равно числу внутренней устойчивости графа, и выберем из каждого подграфа по одной вершине, то эти вершины в преобразованном графе будут образовывать внутренне устойчивое множество, причем в силу того, что их P - максимальное.
Отсюда сложность алгоритма решения твоей задачи (по крайней мере при одном P) не меньше сложности нахождения максимального внутренне устойчивого множества.
Сложность нахождения максимального внутренне устойчивого множества двойственна к задаче о максимальной клике, т.е. является NP-полной.
Оставить комментарий
Имя или ник:
Комментарий: