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

Graf s

• 23 × 1 vrchol kliky (vrcholy),
• Kliky 42 × 2 vrcholy (okraje),
• 19 × 3 vrcholové kliky (světlé 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ě tmavě modré 4 kliky jsou maximální i maximální a klikové číslo grafu je 4.

V matematickém oblasti teorie grafů , je klika ( / k l jsem k / nebo / k l ɪ k / ) je podmnožinou vrcholech undirected grafu tak, že každé dva různé vrcholy v klika vedle sebe. To znamená, že klika grafu je indukovaná podgrafem ze které je dokončena . 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 na grafech. Kliky byly také studovány v informatice${\ displaystyle G}$${\ displaystyle G}$: úkol zjistit, zda je v grafu klika dané velikosti ( problém kliky ), je NP-úplný , ale i přes tento výsledek tvrdosti bylo studováno mnoho algoritmů pro hledání klik.

I když studie o celých podgrafy sahá přinejmenším do grafu-teoretické reformulaci teorie Ramsey od Erdős a Szekeres (1935) , termín klika pochází z Luce & Perry (1949) , který použil kompletní subgraphs v sociálních sítích na modelových klik z lidé; tj. skupiny lidí, z nichž se všichni navzájem znají. Cliques mají mnoho dalších aplikací ve vědách a zejména v bioinformatice .

Definice

Klika , , v undirected grafu je podmnožinou vrcholů , tak, že každé dva odlišné vrcholy jsou vedle sebe. To je ekvivalentní podmínky, že indukovaná podgrafem z vyvolaná je úplný graf . V některých případech může termín klika také odkazovat přímo na podgraf. ${\ displaystyle C}$ ${\ displaystyle G = (V, E)}$${\ Displaystyle C \ subseteq V}$${\ displaystyle G}$${\ displaystyle C}$

Maximální klika je klika, která nemůže být prodloužena tím, že zahrnuje jednu sousední vrchol, to znamená, je klika, která neexistuje výhradně v vrcholu sady většího kliky. Někteří autoři definují kliky způsobem, který vyžaduje, aby byly maximální, a pro úplné podgrafy, které nejsou maximální, používají jinou terminologii.

Maximální klika grafu, je klika, takže není klika s více vrcholy. Navíc klikové číslo grafu je počet vrcholů v maximální klice v . ${\ displaystyle G}$ ${\ displaystyle \ omega (G)}$${\ displaystyle G}$${\ displaystyle G}$

Počet křižovatka of je nejmenší počet klik, které dohromady pokrývají všechny hrany . ${\ displaystyle G}$${\ displaystyle G}$

Číslo obalu kliky grafu je nejmenší počet kliků, jejichž sjednocení pokrývá množinu vrcholů grafu. ${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle V}$

Maximální klika příčná grafu je podmnožinou vrcholů s vlastností, že každé maximální klika grafu obsahuje alespoň jeden vrchol v podskupině.

Opakem kliky je nezávislá množina v tom smyslu, že každá klika odpovídá nezávislé sadě v grafu komplementu . Problém obalu kliky se týká nalezení co nejméně klik, které zahrnují každý vrchol v grafu.

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

Matematika

Mezi matematické výsledky týkající se klik patří následující.

• Turánova věta udává dolní mez velikosti kliky v hustých grafech . Pokud má graf dostatečně mnoho hran, musí obsahovat velkou kliku. Například každý graf s vrcholy a více než hranami musí obsahovat kliku se třemi vrcholy.${\ displaystyle n}$${\ Displaystyle \ scriptstyle \ lfloor {\ frac {n} {2}} \ rfloor \ cdot \ lceil {\ frac {n} {2}} \ rceil}$
• Ramseyova věta uvádí, že každý graf nebo jeho graf komplementu obsahuje kliku s alespoň logaritmickým počtem vrcholů.
• Podle výsledku Moon & Moser (1965) může mít graf se 3 n vrcholy nejvýše 3 ⁿ maximální kliky. Grafy splňující tuto hranici jsou Moon -Moserovy grafy K _{3,3, ...} , zvláštní případ turánských grafů vznikajících jako extrémní případy v Turánově větě.
• Hadwiger dohad , ještě nevyzkoušené, se týká velikosti největší kliky moll v grafu (jeho Hadwiger číslo ) k jeho barevnosti .
• Erdős-Faber-Lovász domněnka je další neprokázané tvrzení týkající barvení grafu na klik.

Jejich kliky lze definovat nebo charakterizovat několik důležitých tříd grafů:

• Clusteru graf je graf, jehož připojená zařízení jsou kliky.
• Blok graf je graf, jehož biconnected komponenty jsou kliky.
• Chordal graf je graf, jehož vrcholy je možné objednat do dokonalého odstranění uspořádání, uspořádání tak, že sousedi z každého vrcholu V , které přijdou později než objem v uspořádání tvoří kliku.
• Cograph je graf všech jehož indukované podgrafy mají tu vlastnost, že každá maximální klika protíná jakýkoli maximální nezávislé nastavení v jednom vrcholu.
• Interval graf je graf, jehož maximální kliky je možné objednat takovým způsobem, že pro každý vrchol V , jsou kliky s obsahem V následující za sebou v uspořádání.
• Čárový graf je graf, jehož hrany může být pokryta hran disjunktní klik takovým způsobem, že každý vrchol patří do přesně dva z klik v krytu.
• Perfektní graf je graf, ve kterém klika číslo rovná barevnost v každém vyvolané subgrafu .
• Dělená graf je graf, ve kterém některé klika obsahuje alespoň jeden koncový bod každé hrany.
• Trojúhelník bez graf je graf, který nemá žádné jiné než jeho vrcholů a hran kliky.

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

• Klika komplex grafu G je abstraktní simplicial komplex X ( G ) s simplexní pro každý kliky v G
• Simplex graf je neorientovaný graf κ ( G ) s vrcholem pro každý kliky v grafu G a okraje spojující dvě kliky, které se liší od jednoho vrcholu. Je to příklad mediánu grafu a je spojen se střední algebrou na klikách grafu: medián m ( A , B , C ) tří klik A , B a C je klika, jejíž vrcholy patří alespoň dva z klik , B a C .
• Klika součtem je způsob kombinací dvou grafů jejich sloučením podél společné klika.
• Šířka kliky je pojem složitosti grafu z hlediska minimálního počtu odlišných štítků vrcholů potřebných k sestavení grafu z disjunktních svazků, operací relabelingu a operací, které spojují všechny páry vrcholů s danými popisky. Grafy s klikou o šířce kliky jsou přesně nesouvislými svazky klik.
• Počet průsečík grafu je minimální počet klik potřebných k pokrytí všech hran grafu.
• Klika grafu grafu je křižovatka graf svých maximálních klik.

Úzce související pojmy s úplnými podgrafy jsou pododdělení celých grafů a úplných nezletilých grafů . Zejména Kuratowského věta a Wagner teorém charakterizují plošné grafy o zakázaných úplných a kompletní bipartitní třídění a mladistvých, resp.

Počítačová věda

V počítačové vědě je problémem kliky výpočetní problém nalezení maximální kliky nebo všech klik v daném grafu. Je to NP-Complete , jeden z Karpových 21 NP-kompletních problémů . Je také neřešitelný s pevnými parametry a je těžké jej přiblížit . Přesto bylo vyvinuto mnoho algoritmů pro výpočetní kliky, buď běžících v exponenciálním čase (například Bron -Kerboschův algoritmus ), nebo specializovaných na rodiny grafů, jako jsou planární grafy nebo dokonalé grafy, u nichž lze problém vyřešit v polynomiálním čase .

Aplikace

Slovo „klika“ ve svém graficko-teoretickém použití vzniklo z díla Luce & Perryho (1949) , který pomocí kompletních podgrafů modeloval kliky (skupiny lidí, kteří se všichni navzájem znají) v sociálních sítích . Stejnou definici použil Festinger (1949) v článku s použitím méně odborných výrazů. Obě díla pojednávají o odkrývání klik v sociální síti pomocí matic. Pokračující úsilí o teoretické modelování sociálních klik viz např. Alba (1973) , Peay (1974) a Doreian & Woodard (1994) .

Mnoho různých problémů z bioinformatiky bylo modelováno pomocí kliků. Například Ben-Dor, Shamir & Yakhini (1999) modelují problém shlukování dat genové exprese jako jeden z 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) diskutují o podobném problému s dvojitým shlukováním dat exprese, ve kterých musí být klastry kliky. Sugihara (1984) používá kliky k modelování ekologických mezer v potravních sítích . Day & Sankoff (1986) popisují problém odvozování evolučních stromů 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 kombinující tyto dva znaky. Samudrala & Moult (1998) modelují predikci struktury proteinu jako problém hledání klik v grafu, jehož vrcholy představují polohy podjednotek proteinu. A hledáním kliků v interakční síti protein-protein našli Spirin & Mirny (2003) shluky proteinů, které spolu úzce interagují a mají málo interakcí s proteiny mimo klastr. Analýza výkonových grafů 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 elektrotechnice , Prihar (1956) používá k analýze kliky komunikační sítě, a Paull & Unger (1959), použít je navrhnout efektivní obvody pro výpočet částečně uvedených logických funkcí. Při generování automatického testovacího vzoru byly použity také kliky: velká klika v grafu nekompatibility možných poruch poskytuje dolní mez velikosti testovací sady. Cong & Smith (1993) popisují aplikaci klik při hledání hierarchického rozdělení elektronického obvodu na menší podjednotky.

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

Viz také

• Kliková hra

Poznámky

Reference

externí odkazy

• Weisstein, Eric W. , „Clique“ , MathWorld
• Weisstein, Eric W. , „Clique Number“ , MathWorld