Pánciklikus gráf
A matematika, azon belül a gráfelmélet területén egy pánciklikus gráf (pancyclic graph) olyan akár irányított, akár irányítatlan gráf, melyben minden lehetséges körhosszúság előfordul háromtól a gráf csúcsainak számáig.[1] A pánciklikus gráfok a maximálisan lehetséges hosszúságú, ún. Hamilton-körrel rendelkező gráfok általánosításai.
Definíciók
[szerkesztés]Az n csúcsú G gráf akkor pánciklikus, ha 3 ≤ k ≤ n G minden k-ra tartalmaz k hosszúságú kört.[1] Csúcs-pánciklikus (node-pancyclic vagy vertex-pancyclic) ha minden v csúcsra és az előbb említett k értékekre a gráf tartalmaz olyan k hosszúságú köröket, melyek része v.[2] Hasonlóan, él-pánciklikus (edge-pancyclic), ha minden e élre és az előbb említett k értékekre a gráf tartalmaz olyan k hosszúságú köröket, melyek része e.[2]
Páros gráf nem lehet pánciklikus, hiszen egyáltalán nem tartalmaz páratlan hosszúságú köröket, de lehet bipánciklikus (bipancyclic), ha 4-től n-ig minden páros hosszúságú kör előfordul benne.[3]
Síkbarajzolható gráfok
[szerkesztés]Egy maximális külsíkgráf olyan gráf, ami a sík egyszerű sokszöge belsejének háromszögekre bontásával előállítható. Indukcióval belátható, hogy minden maximális külsíkgráf pánciklikus. A gráf külső tartománya egy n csúcsú kör, és egy olyan háromszög eltávolításával, ami a gráf maradékához csak egy éllel csatlakozik (a háromszögelés duális gráfját alkotó fa egy levele) eggyel kevesebb csúcsból álló maximális külsíkgráf jön létre, ami az indukció szerint az összes maradék hosszúságú kört tartalmazza. Az eltávolítandó háromszög elővigyázatos megválasztásával, ugyanezen az elven belátható az is, hogy minden maximális külsíkgráf csúcs-pánciklikus.[4] Ugyanez igaz azokra a gráfokra, melyek rendelkeznek maximális outerplanáris feszítő részgráffal, mint például a kerékgráfok.
Egy maximális síkbarajzolható gráfban a külsőt is beleértve minden tartományt háromszögek alkotnak. Egy maximális síkbarajzolható gráf pontosan akkor csúcs-pánciklikus, ha van Hamilton-köre:[5] Ha nincs Hamilton-köre, nyilvánvalóan nem pánciklikus, ha van neki, akkor a Hamilton-kör belseje ugyanazokon a csúcsokon maximális külsíkgráfot alkot, amire alkalmazni lehet a maximális külsíkgráfokra vonatkozó korábbi okfejtést.[6] Például az illusztráción látható pánciklikus oktaéder is egy Hamilton-körrel rendelkező maximális síkbarajzolható gráf, hat csúccsal. Erősebb állítás, ugyanazon érvelés alapján, hogy ha egy maximális síkbarajzolható gráfnak van k hosszúságú köre, akkor rendelkezik az összes kisebb hosszúságú körrel is.[7]
A Halin-gráfok olyan síkbarajzolható gráfok, melyek egy kettő fokszámú csúcsot nem tartalmazó fa leveleinek körré történő összehúzásával állíthatók elő. A Halin-gráfok nem minden esetben pánciklikusak, viszont csaknem pánciklikusak abban az értelemben, hogy legfeljebb egy, minden esetben páros körhosszúság hiányozhat belőlük. Ha a Halin-gráf belső csúcsai közül egyiknek sem három a fokszáma, akkor szükségképpen pánciklikus.[8]
(Bondy 1971) megfigyelése szerint a Hamilton-kör létezésének klasszikusan ismert feltételei közül némelyik egyben a gráf pánciklikusságának elégséges feltétele is, ezért sejtése szerint minden 4-szeresen összefüggő síkbarajzolható gráf pánciklikus. Azonban (Malkevitch 1971) ellenpéldák egész családját alkotta meg.
Tournamentek
[szerkesztés]Egy tournament olyan irányított gráf, melyben a gráf bármely csúcspárja között húzódik egy irányított él. Könnyen látható, hogy a tournamentek modellezhetik a körmérkőzéses rendszereket, minden játék után a nyertestől a vesztesig húzva be egy irányított élt. Egy tournament pontosan akkor erősen összefüggő vagy erős, ha nem particionálható vesztesek (L) és győztesek (W) két nem üres részhalmazára úgy, hogy minden W-beli versenyző legyőzzön minden L-beli versenyzőt.[9] Minden erős tournament pánciklikus[10] és csúcs-pánciklikus.[11] Ha egy tournament reguláris (minden versenyzőnek pontosan ugyanannyi győzelme és veresége van, mint a többieknek), akkor él-pánciklikus is;[12] egy négy csúcsú erős tournament azonban nem lehet él-pánciklikus.
Sok éllel rendelkező gráfok
[szerkesztés]A Mantel-tétel szerint egy n csúcsú irányítatlan egyszerű gráfnak ha legalább n2/4 éle van, akkor vagy tartalmaz háromszöget, vagy a Kn/2,n/2 teljes páros gráfról van szó. Ennek a tételnek az erősebb változata szerint bármely irányítatlan, Hamilton-kört tartalmazó gráfnak ha legalább n2/4 éle van, akkor vagy pánciklikus, vagy a Kn/2,n/2.[1]
Az irányított esetben, létezik n csúcsú, Hamilton-kört tartalmazó irányított gráf n(n + 1)/2 − 3 éllel, ami nem pánciklikus, viszont a legalább n(n + 1)/2 − 1 élt tartalmazók pánciklikusak. Továbbá, az n csúcsú, erősen összefüggő irányított gráfok, melyekben minden csúcs fokszáma eléri n-et (a befokokat és a kifokokat összeadva) vagy pánciklikus, vagy irányított teljes páros gráf.[13]
Gráfhatványok
[szerkesztés]A G gráf k-adik hatványa, Gk olyan gráf, melynek csúcskészlete megegyezik az eredeti gráféval, és két csúcsa akkor van éllel összekötve, ha G-beli távolságuk legfeljebb k. Ha G is kétszeresen összefüggő, akkor a Fleischner-tétel szerint négyzete, G2 tartalmaz Hamilton-kört; ennek a kijelentésnek erősebb változata is igaz, miszerint csúcs-pánciklikus is.[14] Ráadásul, amennyiben G2 tartalmaz Hamilton-kört, akkor minden esetben pánciklikus is.[15]
Számítási bonyolultság
[szerkesztés]Egy gráf pánciklikusságának vizsgálata NP-teljes, még a 3-szorosan összefüggő 3-reguláris gráfok esetén is; szintén NP-teljes a csúcs-pánciklikusság tesztelése, még poliédergráfokon is.[16] NP-teljes annak tesztelése is, hogy adott gráf négyzetének van-e Hamilton-köre (és ezért pánciklikus-e).[17]
Története
[szerkesztés]A pánciklikusságot a tournamentek kontextusában először (Harary & Moser 1966), (Moon 1966) és (Alspach 1967) elemezték. A pánciklikusságot az irányítatlan gráfokra (Bondy 1971) terjesztette ki, nevet is ő adott a fogalomnak.
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Pancyclic graph 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
[szerkesztés]- ↑ a b c (Bondy 1971).
- ↑ a b (Randerath et al. 2002).
- ↑ (Schmeichel & Mitchem 1982).
- ↑ (Li, Corneil & Mendelsohn 2000), Proposition 2.5.
- ↑ (Helden 2007), Corollary 3.78.
- ↑ (Bernhart & Kainen 1979).
- ↑ (Hakimi & Schmeichel 1979).
- ↑ (Skowrońska 1985).
- ↑ (Harary & Moser 1966), Corollary 5b.
- ↑ (Harary & Moser 1966), Theorem 7.
- ↑ (Moon 1966), Theorem 1.
- ↑ (Alspach 1967).
- ↑ (Häggkvist & Thomassen 1976).
- ↑ Hobbs (1976).
- ↑ Fleischner (1976).
- ↑ (Li, Corneil & Mendelsohn 2000), Theorems 2.3 and 2.4.
- ↑ Underground (1978).
- Alspach, Brian (1967), "Cycles of each length in regular tournaments", Canadian Mathematical Bulletin 10 (2): 283–286, <http://cms.math.ca/cmb/v10/p283> Archiválva 2011. július 16-i dátummal a Wayback Machine-ben.
- Bernhart, Frank & Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B 27 (3): 320–331, DOI 10.1016/0095-8956(79)90021-2.
- Bondy, J. A. (1971), "Pancyclic graphs I", Journal of Combinatorial Theory, Series B 11 (1): 80–84, DOI 10.1016/0095-8956(71)90016-5.
- Fleischner, H. (1976), "In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts", Monatshefte für Mathematik 82 (2): 125–149, DOI 10.1007/BF01305995.
- Häggkvist, Roland & Thomassen, Carsten (1976), "On pancyclic digraphs", Journal of Combinatorial Theory, Series B 20 (1): 20–40, DOI 10.1016/0095-8956(76)90063-0.
- Hakimi, S. L. & Schmeichel, E. F. (1979), "On the number of cycles of length k in a maximal planar graph", Journal of Graph Theory 3: 69–86, DOI 10.1002/jgt.3190030108.
- Harary, Frank & Moser, Leo (1966), "The theory of round robin tournaments", American Mathematical Monthly 73 (3): 231–246, DOI 10.2307/2315334.
- Helden, Guido (2007), Hamiltonicity of maximal planar graphs and planar triangulations, Dissertation, Rheinisch-Westfälischen Technischen Hochschule Aachen, <http://darwin.bth.rwth-aachen.de/opus3/volltexte/2007/1949/pdf/Helden_Guido.pdf> Archiválva 2011. július 18-i dátummal a Wayback Machine-ben.
- Hobbs, Arthur M. (1976), "The square of a block is vertex pancyclic", Journal of Combinatorial Theory, Series B 20 (1): 1–4, DOI 10.1016/0095-8956(76)90061-7.
- Li, Ming-Chu; Corneil, Derek G. & Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics 98 (3): 219–225, DOI 10.1016/S0166-218X(99)00163-8.
- Malkevitch, Joseph (1971), "On the lengths of cycles in planar graphs", Recent Trends in Graph Theory, vol. 186, Lecture Notes in Mathematics, Springer-Verlag, pp. 191–195, DOI 10.1007/BFb0059437.
- Moon, J. W. (1966), "On subtournaments of a tournament", Canadian Mathematical Bulletin 9 (3): 297–301, doi:10.4153/CMB-1966-038-7, <http://cms.math.ca/cmb/v9/p297> Archiválva 2016. március 3-i dátummal a Wayback Machine-ben.
- Randerath, Bert; Schiermeyer, Ingo & Tewes, Meike et al. (2002), "Vertex pancyclic graphs", Discrete Applied Mathematics 120 (1-3): 219–237, DOI 10.1016/S0166-218X(01)00292-X.
- Schmeichel, Edward & Mitchem, John (1982), "Bipartite graphs with cycles of all even lengths", Journal of Graph Theory 6 (4): 429–439, DOI 10.1002/jgt.3190060407.
- Skowrońska, Mirosława (1985), "The pancyclicity of Halin graphs and their exterior contractions", in Alspach, Brian R. & Godsil, Christopher D., Cycles in Graphs, vol. 27, Annals of Discrete Mathematics, Elsevier Science Publishers B.V., pp. 179–194.
- Underground, Polly (1978), "On graphs with Hamiltonian squares", Discrete Mathematics 21 (3): 323, DOI 10.1016/0012-365X(78)90164-4.
További információk
[szerkesztés]- Weisstein, Eric W.: Pancyclic Graph (angol nyelven). Wolfram MathWorld