Hypohamiltonin kaavio

Graafiteoriassa graafin G sanotaan olevan hypo -Hamiltonin , jos graafissa itsessään ei ole Hamiltonin sykliä , mutta mikä tahansa graafi, joka saadaan poistamalla yksi piste G :stä, on Hamiltonin .

Historia

Sousselier tutki hypo-Hamiltonin graafit ensimmäisen kerran vuonna 1963 [2] . Lindgren [1] mainitsee Gaudinin, Hertzin ja Rossin (1964) [3] sekä Busakerin ja Saatyn (1965) [4] lisämateriaalina tästä aiheesta. Toinen varhainen työ on Hertzin, Dubyn ja Vigen vuoden 1967 paperi [5] .

Grötschel [6] tiivisti suurimman osan tällä alalla tehdystä työstä seuraavalla lausunnolla: "Näistä kaavioista tehdyt asiakirjat... paljastavat yleensä uusia hypo-Hamiltonin ja hypopiirrettyjen graafien luokkia ja osoittavat, että joillekin n :lle tällaisia ​​kaavioita on olemassa, tai että niillä on outoja ja odottamattomia ominaisuuksia."

Sovellukset

Hypo-Hamiltonin graafit esiintyvät matkustavan myyjän ongelman kokonaislukuratkaisuissa - tietyntyyppiset hypo-Hamiltonin graafit määrittelevät puolia matkustavan myyjän monitahoista , kappaletta, joka määritellään matkustavan myyjän ongelman mahdollisten ratkaisujen joukon kuperaksi rungoksi , ja näitä puolia voidaan käyttää leikkaustasomenetelmissä ratkaistaessa tehtävää Gomoryn algoritmilla [7] [6] [8] . Grötschel totesi [6] , että laskennallinen monimutkaisuus määrittää, onko graafi hypo-Hamiltonin graafinen, vaikka sitä ei tunneta, näyttää olevan korkea, mikä vaikeuttaa tämän tyyppisten aspektien löytämistä, lukuun ottamatta pienikokoisten hypo-Hamiltonin graafien määrittelemiä aspekteja. . Onneksi pienimmät kuvaajat johtavat vahvimpiin epäyhtälöihin tietyssä ongelmassa [9] .

Park, Lim ja Kim [10] käyttivät hypo-Hamiltonisuuden kaltaisia ​​käsitteitä mittaamaan rinnakkaisten laskentaverkkotopologioiden vikasietoisuutta .

Ominaisuudet

Jokaisen hypo-Hamiltonin graafin on oltava 3-verteinen , koska minkä tahansa kahden kärjen poistaminen jättää Hamiltonin polun, joka on yhdistetty (graafissa, josta yksi kärki on poistettu, on Hamiltonin sykli ja toisen kärjen poistaminen antaa Hamiltonin polun). On olemassa n-pisteisiä hypo-Hamiltonin graafeja, joissa kärjen maksimiaste on n /2 ja joissa on noin n 2 /4 reunaa [11] .

Hertz, Duby ja Vige arvelivat [5] , että minkä tahansa hypo-Hamiltonin graafin ympärysmitta on 5 tai enemmän, mutta arvauksen kumosi Thomassen [12] , joka löysi esimerkkejä ympärysmitoista 3 ja 4. Ei tiedetty pitkään aikaan, Hypo-Hamiltonin graafit voivat olla tasomaisia , mutta nyt tunnetaan joitain esimerkkejä sellaisista graafista [13] ja pienimmässä näistä graafista on 40 kärkeä [14] . Jokaisella tasomaisella hypo-Hamiltonin graafilla on vähintään yksi kärki, jossa on vain kolme tuloreunaa [15] .

Jos kyseessä on 3-homogeeninen Hamiltonin graafi, sen reunat voidaan värjätä kolmella värillä - käytämme vuorotellen reunojen väritystä kahdella värillä Hamiltonin sykliä pitkin (jonka pitää olla tasainen kädenpuristuslemman mukaan ) ja väritä kaikki loput reunat kolmas väri. Siten kaikkien snarkkien , kuutiomaisten sillattomien graafien, jotka vaativat neljää väriä reunan värjäykseen, on oltava ei-Hamiltonilaisia, ja monet tunnetut snarkit ovat hypo-Hamiltonisia. Mikä tahansa hypokamiltoninen snark on kaksinkertainen – minkä tahansa kahden kärjen poistaminen jättää aligraafin, jonka reunat voidaan värjätä kolmella värillä [16] [17] . Tämän aligraafin kolmivärinen väritys voidaan kuvata helposti - kärjen poistamisen jälkeen jäljellä oleva osa sisältää Hamiltonin syklin. Kun toinen kärki on poistettu, syklistä tulee polku, jonka reunat voidaan värjätä vuorotellen kahdella värillä. Loput reunat muodostavat yhteensopivan , ja kaikki nämä reunat voidaan värjätä kolmannella värillä.

