Pancyklický graf

Pancyklický graf  je řízený nebo neorientovaný graf , který obsahuje cykly všech možných délek od tří do počtu vrcholů grafu [1] . Pancyklické grafy jsou zobecněním hamiltonovských grafů , grafů, které mají cykly o maximální možné délce.

Definice

Graf s vrcholy je pancyklický, pokud pro jakýkoli uvnitř graf obsahuje cyklus délky [1] . Graf je vrcholově-pancyklický , pokud pro jakýkoli vrchol a kterýkoli ve stejných mezích graf obsahuje cyklus délky obsahující vrchol [2] . Podobně je graf hranový pancyklický , pokud pro jakoukoli hranu a pro kteroukoli ve stejných mezích obsahuje cyklus délky obsahující hranu [2] .

Bipartitní graf nemůže být pancyklický, protože neobsahuje cykly žádné liché délky, ale o grafu se říká, že je bipancyklický , pokud obsahuje cykly všech sudých délek od 4 do [3] .

Rovinné grafy

Maximální vnější rovinný graf  je graf vytvořený z jednoduchého mnohoúhelníku v rovině triagularizací jeho vnitřku. Jakýkoli maximální vnější rovinný graf je pancyklický, což lze zobrazit indukcí. Vnější plocha grafu je cyklus s n vrcholy a odstranění jakéhokoli trojúhelníku spojeného se zbytkem grafu pouze jednou hranou (listem stromu, který tvoří graf duální triangulace) vytvoří maximální vnější rovinný graf s jedním číslem menším. vrcholů a podle indukčního předpokladu má tento graf všechny cykly všech zbývajících délek. Je-li věnována větší pozornost volbě trojúhelníku k odstranění, pak stejné argumenty ukazují přesnější výsledek, že jakýkoli maximální vnější rovinný graf je vertex-pancyklický [4] . Totéž platí pro grafy, které mají maximální vnější rovinný graf jako překlenovací podgraf , zejména pro kola .

Maximální rovinný graf  je rovinný graf, ve kterém jsou všechny plochy, včetně vnější, trojúhelníky. Maximální rovinný graf je vertex-pancyklický právě tehdy, pokud obsahuje hamiltonovský cyklus [5]  — pokud není hamiltonovský, rozhodně není pancyklický, a pokud je hamiltonovský, pak vnitřek hamiltonovského cyklu tvoří vnější plochu maximálního vnějšího rovinného grafu na stejných vrcholech a hranách, na které lze aplikovat předchozí argumenty pro vnější rovinné grafy [6] . Například na obrázku[ co? ] ukazuje pancykličnost oktaedronového grafu , hamiltonovského maximálního rovinného grafu se šesti vrcholy. Přesněji řečeno, ze stejných důvodů, pokud má maximální rovinný graf cyklus délky , má cykly všech menších délek [7] .

Halinovy ​​grafy jsou rovinné grafy vytvořené z rovinné kresby stromu bez vrcholů stupně dva přidáním cyklu spojujícího listy stromu. Halinovy ​​grafy nemusí být nutně pancyklické, ale jsou téměř pancyklické v tom smyslu, že neexistuje cyklus o nejvýše jedné délce. Délka chybějícího cyklu je nutně sudá. Pokud žádný z vnitřních vrcholů Halinova grafu nemá stupeň tři, pak je graf nutně pancyklický [8] .

V roce 1971 bylo konstatováno [1] , že pro pancykličnost postačuje i mnoho klasických podmínek pro existenci hamiltonovského cyklu, a proto se předpokládalo, že jakýkoli 4-souvislý rovinný graf je pancyklický, ale brzy byla nalezena rodina protipříkladů [ 9] .

Turnaje

Turnaj  je orientovaný graf s jedním nasměrovaným obloukem mezi libovolným párem vrcholů. Intuitivně lze turnaj použít k simulaci cyklického souboje tak, že pro každou hru v soutěži nakreslíte oblouk od vítěze k poraženému. O turnaji se říká , že je silně propojený nebo jednoduše silný tehdy a jen tehdy, pokud jej nelze rozdělit na dvě neprázdné podmnožiny poražených a vítězů, takže kterýkoli účastník porazí kteréhokoli účastníka v [10] . Každý silný turnaj je pancyklický [11] a vrcholový pancyklický [12] . Pokud je turnaj regulérní (kterýkoli účastník má stejný počet výher a proher jako ostatní účastníci), pak je také edge-pancyclic [13] , ale silné turnaje se čtyřmi vrcholy nemohou být edge-pancyclic.

Grafy s velkým počtem hran

Mantelův teorém říká, že jakýkoli neorientovanývrcholový graf, který má alespoňhrany a nemá více hran nebo smyček, obsahuje trojúhelník nebo je úplným bipartitním grafem . Tuto větu lze posílit - každý neorientovaný hamiltonovský graf s alespoňhranami je buď pancyklický, nebo je [1] .

Existují hamiltonovské řízené grafy s vrcholy a oblouky, které nejsou pancyklické, ale jakýkoli hamiltonovský řízený graf s alespoň oblouky je pancyklický. Navíc přísně propojený vrcholový graf, ve kterém má každý vrchol alespoň stupeň (příchozí a odchozí oblouky se počítají společně), je buď pancyklický, nebo jde o úplný bipartitní graf [14] .

Stupně grafu

Pro jakýkoli graf je jeho tý stupeň grafu definován jako graf na stejné množině vrcholů, která má hranu mezi libovolnými dvěma vrcholy, přičemž vzdálenost mezi nimi nepřesahuje . Pokud je vrchol 2-souvislý , pak podle Fleischnerovy věty je hamiltonovský graf. Tvrzení lze posílit: graf bude nutně vertex-pancyklický [15] . Přesněji řečeno, pokud je hamiltonovský, je také pancyklický [16] .

Výpočetní složitost

Testování grafu na pancykličnost je NP-úplný problém i pro speciální případ 3-spojených kubických grafů . NP-úplným problémem je také testovat graf na pancykličnost vrcholu i pro speciální případ polyedrických grafů [17] . NP-úplným úkolem je také otestovat druhou mocninu grafu na hamiltonianitu, a tedy také na pancykličnost [18] .

Historie

Pancykličnost poprvé prozkoumali Harari a Moser v kontextu turnajů [19] a také Muun [20] a Alpach [13] . Koncept pancykličnosti pojmenoval Bondi, který tento koncept rozšířil o neorientované grafy [1] .

Poznámky

  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 , Tvrzení 2.5.
  5. ↑ Helden, 2007 , důsledek 3.78.
  6. ↑ Bernhart, Kainen, 1979 .
  7. ↑ Hakimi, Schmeichel, 1979 .
  8. ↑ Skowrońska, 1985 .
  9. ↑ Malkevitch, 1971 .
  10. ↑ Harary a Moser, 1966 , důsledek 5b.
  11. ↑ Harary a Moser, 1966 , Věta 7.
  12. ↑ Měsíc, 1966 , Věta 1.
  13. ↑ 12 Alspach , 1967 .
  14. ↑ Häggkvist, Thomassen, 1976 , s. 20–40.
  15. ↑ Hobbs (1976) .
  16. ↑ Fleischner, 1976 .
  17. ↑ Li, Corneil, Mendelsohn, 2000 , Věty 2.3 a 2.4.
  18. ↑ Underground (1978) .
  19. ↑ Harary, Moser, 1966 .
  20. ↑ Měsíc, 1966 .

Literatura

Odkazy