Klika (teorie grafů)
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od
verze recenzované 11. dubna 2022; kontroly vyžadují
4 úpravy .
Klika neorientovaného grafu je podmnožinou jeho vrcholů, z nichž libovolné dva jsou spojeny hranou. Kliky jsou jedním ze základních konceptů teorie grafů a používají se v mnoha dalších matematických problémech a konstrukcích grafů. Kliky jsou také studovány v informatice - problém určení, zda existuje klika dané velikosti v grafu ( Clique problem ) je NP-úplný . Navzdory této obtížnosti se studuje mnoho algoritmů pro hledání klik.
Přestože studium úplných podgrafů začalo formulací Ramseyho věty z hlediska teorie grafů Erdősem a Székeresem [1] [2] . Termín „klika“ pochází z práce Luca a Periho [3] , kteří při studiu sociálních sítí používali plné podgrafy k modelování klik lidí , tedy skupin lidí, kteří se znají [4] . Kliknutí má mnoho dalších aplikací ve vědě, a zejména v bioinformatice .
Definice
Klika v neorientovaném grafu je podmnožina vrcholů taková, že pro jakékoli dva vrcholy existuje hrana, která je spojuje. To je ekvivalentní tvrzení, že podgraf vygenerovaný pomocí je kompletní .
![G=(V,E)](https://wikimedia.org/api/rest_v1/media/math/render/svg/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182)
![C\subseteq V](https://wikimedia.org/api/rest_v1/media/math/render/svg/3674daa0563e2c8ecaaa5f0fbac07010419c4269)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
Maximum clique , nebo clique maximum by inclusion , je klika, kterou nelze rozšířit přidáním vrcholů. Jinými slovy, tento graf neobsahuje větší kliku, ke které patří.
Největší klika nebo klika, která má maximální velikost , je klika maximální velikosti pro daný graf.
Číslo kliky grafu je počet vrcholů největší kliky grafu . Průsečíkové číslo grafu je nejmenší počet klik, které společně pokrývají všechny okraje grafu .
![\omega (G)](https://wikimedia.org/api/rest_v1/media/math/render/svg/75a4da4509a1dd5d7d6194b294e6db37dc85ea8e)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
Opakem kliky je nezávislá množina v tom smyslu, že každá klika odpovídá nezávislé množině v komplementárním grafu . Problém pokrytí kliky je najít co nejmenší počet klik obsahujících všechny vrcholy grafu.
Příbuzný termín je biclique, kompletní bipartitní podgraf . Bipartitní rozměr grafu je minimální počet bicliques potřebných k pokrytí všech okrajů grafu.
Matematika
Matematické výsledky týkající se klik zahrnují následující.
- Turanova věta [5] udává dolní hranici počtu klik v hustých grafech . Pokud má graf dostatek hran, musí obsahovat kliku. Například každý graf s vrcholy a více než hranami musí mít kliku tří vrcholů.
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![\scriptstyle \lfloor {\frac {n}{2}}\rfloor \cdot \lceil {\frac {n}{2}}\rceil](https://wikimedia.org/api/rest_v1/media/math/render/svg/7875b1f00c7ba08ac44b2fcadb3dc17e7a71e8f2)
- Ramseyův teorém [6] říká, že každý graf nebo jeho komplementární graf obsahuje kliku s alespoň logaritmickým počtem vrcholů.
- Podle výsledků Moona a Mosera [7] může graf s vrcholy obsahovat maximálně největší kliky. Grafy, které splňují tuto hranici, jsou Moon-Moserovy grafy, speciální případ Turanových grafů , které vznikají jako extrémní případ Turanova teorému.
![3n](https://wikimedia.org/api/rest_v1/media/math/render/svg/702e054176930a46bb558f22adad5d81f9f0cafd)
![3^n](https://wikimedia.org/api/rest_v1/media/math/render/svg/193abd21d79ceb2992929ab3b3a1ee97d2afb6a0)
![K_{3,3,\tečky}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43e0fd7637bcdb9a7fdf24acebe2f98ea8beb404)
- Hadwigerova domněnka , která zůstává neprokázaná, dává do souvislosti velikost největší kliky minoru v grafu (jeho Hadwigerovo číslo ) s jeho chromatickým číslem .
- Erdős-Faber-Lovasova domněnka je dalším neprokázaným tvrzením o vztahu mezi zbarvením grafu a klikami.
Některé důležité třídy grafů lze definovat pomocí jejich kliků:
- Akordický graf je graf, jehož vrcholy mohou být uspořádány v pořadí dokonalé eliminace; pořadí, ve kterém sousedé každého vrcholu přicházejí po vrcholu .
![proti](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
![proti](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
- Cograph je graf, jehož všechny vygenerované podgrafy mají tu vlastnost, že jakákoliv největší klika protíná jakoukoli největší nezávislou množinu v jediném vrcholu.
- Intervalový graf je graf, jehož největší kliky mohou být uspořádány tak, že pro jakýkoli vrchol , kliky obsahující , jdou postupně.
![proti](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
![proti](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
- Spojnicový graf je graf, jehož hrany mohou být pokryty klikami bez společných hran, navíc každý vrchol bude patřit právě dvěma klikám.
- Dokonalý graf je graf, ve kterém se počet kliky rovná chromatickému číslu v každém generovaném podgrafu .
- Rozdělený graf je graf, ve kterém některá sada klik obsahuje alespoň jeden vrchol z každé hrany.
- Graf bez trojúhelníků je graf, ve kterém nejsou žádné jiné kliky kromě vrcholů a hran.
Kromě toho mnoho dalších matematických konstrukcí zahrnuje kliky grafů. Mezi nimi:
- Kolekce kliků grafu je abstraktní simplexní kolekce s simplexem pro každý klik v;
![X(G)](https://wikimedia.org/api/rest_v1/media/math/render/svg/dcfa3d3f2e801e62a38bfcc0842e5861f3898900)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
- Simplexní graf je neorientovaný grafs vrcholy pro každou kliku v grafua hranami spojujícími dvě kliky, které se liší o jeden vrchol. Tento graf je příkladem mediánového grafu a souvisí s algebrou mediánů na klikách grafu — mediánutří klikaje klikou, jejíž vrcholy patří alespoň dvěma klikám z,a [8] ;
![\kappa (G)](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b77bb1e6f4cb161f736c8770bf755a0c1852c12)
![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
![m(A, B, C)](https://wikimedia.org/api/rest_v1/media/math/render/svg/b37dd78237e2d5f7cb701e0787d543e242aba3a3)
![A](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
![B](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
![A](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
![B](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
- Součet po kliknutí je metoda kombinace dvou grafů jejich sloučením po kliknutí;
- Šířka kliky je kategorie složitosti grafu ve smyslu minimálního počtu různých štítků vrcholů potřebných k sestavení grafu z nesourodých množin pomocí operací značení a operací spojení pro všechny páry vrcholů se stejným štítkem. Grafy se šířkou kliky jedna jsou přesně nesourodé sady klik;
- Počet průsečíků grafu je minimální počet kliků potřebný k pokrytí všech okrajů grafu.
Blízký koncept pro úplné podgrafy je rozdělení grafů na kompletní podgrafy a kompletní grafové minory . Zejména Kuratowského teorém a Wagnerův teorém charakterizují rovinné grafy tím, že zakazují úplné a úplné bipartitní podgrafy a menší.
Počítačová věda
V informatice je problém kliky výpočetním problémem nalezení maximální kliky nebo klik v daném grafu. Problém je NP-úplný , jeden z Karpových 21 NP-úplných problémů [9] . Je také obtížné pro parametrickou aproximaci a obtížné aproximovat . Bylo však vyvinuto mnoho klikových algoritmů , které buď běží v exponenciálním čase (jako je Bron-Kerboschův algoritmus ), nebo se specializují na rodiny grafů, jako jsou rovinné grafy nebo dokonalé grafy , pro které lze problém vyřešit v polynomiálním čase .
Svobodný software pro nalezení maximální kliky
Níže je uveden seznam svobodného softwaru pro nalezení maximálního klikání.
název |
Licence |
API jazyk |
Stručný popis
|
NetworkX |
BSD |
Krajta |
přibližné řešení, viz postup max_clique (downlink)
|
maxClique |
CRAPL |
Jáva |
přesné algoritmy, implementace DIMACS Archivováno 23. září 2015 na Wayback Machine
|
openopt |
BSD |
Krajta |
přesná a přibližná řešení, schopnost specifikovat hrany, které mají být zahrnuty ( MCP )
|
Aplikace
Mnoho různých bioinformatických problémů je modelováno pomocí klik. Například Ben-Dor, Shamir a Yahini [10]
modelovali problém seskupování genové exprese jako problém nalezení minimálního počtu změn potřebných k transformaci datového grafu do grafu tvořeného odpojenými sadami klik. Tanay, Sharan a Shamir [11] diskutují o podobném problému seskupení dat genové exprese, kdy shluky musí být kliky. Sugihara [12] použil kliky k modelování ekologických nik v potravinových řetězcích . Day a Sankow [13] popisují problém popisu evolučních stromů jako problém nalezení maximálních kliků v grafu, ve kterém vrcholy představují charakteristiky a dva vrcholy jsou spojeny hranou, pokud existuje ideální vývojová historie , která je kombinuje dvě vlastnosti. Samudrala a Molt [14] modelovali predikci proteinové struktury jako problém hledání klik v grafu, jehož vrcholy reprezentují pozice proteinových částí, a hledáním klik ve schématu interakce protein-protein . Spirit a Mirni [15] našli shluky proteinů, které spolu úzce interagují a mimo shluk mají jen malou interakci. Analýza mohutnosti grafu je metoda pro zjednodušení složitých biologických systémů hledáním klik a příbuzných struktur v těchto systémech.
V elektrotechnice Prihar [16] použil kliky k analýze komunikačních sítí a Paul a Unger [17] je použili k vývoji účinných obvodů pro výpočet částečně definovaných booleovských funkcí. Kliknutí se také používá při automatickém generování testovacích obrazců - velká klika v grafu nekompatibility možných defektů dává dolní hranici sady testů [18] . Kong a Smith [19] popisují použití klik pro hledání hierarchických struktur v elektrických obvodech.
V chemii Rhodes et al [20] použili kliky k popisu chemických sloučenin v chemické databázi , které mají vysoký stupeň podobnosti. Kuhl, Kripen a Friesen [21] použili kliky k modelování pozic, ve kterých se dvě chemické sloučeniny na sebe vážou.
Viz také
Poznámky
- ↑ Erdős, Szekeres, 1935 .
- ↑ Dřívější práce Kazimira Kuratowského Kuratowského z roku 1930 o charakterizaci rovinných grafů zákazem úplných a úplných bipartitních podgrafů je formulována spíše v topologických termínech než v termínech teorie grafů
- ↑ Luce, Perry, 1949 .
- ↑ Pro další práci při modelování sociálních klik pomocí teorie grafů viz Alba Alba, 1973 , Pius Peay, 1974 a Dorian a Woodard Doreian, Woodard, 1994
- ↑ Turán, 1941 .
- ↑ Graham, Rothschild, Spencer, 1990 .
- ↑ Moon, Moser, 1965 .
- ↑ J.-P. Barthelemy, B. Leclerc, B. Monjardet. O použití uspořádaných množin v problémech srovnání a konsensu klasifikací // Journal of Classification. - 1986. - T. 3 , vydání. 2 . - S. 200 . - doi : 10.1007/BF01894188 .
- ↑ Karp, 1972 .
- ↑ Ben-Dor, Shamir, Yakhini, 1999 .
- ↑ Tanay, Sharan, Shamir, 2002 .
- ↑ Sugihara, 1984 .
- ↑ Day, Sankoff, 1986 .
- ↑ Samudrala, Moult, 1998 .
- ↑ Spirin, Mirny, 2003 .
- ↑ Příhar, 1956 .
- ↑ Paull, Unger, 1959 .
- ↑ I. Hamzaoglu, JH Patel. Proč. 1998 Mezinárodní konference IEEE/ACM o počítačově podporovaném designu. - 1998. - S. 283-289 . doi : 10.1145 / 288548.288615 .
- ↑ Cong, Smith, 1993 .
- ↑ Rhodes, Willett, Calvet, Dunbar, Humblet, 2003 .
- ↑ Kuhl, Crippen, Friesen, 1983 .
Literatura
- Paul Erdős, George Szekeres. Kombinatorický problém v geometrii // Compositio Math. - 1935. - T. 2 . - S. 463-470 .
- Luce R. Duncan, Albert D. Perry. Metoda maticové analýzy skupinové struktury // Psychometrie. - 1949. - svazek 2 , vydání. 14 . - S. 95-116 . - doi : 10.1007/BF02289146 . — PMID 18152948 .
- Moon, JW, Leo Moser. O klikách v grafech // Israel J. Math .. - 1965. - T. 3 . — S. 23–28 . - doi : 10.1007/BF02760024 .
- Ronald Graham, B. Rothschild, Joel Spencer. Ramseyho teorie. - New York: John Wiley and Sons, 1990. - ISBN 0-471-50046-1 .
- Pavel Turan. K extrémnímu problému v teorii grafů (maďarsky) // Matematikai és Fizikai Lapok. - 1941. - T. 48 . - S. 436-452 .
- Richard D. Alba. Grafově teoretická definice sociometrické kliky // Journal of Mathematical Sociology. - 1973. - T. 3 , no. 1 . - S. 113-126 . - doi : 10.1080/0022250X.1973.9989826 .
- Edmund R. Peay. Hierarchické klikové struktury // Sociometrie. - 1974. - T. 37 , no. 1 . - S. 54-65 . - doi : 10.2307/2786466 . — .
- Patrick Doreian, Katherine L. Woodard. Definování a lokalizace jader a hranic sociálních sítí // Sociální sítě. - 1994. - T. 16 , no. 4 . - S. 267-293 . - doi : 10.1016/0378-8733(94)90013-2 .
- Richard M. Karp. Složitost počítačových výpočtů / RE Miller, JW Thatcher. - New York: Plénum, 1972. - s. 85–103 .
- Amir Ben-Dor, Ron Shamir, Zohar Yakhini. Shlukování vzorů genové exprese // Journal of Computational Biology. - 1999. - V. 6 , čís. 3-4 . - S. 281-297 . doi : 10.1089 / 106652799318274 . — PMID 10582567 .
- Amos Tanay, Roded Sharan, Ron Shamir. Objevování statisticky významných klastrů v datech genové exprese // Bioinformatika. - 2002. - T. 18 , no. Suppl. 1 . - S. S136-S144 . - doi : 10.1093/bioinformatics/18.suppl_1.S136 . — PMID 12169541 .
- George Sugihara. Populační biologie / editor: Simon A. Levin. - 1984. - T. 30 . - S. 83-101 .
- William HE Day, David Sankoff. Výpočetní složitost odvozování fylogenezí podle kompatibility // Systematická zoologie. - 1986. - T. 35 , no. 2 . - S. 224-229 . - doi : 10.2307/2413432 . — .
- Ram Samudrala, John Moult. Grafově teoretický algoritmus pro srovnávací modelování struktury proteinů // Journal of Molecular Biology. - 1998. - T. 279 , č. 1 . - S. 287-302 . - doi : 10.1006/jmbi.1998.1689 . — PMID 9636717 .
- Victor Spirin, Leonid A. Mirny. Proteinové komplexy a funkční moduly v molekulárních sítích // Proceedings of the National Academy of Sciences . - 2003. - T. 100 , no. 21 . - S. 12123-12128 . - doi : 10.1073/pnas.2032324100 . — PMID 14517352 .
- Z. Přihar. Topologické vlastnosti telekomunikačních sítí // Proceedings of the IRE . - 1956. - T. 44 , čís. 7 . - S. 927-933 . - doi : 10.1109/JRPROC.1956.275149 .
- MC Paull, SH Unger. Minimalizace počtu stavů v neúplně specifikovaných funkcích sekvenčního přepínání. - 1959. - Sv. EC-8. - Problém. 3 . - S. 356-367 . - doi : 10.1109/TEC.1959.5222697 .
- J. Cong, M. Smith. Proč. 30. mezinárodní konference automatizace designu. - 1993. - S. 755-760 . - doi : 10.1145/157485.165119 .
- Nicholas Rhodes, Peter Willett, Alain Calvet, James B. Dunbar, Christine Humblet. CLIP: podobnostní vyhledávání 3D databází pomocí detekce kliky // Journal of Chemical Information and Computer Sciences. - 2003. - T. 43 , no. 2 . - S. 443-448 . - doi : 10.1021/ci025605o . — PMID 12653507 .
- FS Kuhl, GM Crippen, DK Friesen. Kombinatorický algoritmus pro výpočet vazby ligandu // Journal of Computational Chemistry. - 1983. - V. 5 , čís. 1 . — S. 24–34 . - doi : 10.1002/jcc.540050105 .
- Kazimierz Kuratowski. Sur le probleme des courbes gauches en Topologie (francouzsky) // Fundamenta Mathematicae. - 1930. - T. 15 . - S. 271-283 .
Odkazy