Pánciklikus grafikon

A panciklikus gráf olyan  irányított vagy irányítatlan gráf , amely háromtól a gráfcsúcsok számáig minden lehetséges hosszúságú ciklust tartalmaz [1] . A panciklikus gráfok a Hamilton-gráfok általánosítása , olyan gráfok, amelyek ciklusai a lehető legnagyobb hosszúságúak.

Definíciók

Egy csúcsokkal rendelkező gráf panciklikus , ha bármely belüli gráf tartalmaz egy [1] hosszúságú ciklust . Egy gráf csúcs-panciklikus , ha bármely csúcsra és bármely ugyanazon határon belüli csúcsra a gráf tartalmaz egy csúcsot tartalmazó hosszúságú ciklust [2] . Hasonlóképpen, egy gráf élpanciklikus , ha bármely élre és bármely azonos határon belüli élre tartalmaz egy olyan hosszúságú ciklust, amely tartalmazza az élt [2] .

Egy kétrészes gráf nem lehet panciklikus, mert nem tartalmaz páratlan hosszúságú ciklusokat, de egy gráfot bipanciklikusnak mondunk , ha 4-től [3] -ig minden páros hosszúságú ciklust tartalmaz .

Síkgráfok

A maximális külső sík gráf  egy olyan gráf, amelyet a síkban egy egyszerű sokszögből alakítunk ki, annak belsejét triagularizálva . Bármely maximális külső síkbeli gráf panciklikus, ami indukcióval mutatható ki. A gráf külső felülete egy n csúcsú ciklus, és ha a gráf többi részéhez csak egy éllel kapcsolt háromszöget ( a kettős háromszögelési gráfot alkotó fa levelével) töröljük, akkor egy maximális külső sík gráfot kapunk eggyel kevesebb számmal. csúcsokból, és az induktív feltevés szerint ennek a gráfnak az összes fennmaradó hosszúságú ciklusa van. Ha nagyobb figyelmet fordítunk az eltávolítandó háromszög kiválasztására, akkor ugyanezek az érvek azt a szigorúbb eredményt mutatják, hogy bármely maximális külső sík gráf csúcs-panciklikus [4] . Ugyanez igaz azokra a grafikonokra is, amelyek egy maximális külső síkbeli gráfot tartalmaznak feszítő részgráfként , különösen a kerekekre .

A maximális síkgráf  olyan sík gráf, amelyben minden lap, beleértve a külsőt is, háromszög. Egy maximális síkgráf akkor és csak akkor csúcs-panciklikus, ha tartalmaz Hamilton-ciklust [5]  – ha nem Hamilton-ciklus, akkor biztosan nem panciklikus, ha pedig Hamilton-gráf, akkor a Hamilton-ciklus belseje alkotja a külső felületet. a maximális külső sík gráf ugyanazon csúcsokon és éleken, amelyre az előző, külső síkbeli gráfok argumentumai alkalmazhatók [6] . Például az ábrán[ mi? ] mutatja az oktaéder gráf panciklicitását , egy hat csúcsú Hamilton-féle maximális síkgráfot. Pontosabban, ugyanezen okok miatt, ha egy maximális síkgráfnak van egy hosszúságú ciklusa , akkor minden kisebb hosszúságú ciklusa van [7] .

A Halin gráfok olyan síkgráfok, amelyeket egy fa síkbeli rajzából alakítanak ki, amelynek nincs második foka csúcsa, a fa leveleit összekötő ciklus hozzáadásával. A Halin-gráfok nem feltétlenül panciklikusak, de szinte panciklikusak abban az értelemben, hogy nincs legfeljebb egy hosszúságú ciklus. A hiányzó ciklus hossza szükségszerűen páros. Ha a Halin-gráf egyik belső csúcsának sincs három foka, akkor a gráf szükségszerűen panciklikus [8] .

1971-ben megállapították [1] , hogy a Hamilton-ciklus létezésének számos klasszikus feltétele is elegendő a panciklicitáshoz, ezért azt feltételezték, hogy bármely 4-kapcsolatú síkgráf panciklikus, de hamarosan találtak egy ellenpélda-családot . 9] .

Versenyek

