Ugrás a tartalomhoz

Körlefogó csúcshalmaz

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

A matematika, azon belül a gráfelmélet területén egy gráf körlefogó csúcshalmaza vagy körlefogó ponthalmaza (feedback vertex set) a gráf csúcsainak olyan halmaza, melyek eltávolításával a gráf kör nélkül marad. Más szavakkal, a körlefogó csúcshalmaz a gráf minden körének legalább egy csúcsát tartalmazza. A körlefogó csúcshalmaz problémája a számítási bonyolultságelmélet szerint NP-teljes probléma, méghozzá az első problémák között volt, amiről ezt megmutatták. Széles körben alkalmazzák operációs rendszerek, adatbázisok és VLSI-csipek tervezésében.

Definíció

[szerkesztés]

Az eldöntési probléma a következő:

PÉLDÁNY: Egy (irányított vagy irányítatlan) gráf, és ez pozitív egész szám.
KÉRDÉS: Létezik-e olyan részhalmaz, melyre és -ből csúcsainak törlésével kapott gráf körmentes?

A gráf, amit -ből való eltávolításával kapunk, egy feszített erdő (illetve irányított gráfok esetén, irányított körmentes gráf). Így egy gráf körlefogó csúcshalmazának megkeresése ekvivalens maximális feszített erdőjének (illetve maximális feszített irányított körmentes gráfjának) megkeresésével.

NP-nehézség

[szerkesztés]

(Karp 1972) megmutatta, hogy a körlefogó csúcshalmaz problémája irányított gráfok esetén NP-teljes. A probléma szintén NP-teljes olyan irányított gráfokon, melyek maximális be-foka és ki-foka kettő, illetve irányított síkbarajzolható gráfokon, melyek maximális ki- és be-foka három.[1] A Karp-redukcióból következik továbbá a körlefogó csúcshalmaz-probléma NP-teljességét irányítatlan gráfokon, ahol a probléma NP-nehéz marad még négy maximális fokszámú gráfokon is; ellenben polinom időben megoldható három maximális fokszámú gráfok esetében.[2]

Vegyük észre, hogy a lehető legkevesebb él törlésével körmentessé alakítás ekvivalens a gráf feszítőfájának megkeresésével, ami polinom időben elvégezhető. Kontrasztként, az irányított gráf lehető legkevesebb él törlésével körmentessé alakítása, a körlefogó irányított élhalmaz-probléma (feedback arc set), NP-nehéz.[3]

Egzakt algoritmusok

[szerkesztés]

A minimális méretű körlefogó csúcshalmaz NP-optimalizálási problémája O(1,7347n) időben megoldható, ahol n a gráf csúcsainak száma.[4] Ez az algoritmus ténylegesen kiszámítja a maximális feszített erdőt, majd annak komplementereként állítja elő a minimális körlefogó csúcshalmazt. Egy gráf minimális körlefogó csúcshalmazainak száma legfeljebb O(1,8638n).[5] Az irányított eset O*(1,9977n) időben megoldható, ahol n szintén az irányított gráf csúcsainak száma.[6] Mind az irányított, mind az irányítatlan eset parametrizált változata rögzített paraméter mellett kezelhető.[7]

Maximálisan 3 fokszámú irányítatlan gráfokban a probléma polinom időben megoldható, a lineáris matroidok matroidparitás-problémájára átalakítva.[8]

Approximáció

[szerkesztés]

A probléma APX-teljes, ami közvetlen következménye a csúcslefedés-probléma APX-teljességének,[9] és a csúcslefedés-probléma és a körlefogó csúcshalmaz-probléma közötti approximációtartó L-redukció létezésének.[3] Irányítatlan gráfoknál a legjobb ismert approximációs arány 2 faktorú.[10]

Korlátok

[szerkesztés]

Az Erdős–Pósa-tétel szerint a minimális körlefogó csúcshalmaz mérete az adott gráf csúcsdiszjunkt köreinek maximális számának logaritmikus faktora lehet.[11]

Alkalmazások

[szerkesztés]

Operációs rendszerekben a körlefogó csúcshalmazok a holtponti helyzetből (deadlockból) való visszatérésben játszanak szerepet. Az operációs rendszer várakozási gráfjának minden irányított köre egy holtponti helyzetnek felel meg. Az összes deadlock feloldásához egyes blokkolt folyamatokat meg kell szakítani. Ennek a gráfnak a minimális körlefogó csúcshalmaza a megszakítandó folyamatok minimális számának felel meg.[12]

Ezen túl, a körlefogó csúcshalmaz-probléma a VLSI csipek tervezésében is szerephez jut.[13]

Jegyzetek

[szerkesztés]

Fordítás

[szerkesztés]
  • Ez a szócikk részben vagy egészben a Feedback vertex set című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Irodalom

[szerkesztés]

Kutatási cikkek

[szerkesztés]

Tankönyvek és áttekintő cikkek

[szerkesztés]