Feszített út

Négy hosszúságú feszített út egy kockában. A snake-in-the-box („kígyó a dobozban”) probléma a hiperkockagráfok leghosszabb feszített útjaival foglalkozik

A matematika, azon belül a gráfelmélet területén egy G irányítatlan gráfban egy feszített út (induced path) olyan út, mely G-nek feszített részgráfja. Tehát G-beli csúcsok sorozata, melynek egymást követő csúcsai G-ben éllel vannak összekötve, egymást nem követő csúcsai viszont nincsenek G-ben éllel összekötve. A feszített utat angol nyelvterületen néha kígyónak, snake-nek is nevezik, a hiperkockagráfban hosszú feszített utak keresésének problémáját ezért snake-in-the-box problémának hívják.

Hasonlóan a feszített kör (induced cycle) olyan kör, ami G feszített részgráfja; a feszített köröket húrmentes körnek (chordless cycles) vagy (ha a kör legalább 4 hosszúságú) lyuknak (hole) nevezik. Egy antilyuk (antihole) a G komplementerében lévő lyuk, tehát az antilyuk a lyuk komplementere.

Egy gráf leghosszabb feszített útjának hosszát néha detour-számnak (detour number, kb. „kerülőút-szám” vagy „kitérőút-szám”) is nevezik; ritka gráfokon a korlátos detour-szám a korlátos famélységgel ekvivalens. Egy G gráf feszítettút-száma (induced path number) az a legkevesebb partíció, amibe G csúcsai szétoszthatók úgy, hogy mindegyik partícióban egy-egy feszített út legyen, a szorosan kapcsolódó útfedési szám (path cover number) pedig a G összes csúcsát tartalmazó feszített utak minimális száma. Egy gráf girthparamétere (derékbősége) a legrövidebb körének hossza, ez a kör viszont mindenképpen feszített kör, hiszen bármely rajta lévő húr segítségével egy rövidebb kört lehetne előállítani. Hasonló okból egy gráf páratlan, illetve páros bősége egyben a gráf legkisebb páratlan, illetve páros feszített köre.

Példa

Az ábrán egy kocka látható, vagyis egy 8 csúcs és 12 él alkotta gráf, benne egy 4 hosszúságú feszített úttal. Egyszerű esetvizsgálattal belátható, hogy ennél hosszabb feszített út nincs a kockában, annak ellenére, hogy 6 hosszúságú feszített kör viszont van. A leghosszabb feszített út vagy feszített kör megkeresését egy hiperkockában, azaz a snake-in-the-box problémát elsőként (Kautz 1958) vetette fel, azóta széles körben tanulmányozták kódoláselméleti és mérnöki alkalmazásai miatt.

Gráfcsaládok jellemzése

Számos fontos gráfcsalád jellemezhető a család gráfjainak feszített útjai vagy feszített körei alapján.

• Trivális, hogy az összefüggő gráfok közül a 2 él hosszúságú feszített úttal nem rendelkezők éppen a teljes gráfok, a feszített körrel nem rendelkezők pedig a fák.
• A háromszögmentes gráfok azok a gráfok, melyek nem tartalmaznak 3 él hosszúságú feszített kört.
• A kográfok azok a gráfok, melyek nem tartalmaznak 3 él hosszúságú feszített utat.
• A merev körű gráfok azok a gráfok, melyek nem tartalmaznak 4 vagy nagyobb hosszú feszített kört.
• A pároskör-mentes gráfok azok a gráfok, melyek nem tartalmaznak páros számú csúcsból álló feszített kört.
• A triviálisan perfekt gráfok azok a gráfok, melyek nem tartalmaznak se 3 él hosszú feszített utat, se 4 hosszú feszített kört.
• Az erős perfektgráf-tétel értelmében a perfekt gráfok azok a gráfok, melyek nem tartalmaznak se páratlan lyukat, se páratlan antilyukat.
• A távolság-örökletes gráfok azok a gráfok, melyekben minden feszített út legrövidebb út, és így két csúcs között minden feszített út azonos hosszúságú.
• A blokkgráfok azok a gráfok, melyek bármely két csúcsa között legfeljebb egy feszített út van, az összefüggő blokkgráfok esetében pedig pontosan egy.

Algoritmusok és számítási bonyolultság