3-homogeenisen graafin minkä tahansa 3-värisen reunavärjäyksen väriluokat muodostavat kolme yhteensovitusta siten, että jokainen reuna kuuluu täsmälleen yhteen yhteensovitukseen. Hypo-Hamiltonin snarkeilla ei ole tämän tyyppistä yhteensopivuutta, mutta Heggquist [18] oletti, että minkä tahansa hypo-Hamiltonin snarkin reunoja voidaan käyttää muodostamaan kuusi yhteensopivuutta siten, että jokainen reuna kuuluu täsmälleen kahteen yhteensovitukseen. Tämä on erikoistapaus Berge–Fulkerson-oletuksesta, jonka mukaan millä tahansa snarkilla on kuusi vastaavuutta tämän ominaisuuden kanssa.

Hypo-Hamiltonin graafit eivät voi olla kaksiosaisia ​​- kaksiosaisessa graafissa kärkipiste voidaan poistaa muodostamaan Hamiltonin aligraafi vain, jos se kuuluu graafin kahdesta väriluokasta suurempaan. Kuitenkin mikä tahansa kaksiosainen graafi esiintyy jonkin hypo-Hamiltonin graafin generoituna aligraafina [19] .

Esimerkkejä

Pienin hypo-Hamiltonin graafi on Petersenin graafi [5] . Yleisemmin yleistetty Petersen-graafi GP( n ,2) on hypo-Hamiltonin, jos n on 5 (mod 6) [20] . Petersenin graafi edustaa tätä konstruktiota, jossa n  = 5.

Lindgren [1] löysi toisen äärettömän hypo-Hamiltonin graafien luokan, jossa pisteiden lukumäärä on 4 (mod 6). Lindgrenin konstruktio koostuu syklistä, jonka pituus on 3 (mod 6) ja yhdestä keskipisteestä. Keskipiste on yhdistetty syklin joka kolmanteen kärkeen reunalla, jota hän kutsuu pinnaksi, ja kärjet, jotka ovat kaksi asemaa pinnan lopullisesta kärjestä, ovat yhteydessä toisiinsa. Jälleen Lindgren-konstruktion pienin edustaja on Petersenin graafi.

Bondy [21] , Doyen ja van Diest [22] sekä Gutt [23] antoivat lisää äärettömiä perheitä .

Luettelo

Vaclav Chvatal osoitti vuonna 1973, että kaikille riittävän suurille n : ille on hypo-Hamiltoneja, joissa on n kärkeä. Kun myöhemmät löydöt [24] [22] otetaan huomioon , "riittävän suuri määrä" tunnetaan nyt, joten tällaisia ​​kaavioita on olemassa kaikille n ≥ 18. Täydellinen luettelo hypo-Hamiltonin graafista, joissa on enintään 17 kärkeä, tunnetaan [ 25] - tämä on Petersenin graafi, jossa on 10 kärkeä, graafit, joissa on 13 ja 15 pistettä, jotka Hertz löysi tietokonehaun avulla [26] , ja neljä graafia, joissa on 16 pistettä. On olemassa ainakin kolmetoista hypo-Hamiltonin graafia, joissa on 18 kärkeä. Soveltamalla Chvatalin trigger-menetelmää [27] Petersenin graafiin ja kukkassnarkiin voidaan osoittaa, että hypo-Hamiltonin graafien lukumäärä, tarkemmin sanottuna hypo-Hamiltonin snarkkien määrä, kasvaa kärkien lukumäärän eksponentiaalina. [28] [29] .

Yleistykset

Teoreetikot tutkivat myös hypopiirrettyjä graafeja , graafisia, jotka eivät sisällä Hamiltonin polkua, mutta joissa mikä tahansa n  − 1 kärjen osajoukko voidaan yhdistää polulla [30] [31] [32] [24] . Jotkut kirjoittajat ovat ehdottaneet samanlaisia ​​määritelmiä hypo-Hamiltonisuuden ja hypodrawability:lle suunnatuille graafeille [33] [34] [35] [15] .

