Clique (teorie grafů) - Clique (graph theory)

Pro další použití viz Clique (disambiguation).
Graf s
  • 23 × 1-vrchol vrcholů (vrcholy),
  • 42 × 2-vrcholové kliky (hrany),
  • 19 × 3-vrchol vrcholů (světle a tmavě modré trojúhelníky), a
  • 2 × 4-vrcholové kliky (tmavě modré oblasti).
11 světle modrých trojúhelníků tvoří maximální kliky. Dvě tmavomodré 4 kliky jsou maximální i maximální a počet klik v grafu je 4.

V matematický oblast teorie grafů, a klika (/ˈkliːk/ nebo /ˈklɪk/) je podmnožina vrcholů neorientovaný graf tak, že každé dva odlišné vrcholy v klice sousedí; to je jeho indukovaný podgraf je kompletní. Cliques 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 na grafech. Kliky byly také studovány v počítačová věda: úkol zjistit, zda existuje klika dané velikosti v a graf (dále jen klika problém ) je NP-kompletní, ale i přes tento výsledek tvrdosti bylo studováno mnoho algoritmů pro hledání klik.

Ačkoli studie o kompletní podgrafy se vrací alespoň k graficko-teoretickému přeformulování Ramseyova teorie podle Erdős & Szekeres (1935),[1] termín klika pochází z Luce & Perry (1949), kteří v roce 2006 použili kompletní podgrafy sociální sítě modelovat kliky lidí; to znamená skupiny lidí, z nichž se všichni znají. Cliques mají mnoho dalších aplikací ve vědách a zejména v bioinformatika.

Definice

A klika, C, v neorientovaný graf G = (PROTI, E) je podmnožinou souboru vrcholy, C ⊆ PROTI, takže každé dva odlišné vrcholy sousedí. To odpovídá podmínce, že indukovaný podgraf z G vyvolané C je kompletní graf. V některých případech může termín klika odkazovat také přímo na podgraf.

A maximální klika je klika, kterou nelze rozšířit zahrnutím dalšího sousedního vrcholu, tj. kliky, která neexistuje výhradně v sadě vrcholů větší kliky. Někteří autoři definují kliky způsobem, který vyžaduje, aby byly maximální, a používají jinou terminologii pro úplné podgrafy, které nejsou maximální.

A maximální klika grafu, G, je klika, takže neexistuje klika s více vrcholy. Navíc číslo kliky ω (G) grafu G je počet vrcholů v maximálním kliku G.

The číslo křižovatky z G je nejmenší počet klik, které společně pokrývají všechny okrajeG.

The číslo krytu grafu G je nejmenší počet klik G jehož unie pokrývá množinu vrcholů PROTI grafu.

A maximální příčná klika grafu je podmnožina vrcholů s vlastností, že každá maximální klika grafu obsahuje alespoň jeden vrchol v podmnožině.[2]

Opakem kliky je nezávislá sada, v tom smyslu, že každá klika odpovídá nezávislé sadě v doplňkový graf. The klikový obal problém se týká nalezení co nejméně klik, které obsahují každý vrchol v grafu.

Souvisejícím konceptem je a biclique, a kompletní bipartitní podgraf. The bipartitní rozměr grafu je minimální počet cyklů potřebných k pokrytí všech okrajů grafu.

Matematika

Matematické výsledky týkající se klik zahrnují následující.

Několik důležitých tříd grafů může být definováno nebo charakterizováno jejich klikami:

Mnoho dalších matematických konstrukcí navíc zahrnuje kliky v grafech. Mezi nimi,

  • The klikový komplex grafu G je abstraktní zjednodušený komplex X(G) s simplexem pro každé kliky G
  • A simplexní graf je neorientovaný graf κ (G) s vrcholem pro každou kliku v grafu G a hrana spojující dvě kliky, které se liší jedním vrcholem. Je to příklad střední graf, a je spojen s a střední algebra na klikách grafu: medián m(A,B,C) ze tří klik A, B, a C je klika, jejíž vrcholy patří alespoň ke dvěma klikám A, B, a C.[5]
  • The klika-součet je metoda pro kombinaci dvou grafů jejich sloučením podél sdílené kliky.
  • Šířka kliky je pojem složitosti grafu, pokud jde o minimální počet odlišných štítků vrcholů potřebných k sestavení grafu z disjunktních spojení, operací rebrandingu a operací, které spojují všechny páry vrcholů s danými štítky. Grafy s šířkou kliky jsou přesně nesouvislé svazky klik.
  • The číslo křižovatky grafu je minimální počet klik nutných k pokrytí všech okrajů grafu.
  • The klikový graf grafu je průsečíkový graf jeho maximálních klik.

Úzce související koncepty k dokončení podgrafů jsou dělení úplných grafů a úplných nezletilí v grafu. Zejména, Kuratowského věta a Wagnerova věta charakterizovat rovinné grafy zakázaným úplným a kompletní bipartita dělení a nezletilí.

Počítačová věda

Hlavní článek: Clique problém

