Sub-Hamiltonin graafi

Ali- Hamiltonin graafi on tasomaisen Hamiltonin graafin osagraafi [1] [2] .

Määritelmä

Graafi G on aliHamiltonin, jos G on jonkin muun graafin aug( G ) aligraafi, jolla on samat kärkijoukot, kun taas graafi aug( G ) on tasomainen ja sisältää Hamiltonin syklin . Jotta nämä ehdot täyttyisivät, itse graafin G on oltava tasomainen ja lisäksi on voitava lisätä tasomaisuutta säilyttäviä reunoja, jotta laajennetussa graafissa luodaan sykli, joka kulkee kaikki kärjet tarkalleen kerran. Graafia aug( G ) kutsutaan graafin G Hamiltonin laajennukseksi [2] .

Osa-Hamiltonin graafi voidaan määritellä Hamiltonin graafin aligraafiksi ilman, että suuremmalla graafilla on sama kärkijoukko. Toisin sanoen tässä vaihtoehtoisessa määritelmässä kärjet ja reunat voitaisiin lisätä. Kuitenkin, jos graafista voidaan tehdä Hamiltoninen lisäämällä pisteitä ja reunoja, se voidaan tehdä Hamiltoniseksi lisäämättä pisteitä, joten tämä ylimääräinen vapaus ei muuta määritelmää [3]

AliHamiltonin graafissa aliHamiltonin sykli on syklinen kärkijono siten, että reunan lisääminen mihin tahansa sekvenssin kärkipariin ei katkaise graafin tasomaisuutta. Graafi on aliHamiltonin, jos ja vain, jos sillä on aliHamiltonin sykli [4] .

Historia ja sovellukset

Sub-Hamiltonin graafien luokan (mutta ei luokan nimeä) ehdottivat Bernhart ja Kainen [5] . He osoittivat, että nämä ovat juuri niitä kaavioita, joissa on kaksi sivua kirjan liitteissä [6] . Sub-Hamiltonin graafit ja Hamiltonin laajennukset käytettiin myös graafisen visualisoinnin alalla ongelmiin, jotka liittyvät graafien upottamiseen universaaliin pistejoukkoon , useiden graafien samanaikaiseen upotukseen ja graafin piirtämiseen kerros kerrokselta [2] .

Liittyvät kaavioperheet

Jotkut tasograafien luokat ovat välttämättä Hamiltonin ja siksi ali-Hamiltonin. Tämä sisältää 4-pisteisiin yhdistetyt graafit [7] ja Halin-graafit [8] .

Mikä tahansa tasograafi, jonka maksimiaste ei ylitä neljää, on Hamiltonin alapuolella [4] , samoin kuin mikä tahansa tasograafi ilman erottavia kolmioita [9] [10] . Jos mielivaltaisen tasograafin reunat jaetaan poluiksi, joiden pituus on kaksi [11] , tuloksena oleva graafi on aina aliHamiltonin [2] .

Muistiinpanot

  1. ↑ Heath, 1987 , s. 198-218.
  2. ↑ 1 2 3 4 Di Giacomo, Liotta, 2010 , s. 35–46.
  3. ↑ Esimerkiksi vuoden 2003 julkaisussa "Graafeiden kirja upotukset ja Whitneyn lause Arkistoitu 29. elokuuta 2017 Wayback Machinessa " Paul Kainen määrittelee osa-Hamiltonin graafit tasomaisten Hamiltonin graafien aligrafeiksi rajoittamatta pisteessä asetettua huippua. laajennettu graafi, mutta kirjoittaa, että "aliHamiltonin graafin määritelmässä voidaan vaatia, että laajennus suoritetaan vain lisäämällä reunoja"
  4. ↑ 1 2 Bekos, Gronemann, Raftopoulou, 2014 .
  5. ↑ Bernhart, Kainen, 1979 .
  6. ↑ Bernhart ja Kainen 1979 , s. 320–331.
  7. ↑ Nishizeki, Chiba, 2008 , s. 171-184.
  8. ↑ Cornuéjols, Naddef, Pulleyblank, 1983 , s. 287-294.
  9. ↑ Kainen, Overbay, 2007 , s. 835–837.
  10. ↑ Erotuskolmio on aligraafi, joka sisältää kolme kärkeä ja kolme reunaa, joiden poistaminen (yhdessä vierekkäisten reunojen kanssa) johtaa graafin jakaantumiseen irrallisiin osiin ( Duncan, Goodrich, Kobourov 2003 ).
  11. ↑ Eli jokainen reuna muunnetaan kahdeksi reunaksi asettamalla kärki reunaan.

Kirjallisuus