Kreivi Halina

Graafiteoriassa Halin-graafi on eräänlainen tasograafi , joka on rakennettu puusta , jossa on vähintään 4 kärkeä, joista millään ei ole täsmälleen kahta naapuria. Puu piirretään tasolle siten, että mikään reuna ei leikkaa, sitten lisätään reunat yhdistämään kaikki sen lehdet sykliksi [ 1] . Halinin laskurit on nimetty saksalaisen matemaatikon Rudolf Halinin mukaan .joka tutki niitä vuonna 1971 [2] , mutta Halinin kuutiokaavioita oli tutkinut sata vuotta aiemmin englantilainen matemaatikko Thomas Kirkman[3] .

Rakentaminen

Halin-graafi rakennetaan seuraavasti: olkoon taso  - upotettu puu, jossa on neljä tai useampia kärkeä siten, että yhdelläkään graafin kärjellä ei ole aste kaksi (eli yhdelläkään kärjellä ei ole tasan kaksi naapuria). Halin-graafi luodaan lisäämällä kuvaajaan sykli, joka kulkee kaikkien lehtien läpi siten, että laajeneva polku pysyy tasomaisena.

Esimerkkejä

Tähti  on puu, jolla on yksi sisäinen kärki. Halinin konstruktiota soveltaen saamme pyörän , pyramidikaavion . Kolmioprismagraafi on myös Halin -graafi - se voidaan piirtää niin, että sen yksi suorakaiteen muotoisista pinnoista on ulompi sykli, ja loput reunat muodostavat puun, jossa on neljä lehteä, kaksi sisäpistettä ja viisi reunaa.

Frucht-graafi , yksi kahdesta pienimmistä kuutiograafisista ei-triviaaleista automorfismista , on myös Halin-graafi.

Ominaisuudet

Mikä tahansa Halin-graafi on 3-kytketty , mikä tarkoittaa, että graafia ei voi jakaa kahdeksi graafiksi poistamalla kaksi kärkeä. Se on myös reuna-minimaalinen 3-kytketty, mikä tarkoittaa, että minkä tahansa reunan poistamisen jälkeen graafi ei ole enää 3-kytketty [1] . Steinitzin lauseen mukaan , koska Halin-graafi on 3-kytkentäinen tasograafi, voidaan esittää konveksin polyhedronin kärkien ja reunojen joukkona . Se on siis monitahoisen kuvaaja , mutta tässä tapauksessa, kuten minkä tahansa monitahoisen graafin kohdalla, sen upottaminen tasoon on ainutlaatuinen siihen asti, kun valitaan pinta, josta tulee sen ulkopinta [1] .

Mikä tahansa Halin-graafi on Hamiltonin graafi ja mikä tahansa reuna kuuluu Hamiltonin sykliin. Lisäksi mikä tahansa Halin-graafi pysyy Hamiltonin muotoisena sen jälkeen, kun se on poistanut minkä tahansa kärjen [4] . Koska mikä tahansa puu, jolla ei ole asteen 2 huippuja, sisältää kaksi lehteä, joilla on sama vanhempi, mikä tahansa Halin-graafi sisältää kolmion. Erityisesti Halin-graafi ei voi olla kolmioton graafi tai kaksiosainen graafi . Tarkemmin sanottuna mikä tahansa Halin-graafi on melkein pansyklinen siinä mielessä, että siinä on kaikenpituisia jaksoja 3:sta n :ään , yhtä parillista pituutta lukuun ottamatta. Lisäksi mikä tahansa Halin-graafi pysyy lähes pansyklisenä yhden reunan supistumisen jälkeen, ja mikä tahansa Halin-graafi, jolla ei ole kolmannen asteen sisäpisteitä, on pansyklinen [5] .

Minkä tahansa Halin-graafin puun leveys on enintään kolme [6] . Siten monet optimointiongelmat, jotka ovat NP-täydellisiä mielivaltaisille kuvaajille, kuten itsenäisen joukon löytäminen Halin-graafille, voidaan ratkaista lineaarisessa ajassa dynaamisen ohjelmoinnin avulla [7] .

