Dvojité cykly povlakování

Nevyřešené problémy v matematice : Existuje pro jakýkoli bezmůstkový graf vícemnožina jednoduchých cyklů pokrývajících každý okraj grafu přesně dvakrát?

Dvojitý cyklus pokrytí v teorii grafů  je soubor cyklů v neorientovaném grafu , který zahrnuje každou hranu přesně dvakrát. Například jakýkoli polyedrický graf je vytvořen z vrcholů a hran konvexního mnohostěnu , zatímco plochy tvoří dvojitý kryt cyklu: každá hrana patří přesně dvěma plochám.

György Szekeres [1] a Paul Seymour [2] předložili domněnku pokrytí dvojitým cyklem , podle níž pro každý bezmůstkový graf existuje pokrytí dvojitým cyklem. Tato domněnka může být ekvivalentně přeformulována z hlediska vkládání grafů a je v oboru známá také jako domněnka o kruhovém vkládání nebo domněnka o silném vkládání . 

Formulace

Dohad je obvykle formulován následovně: je pravda, že v každém bezmůstkovém grafu existuje množina jednoduchých cyklů , pro které je každá hrana obsažena právě ve dvou cyklech této množiny? Požadavek, aby v grafu nebyly žádné můstky, je nezbytný, protože žádný z můstků nemůže patřit do žádného z cyklů. Soubor cyklů, který splňuje podmínku hypotézy, se nazývá pokrytí dvojitým cyklem . Některé grafy, jako jsou cykly nebo kaktusy , lze pokrýt pouze opakovaným použitím některých cyklů, takže tento druh opakování cyklu je povolen v pokrytí dvojitým cyklem.

Redukce na snarks

Snark ( kubický graf bez mostů, ve kterém okraje nemohou být obarveny třemi barvami, aby se dvě hrany stejné barvy nesbíhaly ve stejném vrcholu) bude mít chromatický index 4 podle Vizingovy věty . Snarks jsou nejobtížnější grafy na dvojité pokrytí cykly: pokud platí domněnka pro snarky, pak bude platit pro všechny grafy bez můstků [3] .

Pokud má graf vrchol stupně 1, pak jeho hrana tvoří most. Pokud existuje vrchol stupně 2, pak tento vrchol může být vyhozen z grafu a jeho hrany mohou být spojeny do jednoho. Pokud předpokládáme, že graf má vrchol stupně 4 a více, pak je možné [4] najít dvě takové hrany a , sousedící s tímto vrcholem, takže je lze odstranit a místo nich přidat hranu spojující konce těchto hran, které jsou odlišné od , zachování na Toto je vlastnost, že v grafu nejsou žádné mosty. Z dvojitého krytu nového grafu je snadné získat dvojitý kryt pro starý graf.

Pokud má kubický graf chromatický index 3, je snadné vytvořit pokrytí dvojitým cyklem: první cyklus zahrnuje všechny hrany první a druhé barvy, druhý cyklus zahrnuje všechny hrany první a třetí barvy a třetí cyklus zahrnuje všechny okraje druhé a třetí barvy.

Redukovatelné konfigurace

K dnešnímu dni bylo navrženo několik přístupů k vyřešení hypotézy. Jedním z takových přístupů je, že ukážeme, že neexistuje žádný minimální protipříklad, konkrétně budeme v každém grafu hledat redukovatelné konfigurace . Redukovatelná konfigurace je podgraf, který lze nahradit menším podgrafem, takže si zachováme vlastnost mít nebo nebýt dvakrát pokrytý cykly (podobný přístup byl úspěšně aplikován v důkazu věty o čtyřech barvách ). Je-li například v grafu trojúhelník (tři vrcholy vzájemně propojené), můžeme provést transformaci trojúhelník-hvězda , čímž snížíme počet vrcholů o 2; v tomto případě je pokrytí menšího grafu s dvojitým cyklem převedeno na pokrytí původního většího grafu. V minimálním protipříkladu k domněnce tedy nemůžeme najít podgraf ve tvaru trojúhelníku. Také se například pomocí počítače ukázalo, že v minimálním protipříkladu (což bude kubický graf) nemůže existovat cyklus o délce 11 nebo menší, to znamená, že obvod takového grafu bude alespoň 12 [ 5]

Bohužel, na rozdíl od výše uvedeného teorému o čtyřech barvách, neexistuje žádná konečná množina redukovatelných konfigurací pro domněnku pokrytí dvojitým cyklem. Například v každé redukovatelné konfiguraci existuje nějaký cyklus, takže pro jakoukoli konečnou množinu redukovatelných konfigurací existuje takové číslo γ, že v jakékoli konfiguraci existuje cyklus o délce menší než γ. Ale je známo, že existují snarky s libovolně vysokým obvodem (délkou minimálního cyklu). [6] Takový snark nelze zmenšit, protože v něm není obsažena žádná z konfigurací a naše strategie nebude na tento příklad použitelná.

Chain embedding dohad

Poznámky

  1. ↑ Szekeres, G. Polyedral decomposition of cubic graphs  (neopr.)  // Bulletin of the Australian Mathematical Society. - 1973. - T. 8 , č. 03 . - S. 367-387 . - doi : 10.1017/S0004972700042660 .
  2. ↑ Seymour, PD Disjunktní cesty v grafech  (neopr.)  // Diskrétní matematika. - 1980. - T. 29 , č. 3 . - S. 293-309 . - doi : 10.1016/0012-365X(80)90158-2 .
  3. ↑ Jaeger, F. A survey of the cycle double cover  conjecture (neopr.)  // Annals of Discrete Mathematics. - 1985. - T. 27 . - S. 1-12 . - doi : 10.1016/S0304-0208(08)72993-1 .
  4. ↑ Fleischner, Herbert. Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen  (německy)  // Monatshefte für Mathematik : prodejna. - 1976. - Bd. 81 , č. 4 . - S. 267-278 . — ISSN 1436-5081/e 0026-9255; 1436-5081/e . - doi : 10.1007/BF01387754 .
  5. ↑ Huck, A. Redukovatelné konfigurace pro domněnku dvojitého krytu cyklu  //  Diskrétní aplikovaná matematika : deník. - 2000. - Sv. 99 , č. 1-3 . - S. 71-90 . - doi : 10.1016/S0166-218X(99)00126-2 .
  6. ↑ Kochol, Martin. Snarks bez malých cyklů  (anglicky)  // Journal of Combinatorial Theory, Series B  : journal. - 1996. - Sv. 67 , č. 1 . - str. 34-47 . - doi : 10.1006/jctb.1996.0032 .

Literatura

Odkazy