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í .

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 .

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í.

Některé důležité třídy grafů lze definovat pomocí jejich kliků:

Kromě toho mnoho dalších matematických konstrukcí zahrnuje kliky grafů. Mezi nimi:

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

  1. ↑ Erdős, Szekeres, 1935 .
  2. ↑ 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ů
  3. ↑ Luce, Perry, 1949 .
  4. ↑ 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
  5. ↑ Turán, 1941 .
  6. ↑ Graham, Rothschild, Spencer, 1990 .
  7. ↑ Moon, Moser, 1965 .
  8. ↑ 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 .
  9. ↑ Karp, 1972 .
  10. ↑ Ben-Dor, Shamir, Yakhini, 1999 .
  11. ↑ Tanay, Sharan, Shamir, 2002 .
  12. ↑ Sugihara, 1984 .
  13. ↑ Day, Sankoff, 1986 .
  14. ↑ Samudrala, Moult, 1998 .
  15. ↑ Spirin, Mirny, 2003 .
  16. ↑ Příhar, 1956 .
  17. ↑ Paull, Unger, 1959 .
  18. ↑ 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 .
  19. ↑ Cong, Smith, 1993 .
  20. ↑ Rhodes, Willett, Calvet, Dunbar, Humblet, 2003 .
  21. ↑ Kuhl, Crippen, Friesen, 1983 .

Literatura

Odkazy