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

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

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

Кто не соединен между собой?

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


Разобьет задачу на подзадачи меньшего размера. Т.к. ребро перемычка ни в одну в звезду точно не входит (кроме тех, которые состоят из 2 вершин).
А дальше, видимо, что-то типа перебора: начинаем с пары соединенных вершин и пытаемся добавить еще одну, проверяя, получается ли звезда. 

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

Присоединённый файл ( Кол-во скачиваний: 12 )
 graf.png 154,20 Kb

Тогда в такой постановке это, по-видимому, задача о поиске минимального доминирующего множества вершин.

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

Это классическая NP-полная задача, что означает, что точного эффективного решения её не существует (точнее, не найдено до сих пор).

Следовательно, решать её надо или перебором, или каким-либо приближённым алгоритмом, или как-нибудь ещё.

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

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

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

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

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

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

По поводу приближённых алгоритмов - википедия говорит следующее:



Таким образом, приближённый алгоритм выглядит таким образом: пока мы не покрыли все вершины графа, выбрать вершину максимальной степени, добавить её в ответ и удалить из графа эту вершину вместе со всеми её соседями. Тем самым мы получим ответ не более чем в 1 + ln s раз хуже, чем оптимальный (где s - максимальная степень вершины в графе).

Лучших приближённых полиномиальных алгоритмов (т.е. таких, которые гарантируют константу лучшую, чем 1 + ln s), если верить википедии, не существует.

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