Hypo-Hamiltonin graafien ekvivalentti määritelmä on, että niiden pisimpien syklien pituus on n  − 1 ja kaikkien pisimpien syklien leikkauspiste on tyhjä. Menke ja Zamfirescu [36] tutkivat kuvaajia, joiden ominaisuus on, että pisimpien syklien leikkauspiste on tyhjä, mutta joissa tällaisten syklien pituus on pienempi kuin n  − 1. Hertz [26] määritteli graafin syklisyyden suurimmaksi luvuksi. k siten, että mikä tahansa k pistettä kuuluu sykliin. Hypo-Hamiltonin graafit ovat täsmälleen graafeja, joiden syklisyys on n  − 1. Vastaavasti Park, Lim ja Kim [10] määrittelivät graafin ƒ -stabiilisti ei-Hamiltoniseksi , jos enintään ƒ kärkien poistaminen tuottaa Hamiltonin aligraafin. Schauerte ja Zamfirescu [37] tutkivat kaavioita, joiden syklisyys oli n  − 2.

Muistiinpanot

  1. ↑ 1 2 3 Lindgren, 1967 .
  2. ↑ Sousselier, 1963 .
  3. ↑ Gaudin, Herz, Rossi, 1964 .
  4. ↑ Busacker, Saaty, 1965 .
  5. ↑ 1 2 3 Herz, Duby, Vigué, 1967 .
  6. ↑ 1 2 3 Grötschel, 1980 .
  7. ↑ Grotschel, 1977 .
  8. ↑ Grötschel, Wakabayashi, 1981 .
  9. ↑ Goemans, 1995 .
  10. ↑ 12 Park, Lim, Kim, 2007 .
  11. ↑ Thomassen, 1981 .
  12. ↑ Thomassen, 1974b .
  13. ↑ Tasomaisten hypo-Hamiltonin graafien olemassaolon ongelman esitti avoimena kysymyksenä Václav Chvátal ( Chvátal 1973 ) ja ryhmä Chvátal, Klarner ja Knuth lupasi 5 dollarin palkinnon sellaisen graafin löytäjälle ( Chvátal, Klarner , Knuth 1972 ). Thomassen ( Thomassen 1976 ) käytti Greenbergin lausetta löytääkseen tasomaisia ​​hypo-Hamiltonin kuvaajia, joiden ympärysmitta on 3, 4 ja 5, ja osoitti, että tasomaisia ​​hypo-Hamiltonin kuvaajia on äärettömän monta.
  14. ↑ Löytäjä Juyande, McKay, Östergaard ja Pettersson ( Jooyandeh, McKay, et al. 2013 ) tietokonehaun ja Greenbergin lauseen avulla. Ennen tätä Wiener ja Araya ( Wiener, Araya 2009 ), Hatzel ( Hatzel 1979 ) ja Zamfirescu ( Zamfirescu, Zamfirescu 2007 ) löysivät pienet tasomaiset hypo-Hamiltonin graafit, joissa on 42, 57 ja 48 kärkeä.
  15. ↑ 12 Thomassen , 1978 .
  16. ↑ Steffen, 1998 .
  17. ↑ Steffen, 2001 .
  18. ↑ Häggkvist, 2007 .
  19. ↑ Collier, Schmeichel, 1977 .
  20. ↑ Robertson ( 1969 ) osoitti, että nämä graafit eivät ole Hamiltonin graafisia, vaikka voidaan helposti varmistaa, että yhden kärjen poistaminen antaa Hamiltonin graafin. Katso Alspachin artikkeli ( Alspach 1983 ) ei-Hamiltonin yleistettyjen Petersen-graafien luokittelusta.
  21. ↑ Bondy, 1972 .
  22. ↑ 12 Doyen , van Diest, 1975 .
  23. ↑ Gutt, 1977 .
  24. ↑ 12 Thomassen, 1974a .
  25. ↑ Aldred, McKay, Wormald, 1997 . Katso myös OEIS - sekvenssi A141150 .
  26. ↑ 12 Herz , 1968 .
  27. ↑ Chvatal, 1973 .
  28. ↑ Skupień, 1989 .
  29. ↑ Skupień, 2007 .
  30. ↑ Kapoor, Kronk, Lick, 1968 .
  31. ↑ Kronk, 1969 .
  32. ↑ Grünbaum, 1974 .
  33. ↑ Fouquet, Jolivet, 1978 .
  34. ↑ Grötschel, Wakabayashi, 1980 .
  35. ↑ Grötschel, Wakabayashi, 1984 .
  36. ↑ Menke, Zamfirescu, Zamfirescu, 1998 .
  37. ↑ Schauerte, Zamfirescu, 2006 .

Kirjallisuus

Linkit