Sisäkkäisen tasograafin heikolla duaalilla on tasograafin pintoja vastaavat kärjet ja vierekkäisiä pintoja vastaavat reunat (heikko duaali saadaan duaalista poistamalla ulkopintaa vastaava kärki). Kreivi Halinin heikko kaksoisgraafi on aina kaksikytkentäinen ja ulompi . Tätä ominaisuutta voidaan käyttää Halin-graafien karakterisoimiseen — tasoon upotettu tasograafi on Halin-graafi, jonka lehtikierto on upotuksen ulkopinta, jos ja vain jos sen heikko duaali on kaksinkertaisesti yhdistetty ja ulompi [8] .

Historia

Vuonna 1971 Halin ehdotti graafeja (kutsutaan Halin-grafeiksi) minimiin 3 -vertex-yhdistettyjen graafien luokkaksi - graafin jokaiselle reunalle sen poistaminen vähentää liitettävyyttä [2] . Nämä graafit saivat erityisen merkityksen, kun kävi selväksi, että monet algoritmiset ongelmat, joita on mahdotonta ratkaista mielivaltaisille tasokaavioille, voidaan ratkaista tehokkaasti Halin-graafilla [4] [8] , mikä selitettiin myöhemmin niiden pienen puun leveyden vuoksi [ 6] [7] .

Ennen Halinin työtä Halinin kuutiograafien listausongelmaa käsitteli vuonna 1856 Thomas Kirkman[3] ja vuonna 1965 Hans Rademacher [9] Rademacher kutsui näitä graafisia polyhedriin perustuvia kaavioita . Hän määritteli ne kuutiograafiksi polytooppeista , joissa on f - sivuja, joiden yhdellä pinnalla on f − 1 reunaa. Kuvaajat, jotka täyttävät tämän määritelmän, ovat täsmälleen Halinin kuutiokaavioita.

Halin-graafia kutsutaan joskus myös katottomaksi monitahoiseksi [4] , mutta, kuten nimi "polytooppipohjainen", tämä nimi voidaan liittää kuutiomaisiin Halin-graafisiin [10] . Kupera polyhedra , jonka graafit ovat Halin-graafia, kutsutaan myös kupuiksi [ 11] .

Muistiinpanot

  1. ↑ 1 2 3 Encyclopaedia of Mathematics , ensimmäinen täydentävä osa, 1988, ISBN 0-7923-4709-9 , s. 281, "Halin Graph" -artikkeli Arkistoitu 11. tammikuuta 2014 Wayback Machinessa
  2. ↑ 1 2 Halin. Kombinatorinen matematiikka ja sen sovellukset (Proc. Conf., Oxford, 1969). - Lontoo: Academic Press, 1971. - s. 129-136 .
  3. ↑ 1 2  
  4. ↑ 1 2 3 , DOI 10.1007/BF02591867 
  5. ↑ Skowronska. Syklit kaavioissa. - Elsevier Science Publishers BV, 1985. - T. 27. - S. 179-194. — (Diskreetin matematiikan vuosikirjat).
  6. ↑ 12 Hans Bodlaender . Tasograafit rajatulla puunleveydellä . - Tietojenkäsittelytieteen laitos, Utrechtin yliopisto , 1988. - (Tekninen raportti RUU-CS-88-14).
  7. ↑ 12 Hans Bodlaender . 15. kansainvälisen automaatteja, kieliä ja ohjelmointia käsittelevän kollokvion julkaisut. - Springer-Verlag, 1988. - T. 317. - S. 105-118. — (Luentomuistiinpanot tietojenkäsittelytieteestä).
  8. ↑ 1 2 Maciej M. Sysło, Andrzej Proskurowski. Graph Theory: Proceedings of a Konferenssi, joka pidettiin Lagów'ssa, Puolassa, 10.-13. helmikuuta 1981. - Springer-Verlag, 1983. - Vol. 1018. - P. 248-256. — (Matematiikan luentomuistiinpanot). - doi : 10.1007/BFb0071635 .
  9. ↑ Hans Rademacher. Tiettyjen polyhedratyyppien lukumäärästä // Illinois Journal of Mathematics. - 1965. - T. 9 . - S. 361-380 .
  10. ↑ L. Lovász, M. D. Plummer. Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973). Lontoo: Cambridgen yliopisto Press, 1974. - S. 103-107. Lontoon matematiikka. soc. Luentomuistio Ser., No. 13 .
  11. ↑ Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara. Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Kanada, 8.–10. elokuuta 2013.–2013.–s. 43–48.

Linkit