Fleischnerin lause

Fleischnerin lause  on graafiteorian lause, joka antaa riittävän ehdon sille, että graafi sisältää Hamiltonin syklin : jos graafi on 2-kärkinen graafi , niin Hamiltonin graafin neliö . Nimetty Herbert Fleischnerin mukaan, joka julkaisi lauseen todisteen vuonna 1974 .

Määritelmät ja lausunto

Suuntaamaton graafi G on Hamiltonin, jos se sisältää syklin , joka kulkee kunkin kärjen läpi tasan kerran. Graafi on 2-kärkikytketty, jos se ei sisällä artikuloivia pisteitä, eli pisteitä, joiden poistaminen tekee jäljellä olevan graafin irti. Jokainen 2-kärkinen graafi ei ole Hamiltonin. Vastaesimerkkejä ovat Petersen-graafi ja täydellinen kaksiosainen graafi K 2,3 .

Graafin G neliö on  graafi G 2 , jolla on sama pistejoukko kuin graafilla G ja jossa kaksi kärkeä on vierekkäin silloin ja vain, jos niiden välinen etäisyys G :ssä on enintään kaksi. Fleischerin lause sanoo, että äärelliseen 2-pisteeseen yhdistetyn graafin neliön, jossa on kolme tai useampia kärkeä, on aina oltava Hamiltonin. Vastaavasti minkä tahansa 2-kärkisen graafin G kärjet voidaan järjestää sykliseen järjestykseen siten, että vierekkäiset pisteet tässä järjestyksessä G :ssä ovat enintään kahden päässä toisistaan.

Laajennukset

Fleischnerin lauseessa Hamiltonin sykli voidaan rajoittaa sisältämään kolme valittua kahden valitun kärjen kautta kulkevaa reunaa [1] [2] .

Sen lisäksi, että se sisältää Hamiltonin syklin, 2-kärkisen graafin G neliön on oltava myös Hamiltonin-kytkentäinen (eli sillä on Hamiltonin polku , joka alkaa ja päättyy mihin tahansa kahteen valittuun pisteeseen) ja 1-Hamiltonin (eli jos poistat minkä tahansa kärjen, jäljellä oleva graafi sisältää myös Hamiltonin syklin) [3] [4] . Graafin on myös oltava vertex - pancyclic , mikä tarkoittaa, että minkä tahansa pisteen v ja minkä tahansa kokonaisluvun k kohdalla 3 ≤ k ≤ | V ( G )| on k -pituinen sykli, joka sisältää v [5] .

Jos graafi G ei ole 2-kärkikytketty, sen neliöllä voi olla tai ei ole Hamiltonin sykliä, ja sen määrittäminen, onko graafissa tällainen sykli, on NP-täydellinen tehtävä [6] [7] .

Äärettömällä graafilla ei voi olla Hamiltonin sykliä, koska mikä tahansa sykli on äärellinen, mutta Carsten Thomassen osoitti, että jos G on ääretön paikallisesti äärellinen, kärkeen 2 kytketty graafi, jolla on yksi pää, niin G 2 :lla on välttämättä kaksinkertaisesti ääretön Hamiltonin polku [8] . Yleisemmin sanottuna, jos G on paikallisesti äärellinen, 2-kärkinen ja sillä on mikä tahansa määrä päitä, niin G2 : lla on Hamiltonin sykli. Kompaktissa topologisessa avaruudessa , joka muodostetaan käsittelemällä graafia yksinkertaisena kompleksina ja lisäämällä ylimääräinen piste äärettömyyteen graafin kumpaankin päähän, Hamiltonin sykli määritellään aliavaruudeksi, joka on homeomorfinen Euklidisen ympyrän kanssa ja kattaa kaikki kärjet [9 ] [10] .

Historia

Lauseen todistuksen julkaisi Herbert Fliashner vuonna 1971 ja julkaisi vuonna 1974, mikä ratkaisi vuoden 1966 Nash-Williamsin arvelun , jonka myös L.W. totesi itsenäisesti. Bynik ja Plummer [11] . Fleischnerin artikkelia koskevassa katsauksessaan Nash-Williams kirjoittaa, että hän ratkaisi "tunnetun ongelman, joka on estänyt muiden graafiteoreetikkojen kekseliäisyyden useiden vuosien ajan" [12] .

Fleischerin alkuperäinen todiste oli vaikea. Vaclav Chvatal totesi työssään, jossa hän esitteli graafin jäykkyyden käsitteen , että kärkipisteen ja k -kytketyn graafin neliö on välttämättä k -jäykkä. Hän arveli, että 2-jäykät graafit ovat Hamiltonin, mikä johtaisi toiseen todistukseen Fleischerin lauseesta [13] [7] . Myöhemmin tälle olettamukselle löydettiin vastaesimerkkejä [14] , mutta mahdollisuus, että äärellinen jäykkyysraja voisi viitata Hamiltonin syntymiseen, on säilynyt tärkeänä avoimena ongelmana graafiteoriassa. Yksinkertaisemman todisteen sekä Fleischnerin lauseesta että sen Chartrandin, Hobbsin, Youngin ja Kapuurin [3] laajennuksesta antoi Riha [15] [7] [4] ja toisen yksinkertaistetun todisteen teoreemasta antoi Georgakopoulus [16] [ 4 ] ] [10] .

Muistiinpanot

  1. ↑ Fleischner 1976 , s. 125-149.
  2. ↑ Müttel, Rautenbach, 2012 .
  3. ↑ 1 2 Chartrand, Hobbs, Jung, Kapoor, 1974 .
  4. ↑ 1 2 3 Chartrand, Lesniak, Zhang, 2010 .
  5. ↑ Hobbs ( Hobbs (1976 )), vastaus Bondyn hypoteesiin ( Bondy, 1971 ).
  6. ↑ Underground, 1978 .
  7. ↑ 1 2 3 Bondy, 1995 .
  8. ↑ Thomassen (1978) .
  9. ↑ Georgakopoulos, 2009b .
  10. ↑ 12 Diestel , 2012 .
  11. ↑ Fleischner (1974 ). Katso aikaisemmat hypoteesit Fleischner ja Chartrand, Lesniak ja Zhang ( Chartrand, Lesniak, Zhang (2010 )).
  12. ↑ MR : 0332573 .
  13. ↑ Chvatal, 1973 .
  14. ↑ Bauer, Broersma, Veldman, 2000 .
  15. ↑ Shiha, 1991 .
  16. ↑ Georgakopoulos, 2009a .

Kirjallisuus