Kaksoiskaavio

Tasograafin duaali on graafi, jonka kärjet vastaavat graafin kasvoja ; kaksi kärkeä on yhdistetty reunalla, jos ja vain jos graafin vastaavilla pinnoilla on yhteinen reuna. Esimerkiksi kuutio- ja oktaedrikuvaajat ovat kaksoiskäyrät keskenään .

Termiä duaali käytetään, koska tämä ominaisuus on symmetrinen - jos H on duaali G :n kanssa, niin G on duaali H :n kanssa (olettaen , että G on kytketty ). Samaa käsitettä voidaan käyttää graafien upottamiseen monistoon . Graafin kaksinaisuuden käsite eroaa graafin reuna-vertex -kaksoinnista ( viivakaaviosta ), eikä näitä kahta pidä sekoittaa.

Ominaisuudet

• Kaksoisgraafi on pseudograafi : siinä voi olla silmukoita ja useita reunoja.
• Tasograafin duaali on tasomonigrafi .
• Jos G on yhdistetty graafi ja jos G ′ on G:n duaali , niin G on G ′:n duaali .
• Koska kaksoisgraafi riippuu pinoamismenetelmästä , samassa tasograafissa voi olla useita duaalisia (ei-isomorfisia) . Kuvassa punaiset graafit eivät ole isomorfisia, koska ylemmällä on aste 6 (ulkopinta). Kuitenkin, jos graafi on 3-kytketty , kuten Whitney osoitti , taitto on ainutlaatuinen, ja siksi myös kaksoisgraafi on ainutlaatuinen [1] .

Kaksinaisuuden vuoksi nämä arvot voidaan vaihtaa mille tahansa tulokselle, joka käyttää kasvojen ja kärkien määrää.

Graafin sanotaan olevan itseduaali, jos se on isomorfinen duaaligraafinsa kanssa . Esimerkiksi tetraedrigraafi on itsedual .

Algebrallinen kaksinaisuus

Olkoon G yhdistetty graafi. Graafin G ★ sanotaan olevan algebrallisesti duaali graafin G kanssa siten , että G :llä ja G ★ :llä on samat reunat, mikä tahansa sykli G : ssä on G ★ : n leikkaus ja mikä tahansa G :n leikkaus on G ★ : n sykli . Jokaisella tasograafilla on algebrallinen kaksoisgraafi, joka ei yleensä ole ainutlaatuinen (kaksoisgraafi määräytyy pinoamisen mukaan). Päinvastoin on myös totta – kuten Hassler osoitti tasoisuuskriteerissään [2] , yhdistetty graafi on tasomainen silloin ja vain, jos sillä on algebrallisesti duaaligraafi.

Sama tosiasia voidaan ilmaista matroiditeorialla : jos M on graafin G graafimatroidi : n kaksoismatroidi [en] on graafimatroidi silloin ja vain, jos G on tasomainen. Jos G on tasomainen, niin kaksoismatroidi on G :n kaksoisgraafin graafimatroidi.

Heikko kaksinaisuus

Heikosti duaali tasograafiin on duaaligraafin aligraafi , jonka kärjet vastaavat alkuperäisen graafin rajattuja pintoja. Tasograafi on ulompi silloin ja vain, jos sen duaali on metsä ja tasograafi on Halin-graafi silloin ja vain, jos sen heikosti duaali on kaksinkertaisesti kytketty ja ulompi. Olkoon G + minkä tahansa tasograafin G tasomonigrafi, joka muodostetaan lisäämällä yksi kärki v G :n rajaamattomaan pintaan ja yhdistämällä v kaikkiin ulkopinnan kärkipisteisiin (useita kertoja, jos kärki esiintyy useita kertoja kasvot). Nyt G on G :n (taso)duaalin heikosti duaali + graafi [3] [4] .

Muistiinpanot

1. ↑ Adrian Bondy, USR Murty. luku "Tasograafit", Lause 10.28 // Graafiteoria. - Springer, 2008. - V. 244. - S. 267. - (Matematiikan tutkinnon tekstit). — ISBN 9781846289699 . - doi : 10.1007/978-1-84628-970-5 .
2. ↑ Hassler Whitney. Ei-erotettavissa olevat ja tasomaiset graafit // Transactions of the American Mathematical Society. - 1932. - T. 34 , no. 2 . — S. 339–362 . - doi : 10.1090/S0002-9947-1932-1501641-2 .
3. ↑ Herbert J. Fleischner, D.P. Geller, Frank Harary. Ulompi tasokaaviot ja heikot duaalit // Journal of the Indian Mathematical Society. - 1974. - T. 38 . — S. 215–219 .
4. ↑ 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 .

Linkit

• Weisstein, Eric W. Dual graph  (englanniksi) Wolfram MathWorld -verkkosivustolla .
• Weisstein, Eric W. Self-dual graph  (englanniksi) Wolfram MathWorld -verkkosivustolla .