Как найти максимальную клику в графе? Что-то я не соображу алгоритм. Может кто знает?

перебором не пробовали:?

А что такое клика?

Клика - это полный подграф данного графа.
Самое лучшее решение такое. Строим граф Г* - дополнение нашего графа, то есть там где ребра в графе были там их не будет, а где их не было будут.
Тогда задача нахождения максимальных клик нашего графа, будет аналогичной нахождению максимальных независимых подмножеств в графе Г* (то бишь таких множеств вершин, среди которых никакие две не смежны, и все другие вершины графа смежны хотя бы одной вершине множества). Тогда нашим решением будет макимальное независимое подмножество графа Г*.
Если неизвестен алгоритм нахождения максимальных независимых подмножеств графа, могу скинуть.

Цитата(poor_yorik @ 15.1.2006, 23:13)

Клика - это полный подграф данного графа. Самое лучшее решение такое. Строим граф Г* - дополнение нашего графа, то есть там где ребра в графе были там их не будет, а где их не было будут.  Тогда задача нахождения максимальных клик нашего графа, будет аналогичной нахождению максимальных независимых подмножеств в графе Г* (то бишь таких множеств вершин, среди которых никакие две не смежны, и все другие вершины графа смежны хотя бы одной вершине множества). Тогда нашим решением будет макимальное независимое подмножество графа Г*. Если неизвестен алгоритм нахождения максимальных независимых подмножеств графа, могу скинуть.

Это не самое лучшее решение. Я все тот же перебор, экспоненциальный.


Кроме того что используется перебор еще нужно и редукцию делать.


И еще если вы пишите самое лучшее решение то пишите по какому критерию оно лучшее, а то имхо на самое худшее тянет

esperant0 Интересно, где ты тут редукцию увидел??? Поделись...
Я не спорю, что задача нахождения максимальных подмножеств это вообщем перебор, но довольно усеченнный
Если сравнить скорость алгоритма нахождения макисмального независимого подмножества и простого перебора, то для случаев где количество вершин побольше, перебор работает заметно (!!!)дольше.
Если у вас есть другой более эфективный вариант усечения перебора, прошу поделится.
А непереборного решения задачи про клики насколько мне известно, до сих пор найдено не было.