максимальная клика в графе

[alanta]

Добрый вечер! Это опять я
Мне нужно найти максимальную клику в графе , как это делается?


P.S.

[Dan_Te]

Мне кажется, вы злоупотребляете смайликами.

Что такое "клика"?

[alanta]

Больше не буду смайличать

Из учебника: Клика- это максимальный полный подграф.

У нас ещё небыло графов, так что я никак не разберусь как найти это.

[Capella]

по моему аналогичная тема уже обсуждалась... что мешает самому графу быть подграфом самого себя?

[alanta]

действительно, есть тема созданная Java.

Странно, то есть получается сам граф?

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

[PAV]

Сначала ответьте, речь идет об учебном задании или промышленной задаче?

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

[alanta]

нужно для учебных целей. Граф маленький, до 10 вершин.

Цитата:

Если же нужно сделать учебную программу, то простой алгоритм придумать довольно легко.

Можете по-подробней рассказать о алгоритме?

[Gringoire]

Как уже было сказано,

alanta писал(а):

Клика- это максимальный полный подграф.

Полный - это значит, что любые две вершины соединены ребром. Ясно, что весь граф может не быть полным. Поэтому эта задача вовсе не тривиальная. Более того, проверка того, что в данном графе имеется клика из заданного числа элементов является NP-полной! То есть, грубо говоря, ее решение можно проверить за полиномиальное время, но скорее всего, решить за полиномиальное время нельзя.

Однако для маленьких графов вполне пройдет переборный алгоритм.


Рекомендую следующие книги:

В.А. Емеличев и др., "Лекции по теории графов", стр. 111.
Кормен, Лейзерсон, Ривест, "Алгоритмы: построение и анализ", стр. 864.

а также множество книг из этой библиотеки по теории графов.

[PAV]

Пусть вершины упорядочены. Будем обозначать их v1...vn.

В каждый момент у нас будет пара (G,vi), где G - некоторый полный подграф (возможно, пустой), vi - некоторая вершина, не входящая в G. Также будем помнить максимальный найденный полный подграф Gmax.

В начале работы G=Gm=0 (пустой), vi=v1.

Прямой ход алгоритма заключается в том, что мы проверяем, можно ли добавить к имеющемуся графу G вершину vi. Для этого надо перебрать все вершины в G и проверить, соединены ли они все с vi. Если да, то добавляем vi к G. Затем переходим к вершине v(i+1) и так до тех пор, пока не пройдем все вершины. После этого G будет некоторым максимальным подграфом (не обязательно кликой). Его надо сравнить с Gmax и если он больше, то заменяем Gmax на G.

После этого находим в G вершину с максимальным номером vj, удаляем его из G и проходим снова прямой ход начиная с пары (G,v(j+1)).

Вроде как должно работать.

Далее можно накручивать разные штуки, ускоряющие перебор.

[Capella]

Цитата:

Полный - это значит, что любые две вершины соединены ребром

PAV писал(а):

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

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

[Capella]

Я вот считаю странным, если у графа $ n $ вершин, у него что-же $ n ! $ соединений? Ведь если бы они были соединены через узлы, то было бы $ n - 1$. По моему так работает интернет, сложно представить себе что все серверы мира имеют прямое соединение между собой

[незваный гость]

PAV писал(а):

После этого находим в G вершину с максимальным номером vj, удаляем его из G и проходим снова прямой ход начиная с пары (G,v(j+1)).

Вроде как должно работать.

Не отрицая, что это проходимо (я, правда, запутался в удалении/добавлении -- тут не очень понятно), я бы порекомендовал рекурсивный подход.

clique(G):
  Gmax = max(Gmax, G)
  for each v after G:
     if v can be added to G:
        clique(G + v)                       // ***
     endif
   endfor

Сложность решения - как и положено - экспоненциальная, ведь мы проверяем $2^n$ подграфов.

Стоимость копирования Gmax пренебрежима, так как мы копируем не более $n$ раз. А вот копирование G можно избежать, заменяя clique(G + v) на

        // clique(G + v)
        G += v
        clique(G)
        G -= v

Может быть это именно то, что имел в виду PAV?

[незваный гость]

Capella писал(а):

Я вот считаю странным, если у графа $ n $ вершин, у него что-же $ n ! $ соединений? Ведь если бы они были соединены через узлы, то было бы $ n - 1$.

Мне кажется, Вы путаете понятия связанности и соединения. Две вершины соединены, если существует ребро с началом в одной, и концом в другой. Две вершины связанны, коли существует цепочка ребер из одной в другую. Построение матрицы связей по матрице соединений - одна из классических задач (очень популярна в начальных курсах по теории компиляции). Соединений может быть не более $ n $ (вершина может быть соединена сама с собой), а связей - до хрена...

[Capella]

Ага, да тут лингвистом надо прямо быть Я-же чувствовала, что здесь что-то не то. Спасибо!

[PAV]

незванный гость писал(а):

Может быть это именно то, что имел в виду PAV?

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

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