v počítačová věda, klika problém je výpočetní problém s nalezením maximální kliky nebo všech klik v daném grafu. to je NP-kompletní, jeden z Karpových 21 NP-úplných problémů.[6] Je to také pevný parametr nepoddajný, a těžko aproximovat. Přesto mnoho algoritmy pro výpočet kliky byly vyvinuty, ať už běží exponenciální čas (tak jako Bron – Kerboschův algoritmus ) nebo se specializuje na rodiny grafů, jako je rovinné grafy nebo perfektní grafy pro které lze problém vyřešit v polynomiální čas.

Aplikace

Slovo „klika“ ve svém graficko-teoretickém použití vzniklo z práce Luce & Perry (1949), který k modelování použil úplné podgrafy kliky (skupiny lidí, kteří se navzájem znají) v sociální sítě. Stejnou definici použil i Festinger (1949) v článku používající méně technické výrazy. Obě práce se zabývají odkrýváním klik v sociální síti pomocí matic. Pro pokračující snahy modelovat sociální kliky graficky, viz např. Alba (1973), Peay (1974), a Doreian & Woodard (1994).

Mnoho různých problémů od bioinformatika byly modelovány pomocí klik. Například Ben-Dor, Shamir a Yakhini (1999) modelovat problém shlukování genová exprese data jako jedna z možností nalezení minimálního počtu změn potřebných k transformaci grafu popisujícího data do grafu vytvořeného jako disjunktní spojení klik; Tanay, Sharan & Shamir (2002) diskutovat o podobné biclustering problém pro výrazová data, ve kterých jsou klastry vyžadovány jako kliky. Sugihara (1984) používá k modelování kliky ekologické výklenky v potravinářské weby. Den a Sankoff (1986) popsat problém odvození evoluční stromy jako jeden z nalezení maximálních klik v grafu, který má jako své vrcholy charakteristiky druhu, kde dva vrcholy sdílejí hranu, pokud existuje dokonalá fylogeneze kombinace těchto dvou znaků. Samudrala & Moult (1998) Modelka predikce proteinové struktury jako problém najít kliky v grafu, jehož vrcholy představují polohy podjednotek proteinu. A hledáním kliků v a interakce protein-protein síť, Spirin & Mirny (2003) našel shluky proteinů, které spolu úzce interagují a mají málo interakcí s proteiny mimo shluk. Analýza grafu síly je metoda pro zjednodušení složitých biologických sítí hledáním klik a souvisejících struktur v těchto sítích.

v elektrotechnika, Prihar (1956) používá k analýze komunikačních sítí kliky a Paull & Unger (1959) použít je k návrhu efektivních obvodů pro výpočet částečně specifikovaných booleovských funkcí. Kliky byly také použity v automatické generování testovacího vzoru: velká klika v grafu nekompatibility možných poruch poskytuje dolní mez velikosti testovací sady.[7] Cong & Smith (1993) popsat aplikaci klik při hledání hierarchického rozdělení elektronického obvodu na menší podjednotky.

v chemie, Rhodes a kol. (2003) použijte k popisu chemikálií v a chemická databáze které mají vysoký stupeň podobnosti s cílovou strukturou. Kuhl, Crippen & Friesen (1983) použijte kliky k modelování pozic, ve kterých se na sebe dvě chemikálie váží.

Viz také

Poznámky

  1. ^ Dřívější práce od Kuratowski (1930) charakterizující rovinné grafy zakázaným úplným a kompletní bipartita podgrafy byly původně formulovány spíše topologicky než graficky.
  2. ^ Chang, Kloks & Lee (2001).
  3. ^ Turán (1941).
  4. ^ Graham, Rothschild & Spencer (1990).
  5. ^ Barthélemy, Leclerc a Monjardet (1986), strana 200.
  6. ^ Karp (1972).
  7. ^ Hamzaoglu & Patel (1998).

