Wikipédia

Pánciklikus gráf

gráfelméleti fogalom

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.

Egy oktaéder pánciklikusságát igazoló összes lehetséges hosszúságú köre.

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]

 
Egy csaknem pánciklikus Halin-gráf, amiben 8 hosszúságú körön kívül az összes körhosszúság jelen van

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

  1. ↑ a b c (Bondy 1971).
  2. ↑ a b (Randerath et al. 2002).
  3. ↑ (Schmeichel & Mitchem 1982).
  4. ↑ (Li, Corneil & Mendelsohn 2000), Proposition 2.5.
  5. ↑ (Helden 2007), Corollary 3.78.
  6. ↑ (Bernhart & Kainen 1979).
  7. ↑ (Hakimi & Schmeichel 1979).
  8. ↑ (Skowrońska 1985).
  9. ↑ (Harary & Moser 1966), Corollary 5b.
  10. ↑ (Harary & Moser 1966), Theorem 7.
  11. ↑ (Moon 1966), Theorem 1.
  12. ↑ (Alspach 1967).
  13. ↑ (Häggkvist & Thomassen 1976).
  14. ↑ Hobbs (1976).
  15. ↑ Fleischner (1976).
  16. ↑ (Li, Corneil & Mendelsohn 2000), Theorems 2.3 and 2.4.
  17. ↑ Underground (1978).

További információk szerkesztés

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Pánciklikus_gráf&oldid=26590584”