Я хотел бы знать быстрый алгоритм, чтобы найти только номер клики (без фактического нахождения клики) графа с примерно 100 вершинами.clique number of graph
Я пытаюсь решить следующую проблему. http://uva.onlinejudge.org/external/1/193.html
Это NP-полный, и вы не можете сделать это намного лучше, чем на самом деле находить максимальную клику и подсчитывать ее вершины. От Wikipedia:
Clique проблемы включают в себя:
- решения проблемы принятия тестирования содержит ли граф кликой больше, чем N
Эти проблемы все сложно: Клика проблема решение составляет
NP-полный (один из Карпа 21NP-полные проблемы),
Если вы можете найти номер клики в P, тогда проблема решения ответит в P (вы просто вычислите номер клики и сравните его с N).
Поскольку проблема решения - NP-Complete, поиск номера клики общего графика должен быть NP-Hard.
Как уже было сказано другими, это, вероятно, очень сложно.
Но, как и многие теоретически сложные проблемы, на практике это может быть довольно быстро с хорошим алгоритмом и подходящими данными. Если вы реализуете что-то вроде Bron-Kerbosch для поиска кликов, а отслеживая наибольший размер клики, который вы нашли до сих пор, вы можете отступить от бесплодных поисковых деревьев.
Например, если вы нашли клику с 20 узлами в ней, и ваша сеть имеет большое количество узлов со степенью менее 20, вы можете немедленно исключить эти узлы из дальнейшего рассмотрения. С другой стороны, если распределение степени более однородно, то это может быть так же медленным, как поиск всех клик.
Хотя проблема в NP-hard, размер шрифта, который вы упомянули, не является проблемой для самых быстрых максимальных максимальных кликов сегодняшнего дня (для любой конфигурации).
Если вы готовы реализовать код, я рекомендую вам ознакомиться с документами, связанными с семейством алгоритмов MCQ, MCR и MCS, а также с семейными BBMC, BBMCL и BBMCX. Интересной отправной точкой является сравнительный обзор Prosser [Prosser 12]. Он включает объяснение реализации Java этих алгоритмов.
@poly: http://en.wikipedia.org/wiki/Clique_number#Definitions – kennytm
Число кликов - это число вершин в максимальной клике. – copperhead
Спасибо за ссылку UVA; Я попытаюсь работать над этим в выходные. Обратите внимание, что проблема заключается в Brute Force/Backtracking - простые категории, однако: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=129 – polygenelubricants