Reference

  • Alba, Richard D. (1973), „Graficko-teoretická definice sociometrické kliky“ (PDF), Journal of Mathematical Sociology, 3 (1): 113–126, doi:10.1080 / 0022250X.1973.9989826.
  • Barthélemy, J.-P .; Leclerc, B .; Monjardet, B. (1986), „O použití uspořádaných množin v problémech srovnání a konsensu klasifikací“, Journal of Classification, 3 (2): 187–224, doi:10.1007 / BF01894188.
  • Ben-Dor, Amir; Shamir, Ron; Yakhini, Zohar (1999), „Klastrování vzorů genové exprese.“, Journal of Computational Biology, 6 (3–4): 281–297, CiteSeerX  10.1.1.34.5341, doi:10.1089/106652799318274, PMID  10582567.
  • Chang, Maw-Shang; Kloks, Ton; Lee, Chuan-Min (2001), „Maximum clique transversals“, Graficko-teoretické koncepty v počítačové vědě (Boltenhagen, 2001), Poznámky k přednášce ve Výpočtu. Sci., 2204Springer, Berlín, s. 32–43, doi:10.1007/3-540-45477-2_5, ISBN  978-3-540-42707-0, PAN  1905299.
  • Cong, J .; Smith, M. (1993), „Paralelní algoritmus seskupování zdola nahoru s aplikacemi pro dělení obvodů v designu VLSI“, Proc. 30. mezinárodní konference o automatizaci designu, str. 755–760, CiteSeerX  10.1.1.32.735, doi:10.1145/157485.165119, ISBN  978-0897915779.
  • Day, William H. E .; Sankoff, David (1986), „Výpočetní složitost odvození fylogenezí kompatibilitou“, Systematická zoologie, 35 (2): 224–229, doi:10.2307/2413432, JSTOR  2413432.
  • Doreian, Patrick; Woodard, Katherine L. (1994), „Definování a lokalizace jader a hranic sociálních sítí“, Sociální sítě, 16 (4): 267–293, doi:10.1016/0378-8733(94)90013-2.
  • Erdős, Paul; Szekeres, George (1935), „Kombinatorický problém v geometrii“ (PDF), Compositio Mathematica, 2: 463–470.
  • Festinger, Leon (1949), „Analýza sociogramů pomocí maticové algebry“, Lidské vztahy, 2 (2): 153–158, doi:10.1177/001872674900200205.
  • Graham, R.; Rothschild, B .; Spencer, J. H. (1990), Ramseyova teorie, New York: John Wiley and Sons, ISBN  978-0-471-50046-9.
  • Hamzaoglu, I .; Patel, J. H. (1998), "Testovací algoritmy zhutňování kombinačních obvodů", Proc. 1998 Mezinárodní konference IEEE / ACM o navrhování podporovaném počítačem, str. 283–289, doi:10.1145/288548.288615, ISBN  978-1581130089.
  • Karp, Richard M. (1972), „Reducibilita mezi kombinatorickými problémy“, Miller, R. E .; Thatcher, J. W. (eds.), Složitost počítačových výpočtů (PDF), New York: Plenum, s. 85–103.
  • Kuhl, F. S .; Crippen, G. M .; Friesen, D. K. (1983), „Kombinatorický algoritmus pro výpočet vazby ligandu“, Journal of Computational Chemistry, 5 (1): 24–34, doi:10.1002 / jcc.540050105.
  • Kuratowski, Kazimierz (1930), „Sur le problème des courbes gauches en Topologie“ (PDF), Fundamenta Mathematicae (francouzsky), 15: 271–283, doi:10,4064 / fm-15-1-271-283.
  • Luce, R. Duncan; Perry, Albert D. (1949), „Metoda maticové analýzy skupinové struktury“, Psychometrika, 14 (2): 95–116, doi:10.1007 / BF02289146, PMID  18152948.
  • Moon, J. W .; Moser, L. (1965), „O klikách v grafech“, Israel J. Math., 3: 23–28, doi:10.1007 / BF02760024, PAN  0182577.
  • Paull, M. C .; Unger, S. H. (1959), „Minimalizace počtu stavů v neúplně specifikovaných sekvenčních přepínacích funkcích“, Transakce IRE na elektronických počítačích, EC-8 (3): 356–367, doi:10.1109 / TEC.1959.5222697.
  • Peay, Edmund R. (1974), „Hierarchické klikové struktury“, Sociometrie, 37 (1): 54–65, doi:10.2307/2786466, JSTOR  2786466.
  • Prihar, Z. (1956), "Topologické vlastnosti telekomunikačních sítí", Sborník IRE, 44 (7): 927–933, doi:10.1109 / JRPROC.1956.275149.
  • Rhodos, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B .; Humblet, Christine (2003), "CLIP: vyhledávání podobnosti 3D databází pomocí detekce kliky", Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, doi:10.1021 / ci025605o, PMID  12653507.
  • Samudrala, Ram; Moult, John (1998), „Graficko-teoretický algoritmus pro srovnávací modelování proteinové struktury“, Journal of Molecular Biology, 279 (1): 287–302, CiteSeerX  10.1.1.64.8918, doi:10.1006 / jmbi.1998.1689, PMID  9636717.
  • Spirin, Victor; Mirny, Leonid A. (2003), „Proteinové komplexy a funkční moduly v molekulárních sítích“, Sborník Národní akademie věd, 100 (21): 12123–12128, doi:10.1073 / pnas.2032324100, PMC  218723, PMID  14517352.
  • Sugihara, George (1984), „Teorie grafů, homologie a potravinové sítě“, Levin, Simon A. (ed.), Populační biologie, Proc. Symp. Appl. Matematika., 30, str. 83–101.
  • Tanay, Amos; Sharan, Roded; Shamir, Ron (2002), „Objevení statisticky významných dvojčat v datech genové exprese“, Bioinformatika, 18 (Příloha 1): S136 – S144, doi:10.1093 / bioinformatika / 18.suppl_1.S136, PMID  12169541.
  • Turán, Paul (1941), „O extrémním problému v teorii grafů“, Matematikai a Fizikai Lapok (v maďarštině), 48: 436–452

externí odkazy