Выделение полного подграфа

[Николай]

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

Заранее спасибо.

P.S. Подскажите заодно, как поместить тему в раздел Дискретной математики?

[Sonic86]

Под полным подграфом понимается клика? т.е. граф, любая пара различных вершин которого связана ребром? Тогда это NP-полная задача, в общем решается перебором. Если $\bar G$ - дополнительный граф к данному $G$, то получаем задачу распознавания максимального независимого множества, которая, ессно, так же NP-полная.
Ну то есть не совсем перебором, для некоторых частных случаев задачу можно решить чуть быстрее (и запрограммировать это, я сам так делал), но в общем случае - перебор.
Книжку можно посмотреть: Гэри, Джонсон Вычислительные машины и труднорешаемые задачи - это по NP-задачам. А по графам много книжек: Кристофидес, Харари, Берхс, Зыков и т.п., я их все не помню, погуглите.

-- Чт авг 12, 2010 14:55:10 --

(Оффтоп)

Николай писал(а):

P.S. Подскажите заодно, как поместить тему в раздел Дискретной математики?

Это может сделать только модератор из соображений типа "сохранить учебный материал" (я точно не знаю). Вам это делать не надо.

[Николай]

для Sonic86
Спасибо большое за советы.


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

-- Пт авг 13, 2010 14:37:39 --

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

[Sonic86]

Николай писал(а):

В итоге мы реализовали некоторый самодельный алгоритм, основанный на переборе. Не думаю, что он оптимален, благо графы, возникающие в нашей задаче, имеют небольшое число вершин. Ну и, конечно, это только черновой вариант, который ещё нужно проверить и по возможности оптимизировать.

Ага, хорошо, что они небольшие. И в принципе алгоритм самому можно придумать и пооптимизировать, он простой.
Я только забыл сказать, что задачу эту если свести к задаче о независимом множестве, то потом ее можно записать в виде задачи БЛП (булева линейного программирования), потом взять релаксированную задачу для $x_j \in \mathbb{R}_+$ и решать ее методами линейного программирования и методом отсечений Гомори. Только метод отсечений неизвестно сколько итераций делает, т.е. там тоже особо много чего не получится. Я сам эти алгоритмы не реализовывал никогда, поэтому не могу даже посоветовать, использовать этот метод при большом количестве вершин в графе или нет. Ну просто знайте, что вот этот метод есть, если что, вдруг пригодится.

[Николай]

Нашёл свою старую тему по двум поводам
1) Нашлась хорошая статья. Правда там она платная, но листинг программы, приведённой в ней, можно найти и бесплатно (я и статью где-то бесплатно скачал, но не могу найти - где Если кому надо - вышлю)

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

[sup]

Минимальность не гарантирована. Простой пример. Полный граф $G$ из 4-х вершин. Ещё одна вершина связана с парой из $G$ и еще одна с другой парой. Всего 6 вершин. Можно разбить на два полных графа, каждый с 3-я вершинами. А жадный алгоритм выдаст 3 графа.

[Николай]

sup в сообщении #407580 писал(а):

Минимальность не гарантирована. Простой пример. Полный граф $G$ из 4-х вершин. Ещё одна вершина связана с парой из $G$ и еще одна с другой парой. Всего 6 вершин. Можно разбить на два полных графа, каждый с 3-я вершинами. А жадный алгоритм выдаст 3 графа.

Это действительно так.

А если такой алгоритм. Предположим, у нас есть исходный граф $G$. Действуем по следующему алгоритму. Выделяем из него полный подграф $g$ (один из возможных), удаляем его вершины из исходного, рассматриваем полученный граф $G/g$ (не знаю, есть такое обозначение или нет). В нём снова выделяем один из возможных и т.д., пока не уберём все вершины.

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

[sup]

Ну, по сути, это просто перебор. Этот вариант всегда есть в запасе
Подграфы вполне можно считать изолированными. Если одна вершина принадлежит нескольким подграфам, то её можно просто выбросить из всех, кроме одного.
А вообще любопытная задача.

[Евгений Машеров]

Один из работающих алгоритмов поиска клики - разбиваем множество поиска на две части - подграфы, включающие вершину Х, и подграфы, её заведомо не включающие.
То есть, выбрав Х, строим два графа - первый состоит из вершин, смежных с Х, второй представляет собой исходный граф без вершины Х (и смежных лишь с ней). Проверяем их на полноту. Если полный граф не получен - ветвимся аналогично на каждом из графов. В худшем случае число их растёт, как степени двойки, но на практике достаточно быстро получаем полный граф, и начинаем отсекать ветви, на которых мощность графа меньше найденного.
Относительно выбора вершины Х определённо не скажу, но если брать с наибольшей степенью, работает не так уж плохо.