Kettős bevonási ciklusok

Megoldatlan matematikai problémák : Bármely híd nélküli gráf esetén létezik olyan egyszerű ciklusok több halmaza , amely a gráf minden élét pontosan kétszer fedi le?

A kettős ciklus lefedettsége a gráfelméletben egy irányítatlan gráf ciklusainak  halmaza , amely minden élt pontosan kétszer tartalmaz. Például bármely poliéder gráf egy konvex poliéder csúcsaiból és éleiből jön létre , míg a lapok kettős ciklusfedőt alkotnak: minden él pontosan két laphoz tartozik.

Szekeres György [1] és Paul Seymour [2] a kettős ciklusú fedősejtést terjesztette elő , amely szerint bármely híd nélküli gráfra létezik duplaciklusú fedő. Ez a sejtés ekvivalens módon újrafogalmazható gráfbeágyazások formájában , és a területen körkörös beágyazási sejtésként vagy erős beágyazási sejtésként is ismert . 

Megfogalmazás

A sejtést általában a következőképpen fogalmazzák meg: igaz-e, hogy bármely híd nélküli gráfban van olyan egyszerű ciklusok halmaza, amelyeknél minden él ennek a halmaznak pontosan két ciklusában található? Szükséges az a követelmény, hogy a gráfban ne legyenek hidak, mivel egyik híd sem tartozhat egyik ciklushoz sem. A hipotézisfeltételt kielégítő ciklusok halmazát kettős ciklus lefedettségnek nevezzük . Egyes grafikonok, például ciklusok vagy kaktuszok , csak bizonyos ciklusok ismételt használatával fedhetők le, ezért az ilyen típusú ciklusismétlés megengedett kettős ciklusú lefedettség esetén.

Csökkentés snarks

Egy snark ( egy híd nélküli köbös gráf , amelyben az éleket nem lehet három színnel színezni, hogy két azonos színű él ne konvergáljon ugyanabban a csúcsban) a Vizing -tétel szerint 4 lesz a kromatikus indexe . A snarkok a legnehezebbek. grafikonok dupla lefedésére ciklusokkal: ha a sejtés igaz a snarkra, akkor igaz lesz minden hidak nélküli gráfra [3] .

Valóban, ha egy gráfnak 1-es fokú csúcsa van , akkor az éle hidat képez. Ha van 2-es fokú csúcs, akkor ezt a csúcsot ki lehet dobni a gráfból, és az éleit összevonhatjuk egybe. Ha feltételezzük, hogy a gráfnak van egy 4-es vagy annál nagyobb fokú csúcsa, akkor lehetséges [4] találni két ilyen élt és e csúcs mellett, hogy eltávolíthatók legyenek, és helyettük egy összekötő élt adjunk hozzá. ezeknek az éleknek a végei, amelyek különböznek a -tól , tartása at Ez az a tulajdonság, hogy a gráfban nincsenek hidak. Az új gráf kettős borítójáról könnyen beszerezhető a régi gráf kettős fedele.

Ha a köbös gráf kromatikus indexe 3, akkor könnyű kettős ciklusú lefedettséget felépíteni: az első ciklus az első és a második szín összes élét tartalmazza, a második ciklus az első és a harmadik szín összes élét, és a A harmadik ciklus tartalmazza a második és harmadik szín összes élét.

Csökkenthető konfigurációk

A hipotézis megoldására a mai napig számos megközelítést javasoltak. Az egyik ilyen megközelítés az, hogy megmutatjuk, hogy nincs minimális ellenpélda, vagyis minden gráfban keresünk redukálható konfigurációkat . A redukálható konfiguráció egy részgráf, amely helyettesíthető egy kisebb részgráfral, így megtartjuk azt a tulajdonságot, hogy a ciklusok kétszeresen lefednek-e vagy sem (hasonló megközelítést sikeresen alkalmaztunk a négy szín tétel bizonyításakor ). Például, ha van egy háromszög a gráfban (három csúcs kapcsolódik egymáshoz), akkor elvégezhetünk egy háromszög-csillag transzformációt , ezzel csökkentve a csúcsok számát 2-vel; ebben az esetben a kisebb gráf bármely dupla ciklusú lefedettsége az eredeti nagyobb gráf lefedettségévé alakul. Így a sejtés minimális ellenpéldájában nem találhatunk háromszög alakú részgráfot. Például egy számítógép segítségével kimutatták, hogy a minimális ellenpéldában (ami egy köbös gráf lesz) nem lehet 11 vagy annál rövidebb ciklus, azaz egy ilyen gráf kerülete legalább 12 [ 5]

Sajnos, ellentétben a fenti négy szín tétellel, nincs véges redukálható konfigurációk halmaza a kettős ciklus lefedettség sejtéséhez. Például minden redukálható konfigurációban van valamilyen ciklus, így a redukálható konfigurációk bármely véges halmazához van egy olyan γ szám, hogy bármely konfigurációban van egy γ-nál rövidebb ciklus. De ismert, hogy vannak tetszőlegesen magas kerületű snarkok (a minimális ciklus hossza). [6] Egy ilyen snarkot nem lehet kicsinyíteni, mivel egyik konfiguráció sem szerepel benne, és stratégiánk erre a példára nem lesz alkalmazható.

Láncbeágyazási sejtés

Jegyzetek

  1. ↑ Szekeres, G. Polyhedral decomposition of cubic graphs  (neopr.)  // Bulletin of the Australian Mathematical Society. - 1973. - T. 8 , 03. sz . - S. 367-387 . - doi : 10.1017/S0004972700042660 .
  2. ↑ Seymour, PD Diszjunkt útvonalak gráfokban  (neopr.)  // Discrete Mathematics. - 1980. - T. 29 , 3. sz . - S. 293-309 . - doi : 10.1016/0012-365X(80)90158-2 .
  3. ↑ Jaeger, F. A ciklus kettős fedősejtésének felmérése  (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émet)  // Monatshefte für Mathematik : bolt. - 1976. - Bd. 81 , sz. 4 . - S. 267-278 . — ISSN 1436-5081/e 0026-9255; 1436-5081/e . - doi : 10.1007/BF01387754 .
  5. ↑ Huck, A. Csökkenthető konfigurációk a ciklus kettős fedeles sejtéséhez  //  Discrete Applied Mathematics : folyóirat. - 2000. - Vol. 99 , sz. 1-3 . - 71-90 . - doi : 10.1016/S0166-218X(99)00126-2 .
  6. ↑ Kochol, Martin. Snarks kis ciklusok nélkül  (angol)  // Journal of Combinatorial Theory, Series B  : Journal. - 1996. - 1. évf. 67 , sz. 1 . - P. 34-47 . - doi : 10.1006/jctb.1996.0032 .

Irodalom

Linkek