Kettős gráf

A síkgráf duálisa olyan gráf , amelyben a csúcsok a gráf lapjainak felelnek meg ; két csúcsot akkor és csak akkor köt össze él, ha a gráf megfelelő lapjainak közös éle van. Például a kocka és az oktaéder gráfok duálisak egymással .

A duál kifejezést azért használjuk, mert ez a tulajdonság szimmetrikus – ha H duális G -hez , akkor G duális H -hez (feltételezve , hogy G összefügg ). Ugyanez a fogalom használható gráfok sokaságba ágyazására . A gráf dualitás fogalma különbözik a gráf élcsúcs kettősségétől ( vonalgráf ), és a kettőt nem szabad összekeverni.

Tulajdonságok

A kettősség miatt az oldalak és csúcsok számát használó bármely eredmény esetén ezek az értékek felcserélhetők.

Egy gráfot önduálisnak mondunk, ha izomorf a duális gráfjával. Például a tetraéder gráf önduális .

Algebrai kettősség

Legyen G egy összefüggő gráf. A G ★ gráfról azt mondjuk , hogy algebrailag duális egy G gráfhoz , így G és G ★ élei megegyeznek, G bármely ciklusa G ★ metszete , G bármely metszete pedig G ★ ciklusa . Minden síkgráfnak van algebrai duális gráfja, ami általános esetben nem egyedi (a duális gráfot a halmozás határozza meg). Ennek a fordítottja is igaz – amint Hassler a síkossági kritériumában [2] megmutatta , egy összefüggő gráf akkor és csak akkor sík, ha algebrailag duális gráfja van.

Ugyanez a tény kifejezhető a matroidelméletben is : ha M egy G gráf gráfmatroidja , akkor M duális matroidja akkor és csak akkor gráfmatroid, ha G sík. Ha G sík, akkor a duális matroid G duális gráfjának gráfmatroidja.

Gyenge kettősség

A gyengén duális síkgráfhoz a duális gráf olyan részgráfja , amelyben a csúcsok az eredeti gráf korlátos lapjainak felelnek meg. Egy síkgráf akkor és csak akkor külsõsíkú , ha duálisa egy erdõ , a síkgráf pedig akkor és csak akkor Halin-gráf , ha gyengén duálisa kétszeresen összefüggõ és külsõ síkbeli. Bármely G síkgráf esetén legyen G + egy síkbeli multigráf, amelyet úgy alakítunk ki, hogy egyetlen v csúcsot hozzáadunk G határtalan lapjához, és v -t a külső lap minden csúcsához kapcsoljuk (többször is, ha a csúcs többször is megjelenik a határvonal határán. arc). Most G a G (sík)duálisának gyengén duálisa + a gráf [3] [4] .

Jegyzetek

  1. ↑ Adrian Bondy, USR Murty. fejezet "Síkgráfok", 10.28. Tétel // Gráfelmélet. - Springer, 2008. - V. 244. - P. 267. - (Diplomás szövegek matematikából). — ISBN 9781846289699 . - doi : 10.1007/978-1-84628-970-5 .
  2. ↑ Hassler Whitney. Nem elválasztható és síkbeli gráfok // Transactions of the American Mathematical Society. - 1932. - T. 34 , sz. 2 . – S. 339–362 . - doi : 10.1090/S0002-9947-1932-1501641-2 .
  3. ↑ Herbert J. Fleischner, D. P. Geller, Frank Harary. Outerplanar gráfok és gyenge duálok // Journal of the Indian Mathematical Society. - 1974. - T. 38 . – S. 215–219 .
  4. ↑ Maciej M. Sysło, Andrzej Proskurowski. Graph Theory: Proceedings of a Conference held in Lagów, Poland, 1981. február 10–13. - Springer-Verlag, 1983. - Vol. 1018. - P. 248-256. — (Matematikai előadásjegyzetek). - doi : 10.1007/BFb0071635 .

Linkek