A verseny  egy irányított gráf, amelynek bármely csúcspárja között egy irányított ív található. Intuitív módon egy verseny felhasználható egy körmérkőzés szimulálására úgy, hogy a verseny minden egyes játékánál ívet rajzolunk a győztestől a vesztesig. Egy versenyt akkor és csak akkor nevezünk erősen összefüggőnek vagy egyszerűen erősnek, ha nem osztható két nem üres vesztesek és nyertesek részhalmazára, így bármelyik résztvevő legyőzi bármelyik résztvevőt a [10]-ben . Minden erős verseny panciklikus [11] és vertex panciklikus [12] . Ha egy verseny rendszeres (bármelyik résztvevőnek ugyanannyi győzelme és veresége van, mint a többi résztvevőnek), akkor az is élpanciklikus [13] , de a négy csúcsú erős versenyek nem lehetnek élpanciklikusak.

Grafikonok nagy számú éllel

Mantel tétele kimondja, hogy minden irányítatlancsúcsgráf, amelynek legalábbélei vannak, és nincs több éle vagy hurokja, vagy tartalmaz háromszöget, vagy egy teljes kétrészes gráf . Ez a tétel megerősíthető - bármely irányítatlan Hamilton-gráf, amelynek legalábbélei vannak, vagy panciklikus, vagy [1] .

Vannak olyan Hamilton-irányított gráfok csúcsokkal és ívekkel, amelyek nem panciklikusak, de minden legalább ívet tartalmazó Hamilton-irányított gráf panciklikus. Ezenkívül egy szigorúan összefüggő csúcsgráf, amelyben minden csúcsnak van legalább foka (a bejövő és kimenő íveket együtt számolják), vagy panciklikus, vagy egy teljes bipartit gráf [14] .

Grafikon fokai

Bármely gráf esetén a gráf edik fokát úgy definiáljuk, mint egy gráfot ugyanazon a csúcshalmazon, amelynek van egy éle bármely két csúcs között, amelyek közötti távolság in nem haladja meg a -t . Ha a 2-es csúcs kapcsolódik , akkor Fleischner tétele szerint egy Hamilton-gráf. Az állítás megerősíthető: a gráf szükségszerűen csúcs-panciklikus lesz [15] . Pontosabban, ha hamiltoni, akkor panciklikus is [16] .

Számítási összetettség

Egy gráf panciklicitásának tesztelése NP-teljes probléma még a 3 összekapcsolt köbös gráfok speciális esetére is . Szintén NP-teljes probléma egy gráf csúcspanciklicitásának tesztelése még poliéder gráfok speciális esetére is [17] . Szintén egy NP-teljes feladat egy gráf négyzetének Hamiltonitás vizsgálata, és így a panciklicitás vizsgálata is [18] .

Történelem

A panciklicitást először Harari és Moser tárta fel a versenyek [19] összefüggésében , valamint Muun [20] és Alpach [13] . A panciklicitás fogalmát Bondi nevezte el, aki kiterjesztette a fogalmat az irányítatlan gráfokra [1] .

Jegyzetek

  1. ↑ 1 2 3 4 5 Bondy, 1971 .
  2. ↑ 1 2 Randerath, Schiermeyer, Tewes, Volkmann, 2002 .
  3. ↑ Schmeichel, Mitchem, 1982 .
  4. ↑ Li, Corneil, Mendelsohn, 2000 , 2.5. tétel.
  5. ↑ Helden, 2007 , Következmény 3.78.
  6. ↑ Bernhart, Kainen, 1979 .
  7. ↑ Hakimi, Schmeichel, 1979 .
  8. ↑ Skowrońska, 1985 .
  9. ↑ Malkevics, 1971 .
  10. ↑ Harary és Moser, 1966 , Következmény 5b.
  11. ↑ Harary és Moser, 1966 , 7. tétel.
  12. ↑ Hold, 1966 , 1. tétel.
  13. ↑ Alspach 12. , 1967 .
  14. ↑ Häggkvist, Thomassen, 1976 , p. 20–40.
  15. ↑ Hobbs (1976) .
  16. ↑ Fleischner, 1976 .
  17. ↑ Li, Corneil, Mendelsohn, 2000 , 2.3. és 2.4. tétel.
  18. ↑ Underground (1978) .
  19. ↑ Harary, Moser, 1966 .
  20. ↑ Hold, 1966 .

Irodalom

Linkek