Monitahoinen graafi

Monitahoinen graafi  on suuntaamaton graafi , joka on muodostettu konveksin monitahoisen pisteistä ja reunoista , tai graafiteorian kontekstissa 3-pisteisiin kytketty tasograafi .

Kuvaus

Kuperan polyhedronin Schlegel-diagrammi esittää sen kärjet ja reunat pisteinä ja viivasegmentteinä euklidisessa tasossa , mikä muodostaa ulomman kuperan monikulmion osion pienempiin kupera polygoneihin. Kaaviossa ei ole itseleikkauksia, joten mikä tahansa monitahoinen graafi on myös tasomainen . Myös Balinskyn lauseen mukaan tämä graafi on yhdistetty kärkipisteeseen 3 .

Steinitzin lauseen mukaan nämä kaksi ominaisuutta riittävät kuvaamaan täydellisesti monitahoisia graafisia graafisia piirteitä - ne ovat täsmälleen 3 kärkipisteeseen kytketyt tasograafit. Siten, jos graafi on sekä tasomainen että 3-pisteinen, on olemassa monitahoinen, jonka kärjet ja reunat muodostavat graafin, joka on isomorfinen alkuperäisen kanssa [1] [2] . Kun tällainen graafi on annettu, sen esitys kuperan monikulmion osiona pienemmiksi kuperiksi monikulmioiksi voidaan löytää käyttämällä Tuttan upotusta [3] .

Hamiltonisuus ja lyhyt eksponentti

Tate arveli , että missä tahansa kuutioisessa monitahograafissa (eli monitahoisessa graafissa, jossa kukin kärki kohtaa täsmälleen kolmea reunaa) on Hamiltonin sykli , mutta William Tutt kumosi tämän olettamuksen , joka rakensi vastaesimerkin - ei-Hamiltonin monitahoisen graafin. ( Tatta-kaavio ). Jos lievennämme ehtoa, että graafin on oltava kuutiomainen, tulee näkyviin monia muita pienempiä ei-Hamiltonin monitahoisia graafeja, joista yksi, jossa on 11 kärkeä ja 18 reunaa, on Herschelin graafi [4] , on myös ei-Hamiltonin monitahoinen graafi, jolla on 11 kärkeä, joissa kaikki pinnat kolmion muotoiset - Goldner-graafi - Harari [5] .

Tarkkaan ottaen on olemassa vakio ( lyhyuseksponentti[ tarkentaa ] ) ja ääretön monitahoisten graafien perhe siten, että graafin pisimmän yksinkertaisen polun pituus, jolla on kärjet perheessä, on [6] [7] .

Kombinatorinen luettelointi

Vuonna 1996 määritettiin enintään 26 reunaa sisältävien polyhedraalisten graafien määrä [8] , erityisesti tällaisten 6, 7, ..., 21 reunan graafien lukumäärä on:

1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810 [9] .

Voit myös luetella monitahoiset graafit niiden kärkien lukumäärän mukaan, tällaisten graafien lukumäärä on:

1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, … [10] .

Erikoistilaisuudet

Monitahoinen graafi on yksinkertainen polytooppigraafi, jos se on kuutiomainen (kolme reunaa suppenee kussakin kärjessä), ja se on yksinkertainen polytooppigraafi, jos se on maksimaalinen tasograafi . Halin-graafit , jotka on muodostettu tasomaisista puista lisäämällä ulompi silmukka kaikkien puun lehtien läpi, muodostavat toisen tärkeän monitahograafisen alaluokan.

Muistiinpanot

  1. ↑ Günter M. Ziegler. Luentoja polytoopeista. - 1995. - S. 103, luku 4 "Steinitzin lause 3-polytooppeille". — ISBN 0-387-94365-X .
  2. ↑ Branko Grünbaum. Kuperat polytoopit. - Springer-Verlag, 2003. - Vol. 221. - (Matematiikan tutkinnon tekstit). - ISBN 978-0-387-40409-7 .
  3. ↑ WT Tutte. Kuinka piirtää kaavio // Proceedings of the London Mathematical Society. - 1963. - T. 13 . — S. 743–767 . - doi : 10.1112/plms/s3-13.1.743 .
  4. ↑ Weisstein, Eric W. Herschel Graph  Wolfram MathWorld -verkkosivustolla .
  5. ↑ Weisstein, Eric W. Goldner-Harary Graph  Wolfram MathWorld -verkkosivustolla .
  6. ↑ Weisstein, Eric W. Shortness Exponent  Wolfram MathWorld -verkkosivustolla .
  7. ↑ Branko Grünbaum, TS Motzkin. Pisin yksinkertaiset polut monitahoisissa kaavioissa // Journal of the London Mathematical Society. - 1962. - T. s1-37 , no. 1 . — S. 152–160 . - doi : 10.1112/jlms/s1-37.1.152 .
  8. ↑ AJW Duijvestijn. Monitahoisten (3-liitettyjen tasokaavioiden) lukumäärä  // Laskennan matematiikka. - 1996. - T. 65 . - S. 1289-1293 . - doi : 10.1090/S0025-5718-96-00749-1 . Arkistoitu alkuperäisestä 17. helmikuuta 2019.
  9. ↑ OEIS - sekvenssi A002840 _
  10. ↑ OEIS - sekvenssi A000944 _

Linkit