NP-teljes feladat annak eldöntése, hogy adott G gráf k paraméterre vajon tartalmaz-e legalább k hosszúságú feszített utat. (Garey & Johnson 1979) ezt az eredményt Mihalis Yannakakisszal való publikálatlan kommunikációjának tulajdonítja. A probléma azonban bizonyos gráfcsaládokon polinom időben megoldható, ilyenek az aszteroidszerű hármas-mentes gráfok (AT-free) és a nagy lyukakat nem tartalmazó gráfok.

Szintén NP-teljes annak meghatározása, hogy egy gráf csúcsai feloszthatók-e két feszített útba vagy két feszített körbe. Ennek következményeként a feszítettút-szám meghatározása NP-nehéz.

A leghosszabb feszített út vagy feszített kör megkeresésének bonyolultsága összekapcsolható a legnagyobb független csúcshalmaz keresésének problémájával, a Berman és Schnitger által alkalmazott redukcióval. Ez alapján és (Håstad 1996) a független csúcshalmazok approximálhatóságára vonatkozó negatív eredménye miatt, ha nem igaz, hogy NP=ZPP, akkor nem létezik a leghosszabb feszített utat vagy feszített kört approximáló polinom idejű algoritmus, ami O(n^1/2-ε) faktorral közelíti meg az optimális megoldást.

Az n csúccsal és m éllel rendelkező gráfban a lyukakat (és antilyukakat, ha nincs a gráfban 5 hosszúságú húrmentes kör) (n+m²) időben lehet detektálni.

Atomi körök

Az atomi körök (atomic cycles) a húrmentes körök általánosításai, melyek nem tartalmaznak n-húrokat. Adott körre egy n-húr a kör két pontját összekötő, n hosszúságú út, ahol n kisebb mint ezt a két pontot a körön belül összekötő legrövidebb út. Ha egy kör nem rendelkezik n-húrral, atomi körnek nevezzük, mivel nem lehet kisebb körökre felbontani. Egy gráf atomi köreit legrosszabb esetben O(m²) időben meg lehet keresni, ahol m a gráf éleinek száma.

Fordítás

• Ez a szócikk részben vagy egészben az Induced path 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.

Jegyzetek

• (2004) „Computation of minimal rank and path cover number for certain graphs”. Linear Algebra Appl. 392, 289–303. o. DOI:10.1016/j.laa.2004.06.019. 
• (1992) „On the complexity of approximating the independent set problem”. Information and Computation 96 (1), 77–94. o. DOI:10.1016/0890-5401(92)90056-L. 
• (1988) „On longest induced paths in graphs”. Chinese Quart. J. Math. 3 (3), 61–65. o. 
• (1994) „The induced path number of bipartite graphs”. Ars Combin. 37, 191–208. o. 
• Computers and Intractability: A Guide to the Theory of NP-Completeness.. W. H. Freeman, 196. o. (1979) 
• Gashler, Michael (2012). „Robust manifold learning with CycleCut”. Connection Science 24, 57–69. o. DOI:10.1080/09540091.2012.664122. 
• Gavril, Fănică (2002). „Algorithms for maximum weight induced paths”. Information Processing Letters 81 (4), 203–208. o. DOI:10.1016/S0020-0190(01)00222-8. 
• Håstad, Johan (1996). „Clique is hard to approximate within n^1−ε”. Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science: 627–636. doi:10.1109/SFCS.1996.548522. 
• Kautz, W. H. (1958). „Unit-distance error-checking codes”. IRE Trans. Elect. Comput. 7, 177–180. o. 
• (2003) „Feedback vertex set and longest induced path on AT-free graphs”. Graph-theoretic concepts in computer science: 309–321, Berlin: Lecture Notes in Computer Science, Vol. 2880, Springer-Verlag. [2006. november 25-i dátummal az eredetiből archiválva]. doi:10.1007/b93953. Hozzáférés: 2018. január 3. 
• (2003) „Splitting a graph into disjoint induced paths or cycles” (The Second International Colloquium "Journées de l'Informatique Messine", Metz, 2000). Discrete Appl. Math. 131 (1), 199–212. o. [2016. március 3-i dátummal az eredetiből archiválva]. DOI:10.1016/S0166-218X(02)00425-0. (Hozzáférés: 2018. január 3.) 
• Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics. Heidelberg: Springer, 115–144. o.. DOI: 10.1007/978-3-642-27875-4 (2012). ISBN 978-3-642-27874-7 
• (2004) „Hole and antihole detection in graphs”. Proc. 15th ACM-SIAM Symposium on Discrete Algorithms: 850–859.