Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Разбиение графа на подграфы

Автор: sena 31.10.2011, 18:41

Здравствуйте! Вот бьюсь над одной задачей по разбиению графа на подграфы. Заключается она в следующем:  Имеется неориентированный граф (около 10000 вершин).  Его необходимо разбить на подграфы, которые имеют ограничения: 1. Вершины подграфов не должны пересекаться. 2. Каждый подграф должен иметь топологию типа ЗВЕЗДА. Количество вершин в подграфах не обязательно должно быть одинаковым. 3. Количество подграфов должно быть минимальным из всевозможных комбинаций.

Автор: Earnest 1.11.2011, 09:04

Что такое топология "Звезда"? Возможно, стоит начать с поиска ребер-перемычек, т.е. ребер, удаление которых увеличивает число компонент связности в графе.

Автор: sena 2.11.2011, 10:02

Звезда это когда с одним узлом соединены все остальные, но не соединены между собой. А что даст поиск рёбер-перемычек?

Автор: Earnest 2.11.2011, 10:43

Цитата(sena @  2.11.2011,  11:02 ) но не соединены между собой Кто не соединен между собой? Задача как-то неполно поставлена. Произвольный граф вовсе не обязан содержать такие компоненты, и уж точно не обязан из них состоять (т.е. могут быть вершины, которые ни принадлежат ни одной компоненте-звезде). Или надо сказать, что компоненты не обязаны включать все вершины, или определить минимальный размер компоненты = 1. Кстати, одно ребро (две соединенные вершины) - это звезда или нет? Цитата(sena @  2.11.2011,  11:02 ) А что даст поиск рёбер-перемычек?  Разобьет задачу на подзадачи меньшего размера. Т.к. ребро перемычка ни в одну в звезду точно не входит (кроме тех, которые состоят из 2 вершин). А дальше, видимо, что-то типа перебора: начинаем с пары соединенных вершин и пытаемся добавить еще одну, проверяя, получается ли звезда.

Автор: sena 2.11.2011, 21:08

к примеру вот этот граф имеет такое оптимальное разбиение

Автор: maxdiver 2.11.2011, 22:38

Тогда в такой постановке это, по-видимому, задача о поиске минимального доминирующего множества вершин. Т.е. требуется найти такое множество вершин, что все остальные вершины являются соседями выбранных. (Иными словами, доминирующее множество -  это центры "звёзд"). Это классическая NP-полная задача, что означает, что точного эффективного решения её не существует (точнее, не найдено до сих пор). Следовательно, решать её надо или перебором, или каким-либо приближённым алгоритмом, или как-нибудь ещё.

Автор: sena 3.11.2011, 09:47

Я понял! Просто у меня перебор включает такое количество комбинации при 10 тысячах узлов, что, я думаю, современная вычислительная техника не в состоянии будет справиться с решением. Может всё-таки есть какой-то алгоритм?

Автор: maxdiver 6.11.2011, 18:06

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

Автор: sena 7.11.2011, 19:03

Можно выразиться, что не на подграфы, а на части, где один узел центральный и другие к нему присоединены. А удалять можно какие угодно рёбра, главное, чтобы разбиение было минимальным. Я просто не понимаю как тут более оптимально объяснить????

Автор: maxdiver 8.11.2011, 12:07

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

Автор: sena 9.11.2011, 14:59

Как я теперь понимаю, точно решить не возможно, мне хоть приблизительный бы.

Автор: maxdiver 10.11.2011, 19:39

По поводу приближённых алгоритмов - http://en.wikipedia.org/wiki/Dominating_set говорит следующее: Цитата The approximability of set covering is also well understood: a logarithmic approximation factor can be found by using a http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm, and finding a sublogarithmic approximation factor is NP-hard. More specifically, the greedy algorithm provides a factor 1 + log |V| approximation of a minimum dominating set, and Raz & Safra (1997) show that no algorithm can achieve an approximation factor better than c log |V| for some c > 0 unless P = NP. Таким образом, приближённый алгоритм выглядит таким образом: пока мы не покрыли все вершины графа, выбрать вершину максимальной степени, добавить её в ответ и удалить из графа эту вершину вместе со всеми её соседями. Тем самым мы получим ответ не более чем в 1 + ln s раз хуже, чем оптимальный (где s - максимальная степень вершины в графе). Лучших приближённых полиномиальных алгоритмов (т.е. таких, которые гарантируют константу лучшую, чем 1 + ln s), если верить википедии, не существует.

Автор: sena 10.11.2011, 20:21

Ладно, тогда. Спасибо большое за помощь! Попробую что-нибудь с этим сделать.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)