Csúcsborítási probléma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. május 8-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A csúcsfedő probléma egy NP-teljes számítástechnikai probléma a gráfelmélet területén . A komplexitáselméletben gyakran használják összetettebb problémák NP-teljességének bizonyítására.

Definíció

Az irányítatlan gráf csúcsfedezete a csúcsok halmaza , úgy, hogy a gráf minden éléhez legalább az egyik vége a csúcsba lép be . $G=(V,E)$ $S$ $S$

Egy csúcsfedő mérete a benne lévő csúcsok száma.

Példa: A jobb oldali gráfnak van egy 4-es méretű csúcsfedője. Ez azonban nem a legkisebb csúcsfedő, mert vannak kisebb csúcsfedők, mint pl . $\{1,3,5,6\}$ $\{2,4,5\}$ $\{1,2,4\}$

A csúcsfedő probléma az, hogy meg kell találni a legkisebb méretű csúcsfedőt egy adott gráfhoz (ezt a méretet a gráf csúcsborítószámának nevezzük ) .

Belépés: gróf .

G=(V,E)

Eredmény: a halmaz a gráf legkisebb csúcsa .

C\subseteq V

G

A kérdést feltehetjük egyenértékű megoldási problémaként is :

Bemenet: Grafikon és pozitív egész szám .

G

k

Kérdés: Van-e csúcsfedő egy legfeljebb méretű gráfhoz ?

C

G

k

A csúcsfedő probléma hasonló a független halmazfeladathoz . Mivel egy csúcshalmaz akkor és csak akkor csúcsfedő, ha komplementere független halmaz, a problémák egymásra redukálódnak. $C$ $V\setminus C$

NP-teljes

Mivel a csúcsfedő probléma NP-teljes , ezért sajnos nem ismertek algoritmusok a polinomiális időben történő megoldására. Léteznek azonban olyan közelítő algoritmusok , amelyek polinomiális időben "közelítő" megoldást adnak erre a problémára – találhatunk olyan csúcsfedőt, amelyben a csúcsok száma nem haladja meg a lehetséges minimum kétszeresét.

A probléma megoldásának egyik első megközelítése, ami eszünkbe jut, a közelítés a mohó algoritmuson keresztül : Maximum szomszédos csúcsokat kell hozzáadni a csúcsfedőhöz, amíg a probléma meg nem oldódik, de egy ilyen megoldásnak nincs -közelítése . bármely állandóhoz . $\rho$ $\rho$

Egy másik megoldás az, hogy az adott gráfon megtaláljuk a maximális illeszkedést , és a halmazt választjuk csúcsfedőnek . Egy ilyen algoritmus helyességét ellentmondás bizonyítja: Ha nem csúcsfedő (nem feltétlenül a legkisebb), azaz. , akkor ez nem maximális egyezés. A közelítési tényezőt a következőképpen bizonyítjuk: Legyen , ahol a gráf függetlenségi száma , és a gráf legnagyobb illeszkedése . Ekkor a közelítési tényező . $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$

Általában a csúcsfedő probléma egy tényezővel közelíthető . $2-{\frac {\log \log n}{2\cdot \log n))$

A csúcslefedési probléma bipartit gráfokban

Bipartit gráfokban a csúcsfedési probléma megoldható polinomiális időben, mivel redukálódik a legnagyobb illesztési problémára ( König tétele ).

Linkek

Irodalom

Thomas H. Kormen és munkatársai 36. fejezet NP-teljesség // Algoritmusok: Konstrukció és elemzés = BEVEZETÉS AZ ALGORITMUSOKBA. - 1. kiadás - M. : Moszkvai Matematikai Folyamatos Oktatási Központ, 2001. - 866. o.

NP-teljes problémák
A halmozás (csomagolás) maximalizálási problémája	Csomagolás konténerekbe kétdimenziós csomagolás lineáris csomagolás súly szerinti csomagolás érték szerinti csomagolás A hátizsák probléma
gráfelmélet halmazelmélet	Csúcsborítási probléma Kattintson a probléma Egy független halmaz (halmaz) problémája Állítsa be a fedési problémát Steiner probléma Az utazó eladó probléma Általános utazó eladó probléma
Algoritmikus problémák	Kielégíthetőségi probléma Boole-képleteknél (konjunktív normál formában)
Logikai játékok és rejtvények	Általános címkék (játék N 2 -1-ben) legrövidebb megoldási probléma Problémák, amelyek megoldásait a Tetrisben alkalmazzák Általános Sudoku probléma Latin négyzet kitöltési probléma Kakuro feladata
Nehézségi osztályok Operációkutatás Optimalizálás Kombinatorikus optimalizálás Alkalmazott matematika Algoritmusok elmélete Dinamikus programozás 21 NP-teljes Karp probléma