Kaksoispinnoitusjaksot

Ratkaisemattomat matematiikan ongelmat : Onko missä tahansa sillattomassa graafissa yksinkertaisten syklien joukko , joka kattaa graafin jokaisen reunan tarkalleen kahdesti?

Kaksoissyklin peitto graafiteoriassa  on joukko jaksoja ohjaamattomassa graafissa , joka sisältää jokaisen reunan täsmälleen kahdesti. Esimerkiksi mikä tahansa monitahoinen graafi muodostuu kuperan monitahoisen pisteistä ja reunoista , kun taas pinnat muodostavat kaksoiskiertopeitteen: jokainen reuna kuuluu täsmälleen kahdelle pinnalle.

György Szekeres [1] ja Paul Seymour [2] esittivät kaksoiskiertopeiteoletuksen , jonka mukaan mille tahansa siltaattomalle graafille on olemassa kaksoisjaksopeite. Tämä olettamus voidaan vastaavasti muotoilla uudelleen graafin upotuksina , ja se tunnetaan alalla myös pyöreän upotuksen oletuksena tai vahvan upotuksen oletuksena . 

Sanamuoto

Oletus muotoillaan yleensä seuraavasti: onko totta, että missä tahansa sillattomassa graafissa on joukko yksinkertaisia ​​jaksoja , joiden jokainen reuna sisältyy tarkalleen kahteen tämän joukon sykliin? Vaatimus, että kaaviossa ei ole siltoja, on välttämätön, koska mikään silloista ei voi kuulua mihinkään sykliin. Hypoteesiehdon täyttävää syklien joukkoa kutsutaan kaksoissyklien peitoksi . Jotkut kaaviot, kuten syklit tai kaktukset , voidaan peittää vain joidenkin syklien toistuvalla käytöllä, joten tällainen syklin toisto on sallittua kaksinkertaisen syklin peitossa.

Vähennys snarkeiksi

Snarkin ( kuutiokuvaaja ilman siltoja, jonka reunoja ei voida värjätä kolmella värillä niin, että kaksi samanväristä reunaa eivät konvergoi samassa kärjessä) on Vizingin lauseen mukaan kromaattinen indeksi 4. Snarkit ovat vaikeimpia kaaviot kaksinkertaiseksi peittämiseksi syklien kanssa: jos olettamus on totta snarksille, niin se on totta kaikille kaavioille, joissa ei ole siltoja [3] .

Todellakin, jos graafin kärkipiste on aste 1, niin sen reuna muodostaa sillan. Jos on asteen 2 kärki, niin tämä kärki voidaan heittää pois graafista ja sen reunat voidaan yhdistää yhdeksi. Jos oletetaan, että graafilla on aste 4 tai enemmän, niin on mahdollista [4] löytää kaksi tällaista reunaa ja tämän kärjen vierestä, jotta ne voidaan poistaa ja niiden sijaan lisätä reuna, joka yhdistää näiden reunojen päät, jotka ovat erilaisia ​​kuin , pitäen kohdassa Tämä on ominaisuus, että kaaviossa ei ole siltoja. Uuden graafin kaksoiskannesta on helppo saada kaksoiskansi vanhalle graafille.

Jos kuutiograafin kromaattinen indeksi on 3, on helppo rakentaa kaksoisjaksopeitto: ensimmäinen sykli sisältää kaikki ensimmäisen ja toisen värin reunat, toinen sykli sisältää kaikki ensimmäisen ja kolmannen värin reunat ja kolmas jakso sisältää kaikki toisen ja kolmannen värin reunat.

Pienennettävät kokoonpanot

Tähän mennessä hypoteesin ratkaisemiseksi on ehdotettu useita lähestymistapoja. Yksi tällainen lähestymistapa on, että osoitamme, ettei ole olemassa minimaalista vastaesimerkkiä, nimittäin etsimme jokaisesta kaaviosta pelkistettäviä konfiguraatioita . Pelkistävä konfiguraatio on aligraafi, joka voidaan korvata pienemmällä aligraafilla niin, että säilyy ominaisuus, onko syklien katettu kaksinkertainen vai ei (samalaista lähestymistapaa sovellettiin onnistuneesti neljän värin lauseen todistuksessa ). Esimerkiksi, jos graafissa on kolmio (kolme kärkeä, jotka liittyvät toisiinsa), voimme suorittaa kolmio-tähtimuunnoksen , mikä vähentää pisteiden lukumäärää 2:lla; tässä tapauksessa mikä tahansa pienemmän kaavion kaksinkertainen jaksopeitto muunnetaan alkuperäisen suuremman graafin peittoalueeksi. Näin ollen oletuksen minimaalisessa vastaesimerkissä emme voi löytää kolmion muodossa olevaa osagraafia. Myös esimerkiksi tietokonetta käyttämällä osoitettiin, että minimivastaesimerkissä (joka tulee olemaan kuutiograafi) ei voi olla sykliä, jonka pituus on 11 tai vähemmän, eli tällaisen graafin ympärysmitta on vähintään 12 [ 5]

Valitettavasti, toisin kuin yllä olevassa neljän värin lauseessa, kaksinkertaisen jakson kattavuusoletuksella ei ole rajallista pelkistettäviä konfiguraatioita. Esimerkiksi jokaisessa pelkistettävässä konfiguraatiossa on jokin jakso, joten mille tahansa pelkistettävien konfiguraatioiden äärelliselle joukolle on sellainen luku γ, että missä tahansa konfiguraatiossa on sykli, jonka pituus on pienempi kuin γ. Mutta tiedetään, että on olemassa snarkkeja, joilla on mielivaltaisen suuri ympärysmitta (minimijakson pituus). [6] Tällaista snarkia ei voida pienentää, koska mikään konfiguraatioista ei sisälly siihen, eikä strategiaamme voida soveltaa tähän esimerkkiin.

Ketjun upotusoletus

Muistiinpanot

  1. ↑ Szekeres, G. Kuutiograafien monitahoinen hajottelu  (uus.)  // Bulletin of the Australian Mathematical Society. - 1973. - T. 8 , nro 03 . - S. 367-387 . - doi : 10.1017/S0004972700042660 .
  2. ↑ Seymour, PD Disjunktit polut kaavioissa  (neopr.)  // Diskreetti matematiikka. - 1980. - T. 29 , nro 3 . - S. 293-309 . - doi : 10.1016/0012-365X(80)90158-2 .
  3. ↑ Jaeger, F. Tutkimus syklin kaksoiskannen olettamuksesta  (uuspr.)  // 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  (saksa)  // Monatshefte für Mathematik : myymälä. - 1976. - Bd. 81 , no. 4 . - S. 267-278 . — ISSN 1436-5081/e 0026-9255; 1436-5081/e . - doi : 10.1007/BF01387754 .
  5. ↑ Huck, A. Pelennettävät konfiguraatiot syklin kaksoiskannen olettamukselle  //  Discrete Applied Mathematics : päiväkirja. - 2000. - Voi. 99 , ei. 1-3 . - s. 71-90 . - doi : 10.1016/S0166-218X(99)00126-2 .
  6. ↑ Kochol, Martin. Snarks ilman pieniä syklejä  (englanti)  // Journal of Combinatorial Theory, Series B  : Journal. - 1996. - Voi. 67 , no. 1 . - s. 34-47 . - doi : 10.1006/jctb.1996.0032 .

Kirjallisuus

Linkit