PROFILPELAJAR.COM

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;^[1] ritka gráfokon a korlátos detour-szám a korlátos famélységgel ekvivalens.^[2] 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,^[3] 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.^[4] 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)^[5] és a nagy lyukakat nem tartalmazó gráfok.^[6]

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.^[7] 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.^[8] 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.^[9]

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.^[10] 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

↑ (Buckley & Harary 1988).
↑ (Nešetřil & Ossona de Mendez 2012), Proposition 6.4, p. 122.
↑ (Chartrand et al. 1994).
↑ (Barioli, Fallat & Hogben 2004).
↑ (Kratsch, Müller & Todinca 2003).
↑ (Gavril 2002).
↑ (Le, Le & Müller 2003).
↑ (Berman & Schnitger 1992).
↑ (Nikolopoulos & Palios 2004).
↑ (Gashler & Martinez 2012).

(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.