Klikněte na problém

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é 27. listopadu 2019; kontroly vyžadují 4 úpravy .

Problém kliky patří do třídy NP-úplných problémů v oblasti teorie grafů . Poprvé byl formulován v roce 1972 Richardem Karpem . [jeden]

Klika v neorientovaném grafu je podmnožina vrcholů, z nichž každý je spojen hranou grafu. Jinými slovy, je to úplný podgraf původního grafu. Velikost kliky je definována jako počet vrcholů v ní. Problém kliky existuje ve dvou verzích: v problému rozpoznávání je třeba určit, zda v daném grafu G existujeklika o velikosti k , zatímco ve výpočtové variantě je třeba najítkliku o maximální velikosti v grafu. daný graf G.

NP-kompletní

NP-úplnost problému kliky vyplývá z NP-úplnosti problému nezávislé množiny vrcholů. Je snadné ukázat, že nezbytnou a postačující podmínkou pro existenci kliky o velikosti k je přítomnost nezávislé množiny o velikosti alespoň k v doplňku grafu. To je zřejmé, protože úplnost podgrafu znamená, že jeho doplněk neobsahuje žádné hrany.

Další důkaz NP-úplnosti lze nalézt v Algorithms: Construction and Analysis. [2]

Algoritmy

Stejně jako u jiných NP-úplných problémů nebyl dosud nalezen účinný algoritmus pro nalezení kliky dané velikosti. Vyčerpávající prohledávání všech možných podgrafů o velikosti k a kontrola, zda je alespoň jeden z nich úplný, je neefektivní, protože celkový počet takových podgrafů v grafu s vrcholy v se rovná binomickému koeficientu. ${v \choose k} = \frac{v!}{k!(vk)!}.$

Další algoritmus funguje takto: dvě kliky o velikosti n a m jsou „slepeny“ do velké kliky o velikosti n + m a samostatný vrchol grafu se považuje za kliku o velikosti 1 . Algoritmus se ukončí, jakmile nelze provést žádné další sloučení. Doba běhu tohoto algoritmu je lineární, ale je heuristická , protože ne vždy vede k nalezení kliky o maximální velikosti. Příkladem neúspěšného dokončení je případ, kdy jsou vrcholy patřící do maximální kliky odděleny a jsou v menších klikách a ty již nelze „slepit“ dohromady.

Je dokázáno, že za podmínky nerovnosti tříd P a NP neexistuje žádný polynomiální aproximační algoritmus s absolutní chybou rovnou libovolné . Uvažujme graf u - přímý součin grafu a kliky velikosti . Je zřejmé, že klikací číslo grafu se bude rovnat . Předpokládejme, že existuje aproximační algoritmus s absolutní chybou rovnou . Poté zavedeme graf jako vstup a za podmínky dostaneme . Nechť jsou kliky grafů ve tvaru , kde . Poznamenejte si platnost nerovnosti a dosaďte ji do výše uvedené nerovnosti následovně: . Po transformaci dostaneme , což znamená, že existuje taková, že a tedy kliková úloha je řešitelná v polynomiálním čase, což je v rozporu s podmínkou nerovnosti pro třídy P a NP. $k\in {\mathbb {N}}$ $G$ ${\displaystyle G^{k}=G\times C_{k))$ $G$ $C_{k}$ $k$ $G^{k}$ $\omega (G^{k})=\omega (G)\cdot k$ $A$ $k\in {\mathbb {N}}$ $A$ $G^{k+1}$ $OPT\leqslant A(I)+k$ $\omega (G^{k+1})-A(G^{k+1})=(k+1)\cdot \omega (G)-A(G^{k+1})\ leqslant k$ $C_{i}$ $G^{i}$ $1\leqslant i\leqslant k+1$ $C_{i}\leqslant \omega (G)$ $(k+1)\cdot \omega (G)-\sum _{i=1}^{k+1}|C_{i}|\leqslant k$ $\sum _{i=1}^{k+1}\omega (G)-|C_{i}|\leqslant k$ $i$ $C_{i}=\omega (G)$

Viz také

Bron-Kerboshův algoritmus - rychlé nalezení všech klik

Poznámky

↑ Karp, Richard (1972). „Redukovatelnost mezi kombinatorickými problémy“ (PDF) . Sborník příspěvků ze sympozia o složitosti počítačových výpočtů . Plenum Press. Archivováno z originálu (PDF) dne 29.06.2011 . Získáno 21. 3. 2010 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Literatura

Cook, Stephen A. (1971). „Složitost postupů dokazování teorémů“ . Sborník příspěvků ze třetího výročního sympozia ACM o teorii výpočetní techniky . Shaker Heights, Ohio. str. 151–158. Archivováno z originálu dne 2006-05-03 . Získáno 2007-06-11 . Použitý zastaralý parametr |deadlink=( nápověda ) Archivováno 3. května 2006 na Wayback Machine
Garey, Michael R. & Johnson, David S. (1979), Počítače a nepoddajnost: Průvodce teorií NP-úplnosti , W. H. Freeman, ISBN 0-7167-1045-5 A1.2: GT19, str. 194.

Odkazy

Náročné měřítka pro maximální klikání, maximální nezávislou sadu, minimální krytí vertexu a zbarvení vertexu

NP-úplné problémy
Maximalizační problém stohování (balení)	Balení v kontejnerech dvourozměrné balení lineární balení balení podle hmotnosti balení podle hodnoty Problém s batohem
teorie grafů teorie množin	Problém s krytím vertexu Klikněte na problém Problém nezávislé množiny (množiny) Nastavit problém s krytím Steinerův problém Problém cestujícího prodejce Obecný problém cestujícího prodejce
Algoritmické problémy	Problém splnitelnosti pro booleovské vzorce (v konjunktivní normální formě)
Logické hry a hádanky	Generalizované značky (hra v N 2 -1) problém s nejkratším řešením Problémy, jejichž řešení jsou aplikována v Tetrisu Generalizovaný problém sudoku Problém vyplňování latinského čtverce Kakurův úkol
Třídy obtížnosti Operační výzkum Optimalizace Kombinatorická optimalizace Aplikovaná matematika Teorie algoritmů Dynamické programování 21 NP-úplný Karp problém