Задача про кліку належить до класу NP-повних задач в області теорії графів. Вперше її сформулював 1972 року Річард Карп.
Клікою в неорієнтованому графі називається підмножина вершин, кожні дві з яких з'єднані ребром графу. Іншими словами, це повний підграф первісного графа. Розмір кліки визначається як число вершин в ній. Задача про кліку існує у двох варіантах: у задачі розпізнавання потрібно визначити, чи існує в заданому графі G кліка розміру k, тоді як в обчислювальному варіанті потрібно знайти в заданому графі G кліку максимального розміру або всі максимальні кліки (такі, що не можна збільшити).
Історія
Хоча повні підграфи довгий час вивчалися в математиці, термін «кліка» і задача алгоритмічно оголошеного кліка обидва походять із соціальних наук, де повні підграфи використовувались як модель соціальних кліків, груп людей, які всі знають один одного. Термінологія «кліка» походить від та (1949), та перший алгоритм розв'язання задачі про кліку винайшли Харарі та (1957), для соціологічних досліджень.
Після роботи Харарі і Росса, багато інших авторів розробили алгоритми для розв'язання різних версій задачі про кліку. У 1970-х, дослідники почали вивчати ці алгоритми з точки зору найгіршого аналізу; див., наприклад, Тарьян та Трояновськи (1977), перші роботи про вирішення найгіршого максимального кліку. Крім того, у 1970-х роках, починаючи з роботи (1971) і Карпа (1972), дослідники почали знаходити математичне обґрунтування для сприйманої складності кліку проблеми в теорії NP-повноти і пов'язаних незговірливих результатів. У 1990-ті роки, був написаний цикл робіт, починаючи з Фейга і співавт. (1991) і повідомив у той час пресі про те, що неможливо розв'язати цю задачу максимально точно та ефективно.
NP-Повнота
NP-повнота задачі про кліку випливає з NP-повноти задача про незалежну множину (вершин). Легко показати, що необхідною і достатньою умовою для існування кліки розміру k є наявність незалежної множини розміру не менше k в доповненні графу. Це очевидно, оскільки повнота підграфу означає, що його доповнення не містить жодного ребра.
Інший доказ NP-повноти можна знайти в книзі «Алгоритми: побудова й аналіз».
Алгоритми
Як і для інших NP-повних задач, ефективного алгоритму для пошуку кліки заданого розміру на цей час не знайдено. Повний перебір всіх можливих підграфів розміру k з перевіркою того, чи є хоча б один з них повним, — неефективний, оскільки повне число таких підграфів в графі з v вершинами збігається біноміальним коефіцієнтом
Інший алгоритм працює так: дві кліки розміру n і m «склеюються» у велику кліку розміру (n + m), причому клікою розміру 1 покладається окрема вершина графу. Алгоритм завершується, як тільки жодного злиття більше здійснити не можна. Час роботи даного алгоритму є лінійним, проте він є евристичним, оскільки не завжди призводить до знаходження кліки максимального розміру. Як приклад невдалого завершення можна навести випадок, коли вершини, що належать максимальній кліці, виявляються розділені й перебувають у кліках меншого розміру, причому останні вже не можуть бути «склеєними» між собою.
Див. також
- Алгоритм Брона-Кербоша — швидкий пошук клік
- Соціальний граф
- Словник термінів теорії графів
Примітки
- Karp, Richard (1972). (PDF). Proceedings of a Symposium on the Complexity of Computer Computations. Plenum Press. Архів оригіналу (PDF) за 29 червня 2011. Процитовано 29 травня 2014.
- Complete subgraphs make an early appearance in the mathematical literature in the graph-theoretic reformulation of by Erdős та Szekeres, (1935).
- Kolata, Gina (26 червня 1990), , New York Times, архів оригіналу за 8 квітня 2014, процитовано 3 серпня 2014.
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. —
Література
- (1971). . Proceedings of the Third Annual ACM Symposium on Theory of Computing. Shaker Heights, Ohio. с. 151—158. Архів оригіналу за 3 травня 2006. Процитовано 11 червня 2007.
- ; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A1.2: GT19, pg.194.
- (1971), The complexity of theorem-proving procedures, , с. 151—158, doi:10.1145/800157.805047, архів оригіналу за 30 жовтня 2019, процитовано 29 травня 2014
{{}}
: Назва URL містить вбудоване вікіпосилання (). - Downey, R. G.; (1995), Fixed-parameter tractability and completeness. II. On completeness for W[1], , 141 (1–2): 109—131, doi:10.1016/0304-3975(94)00097-3
- Downey, R. G.; (1999), Parameterized complexity, Springer-Verlag, ISBN .
- Eisenbrand, F.; Grandoni, F. (2004), On the complexity of fixed parameter clique and dominating set, , 326 (1–3): 57—67, doi:10.1016/j.tcs.2004.05.009
- Eppstein, David; Löffler, Maarten; Strash, Darren (2010), Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time, у Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo (ред.), 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, Lecture Notes in Computer Science, т. 6506, Springer-Verlag, с. 403—414, arXiv:1006.5440, doi:10.1007/978-3-642-17517-6_36, ISBN
- Eppstein, David; Strash, Darren (2011), Listing all maximal cliques in large sparse real-world graphs, 10th International Symposium on Experimental Algorithms, arXiv:1103.0318.
- Erdős, Paul; Szekeres, George (1935), (PDF), Compositio Mathematica, 2: 463—470, архів оригіналу (PDF) за 22 травня 2020, процитовано 29 травня 2014.
Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Zadacha pro kliku nalezhit do klasu NP povnih zadach v oblasti teoriyi grafiv Vpershe yiyi sformulyuvav 1972 roku Richard Karp Graf z klikoyu rozmiru 3 Klikoyu v neoriyentovanomu grafi nazivayetsya pidmnozhina vershin kozhni dvi z yakih z yednani rebrom grafu Inshimi slovami ce povnij pidgraf pervisnogo grafa Rozmir kliki viznachayetsya yak chislo vershin v nij Zadacha pro kliku isnuye u dvoh variantah u zadachi rozpiznavannya potribno viznachiti chi isnuye v zadanomu grafi G klika rozmiru k todi yak v obchislyuvalnomu varianti potribno znajti v zadanomu grafi G kliku maksimalnogo rozmiru abo vsi maksimalni kliki taki sho ne mozhna zbilshiti IstoriyaHocha povni pidgrafi dovgij chas vivchalisya v matematici termin klika i zadacha algoritmichno ogoloshenogo klika obidva pohodyat iz socialnih nauk de povni pidgrafi vikoristovuvalis yak model socialnih klikiv grup lyudej yaki vsi znayut odin odnogo Terminologiya klika pohodit vid ta 1949 ta pershij algoritm rozv yazannya zadachi pro kliku vinajshli Harari ta 1957 dlya sociologichnih doslidzhen Pislya roboti Harari i Rossa bagato inshih avtoriv rozrobili algoritmi dlya rozv yazannya riznih versij zadachi pro kliku U 1970 h doslidniki pochali vivchati ci algoritmi z tochki zoru najgirshogo analizu div napriklad Taryan ta Troyanovski 1977 pershi roboti pro virishennya najgirshogo maksimalnogo kliku Krim togo u 1970 h rokah pochinayuchi z roboti 1971 i Karpa 1972 doslidniki pochali znahoditi matematichne obgruntuvannya dlya sprijmanoyi skladnosti kliku problemi v teoriyi NP povnoti i pov yazanih nezgovirlivih rezultativ U 1990 ti roki buv napisanij cikl robit pochinayuchi z Fejga i spivavt 1991 i povidomiv u toj chas presi pro te sho nemozhlivo rozv yazati cyu zadachu maksimalno tochno ta efektivno NP PovnotaNP povnota zadachi pro kliku viplivaye z NP povnoti zadacha pro nezalezhnu mnozhinu vershin Legko pokazati sho neobhidnoyu i dostatnoyu umovoyu dlya isnuvannya kliki rozmiru k ye nayavnist nezalezhnoyi mnozhini rozmiru ne menshe k v dopovnenni grafu Ce ochevidno oskilki povnota pidgrafu oznachaye sho jogo dopovnennya ne mistit zhodnogo rebra Inshij dokaz NP povnoti mozhna znajti v knizi Algoritmi pobudova j analiz AlgoritmiYak i dlya inshih NP povnih zadach efektivnogo algoritmu dlya poshuku kliki zadanogo rozmiru na cej chas ne znajdeno Povnij perebir vsih mozhlivih pidgrafiv rozmiru k z perevirkoyu togo chi ye hocha b odin z nih povnim neefektivnij oskilki povne chislo takih pidgrafiv v grafi z v vershinami zbigayetsya binomialnim koeficiyentom v k v k v k displaystyle v choose k frac v k v k Inshij algoritm pracyuye tak dvi kliki rozmiru n i m skleyuyutsya u veliku kliku rozmiru n m prichomu klikoyu rozmiru 1 pokladayetsya okrema vershina grafu Algoritm zavershuyetsya yak tilki zhodnogo zlittya bilshe zdijsniti ne mozhna Chas roboti danogo algoritmu ye linijnim prote vin ye evristichnim oskilki ne zavzhdi prizvodit do znahodzhennya kliki maksimalnogo rozmiru Yak priklad nevdalogo zavershennya mozhna navesti vipadok koli vershini sho nalezhat maksimalnij klici viyavlyayutsya rozdileni j perebuvayut u klikah menshogo rozmiru prichomu ostanni vzhe ne mozhut buti skleyenimi mizh soboyu Div takozhAlgoritm Brona Kerbosha shvidkij poshuk klik Socialnij graf Slovnik terminiv teoriyi grafivPrimitkiKarp Richard 1972 PDF Proceedings of a Symposium on the Complexity of Computer Computations Plenum Press Arhiv originalu PDF za 29 chervnya 2011 Procitovano 29 travnya 2014 Complete subgraphs make an early appearance in the mathematical literature in the graph theoretic reformulation of by Erdos ta Szekeres 1935 Kolata Gina 26 chervnya 1990 New York Times arhiv originalu za 8 kvitnya 2014 procitovano 3 serpnya 2014 Kormen T Lejzerson Ch Rivest R Shtajn K Algoritmy postroenie i analiz Introduction to Algorithms Pod red I V Krasikova 2 e izd M Vilyams 2005 1296 s ISBN 5 8459 0857 4Literatura 1971 Proceedings of the Third Annual ACM Symposium on Theory of Computing Shaker Heights Ohio s 151 158 Arhiv originalu za 3 travnya 2006 Procitovano 11 chervnya 2007 Johnson David S 1979 Computers and Intractability A Guide to the Theory of NP Completeness W H Freeman ISBN 0 7167 1045 5 A1 2 GT19 pg 194 1971 The complexity of theorem proving procedures s 151 158 doi 10 1145 800157 805047 arhiv originalu za 30 zhovtnya 2019 procitovano 29 travnya 2014 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Nazva URL mistit vbudovane vikiposilannya dovidka Downey R G 1995 Fixed parameter tractability and completeness II On completeness for W 1 141 1 2 109 131 doi 10 1016 0304 3975 94 00097 3 Downey R G 1999 Parameterized complexity Springer Verlag ISBN 0 387 94883 X Eisenbrand F Grandoni F 2004 On the complexity of fixed parameter clique and dominating set 326 1 3 57 67 doi 10 1016 j tcs 2004 05 009 Eppstein David Loffler Maarten Strash Darren 2010 Listing All Maximal Cliques in Sparse Graphs in Near Optimal Time u Cheong Otfried Chwa Kyung Yong Park Kunsoo red 21st International Symposium on Algorithms and Computation ISAAC 2010 Jeju Korea Lecture Notes in Computer Science t 6506 Springer Verlag s 403 414 arXiv 1006 5440 doi 10 1007 978 3 642 17517 6 36 ISBN 978 3 642 17516 9 Eppstein David Strash Darren 2011 Listing all maximal cliques in large sparse real world graphs 10th International Symposium on Experimental Algorithms arXiv 1103 0318 Erdos Paul Szekeres George 1935 PDF Compositio Mathematica 2 463 470 arhiv originalu PDF za 22 travnya 2020 procitovano 29 travnya 2014 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi