Problém s krytím vertexu

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é 8. května 2020; kontroly vyžadují 3 úpravy .

Problém pokrytí vrcholů je NP-úplný počítačový problém v oblasti teorie grafů . Často se používá v teorii složitosti k prokázání NP-úplnosti složitějších problémů.

Definice

Vrcholový kryt pro neorientovaný graf je množina jeho vrcholů , takže pro každou hranu grafu alespoň jeden z konců vstupuje do vrcholu z . $G=(V,E)$ $S$ $S$

Velikost vertexového krytu je počet vertexů, které obsahuje.

Příklad: Graf vpravo má pokrytí vrcholů velikosti 4. Nejedná se však o nejmenší pokrytí vrcholů, protože existují menší kryty vrcholů, jako jsou a . $\{1,3,5,6\}$ $\{2,4,5\}$ $\{1,2,4\}$

Problém pokrytí vrcholu je najít nejmenší velikost pokrytí vrcholu pro daný graf (tato velikost se nazývá krycí číslo vrcholu grafu ).

Vstup: Count .

G=(V,E)

Výsledek: množina je nejmenší vrcholový kryt grafu .

C\subseteq V

G

Otázku lze také položit jako ekvivalentní problém s řešením :

Vstup: Graf a kladné celé číslo .

G

k

Otázka: Existuje vrcholový kryt pro graf o velikosti maximálně ?

C

G

k

Problém pokrytí vrcholů je podobný problému nezávislé množiny . Protože množina vrcholů je krytím vrcholů právě tehdy, když je její doplněk nezávislou množinou, problémy se vzájemně redukují. $C$ $V\setminus C$

NP-kompletní

Protože problém pokrytí vrcholů je NP-úplný , bohužel neexistují žádné známé algoritmy pro jeho řešení v polynomiálním čase. Existují však aproximační algoritmy , které poskytují "přibližné" řešení tohoto problému v polynomiálním čase - můžete najít pokrytí vrcholů, ve kterých počet vrcholů není větší než dvojnásobek možného minima.

Jedním z prvních přístupů k vyřešení problému, který přichází na mysl, je aproximace pomocí chamtivého algoritmu : Je nutné přidávat vrcholy s maximálním počtem sousedů k pokrytí vrcholů, dokud není problém vyřešen, ale takové řešení nemá žádnou -aproximaci. pro jakoukoli konstantu . $\rho$ $\rho$

Dalším řešením je najít maximální shodu na daném grafu a zvolit množinu jako pokrytí vrcholu . Správnost takového algoritmu je dokázána rozporem: If is not vertex cover (ne nutně nejmenší), tzn. , pak nejde o maximální shodu. Aproximační faktor je dokázán takto: Nechť , kde je číslo nezávislosti grafu , a je největší shoda grafu . Pak je aproximační faktor . $M\in E$ $G=(V,E)$ $C=\bigcup _{e\in M}e$ $C$ $\exists e\colon e\cap C=\emptyset$ $M$ $\tau (G)=|V|-\alpha (G)$ $\alpha (G)$ $G$ $M_{max}(G)$ $G$ ${\frac {2\cdot |M|}{\tau (G)))\leqslant {\frac {2\cdot |M_{max}(G)|}{\tau (G)))\ leqslant {\frac {2\cdot |M_{max}(G)|}{|M_{max}(G)|}}=2$

Obecně lze problém pokrytí vrcholů aproximovat faktorem . $2-{\frac {\log \log n}{2\cdot \log n))$

Problém pokrytí vrcholů v bipartitních grafech

V bipartitních grafech je problém pokrytí vrcholů řešitelný v polynomiálním čase, protože se redukuje na největší problém shody ( Königův teorém ).

Odkazy

Literatura

Thomas H. Kormen a kol. , Kapitola 36. NP-úplnost // Algoritmy: Konstrukce a analýza = ÚVOD DO ALGORITHMŮ. - 1. vyd. - M. : Moskevské centrum pro kontinuální matematické vzdělávání, 2001. - S. 866.

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