Dubbel graf

Dualen av en plan graf är en graf där hörnen motsvarar grafens ytor ; två hörn är förbundna med en kant om och endast om motsvarande ytor på grafen har en gemensam kant. Till exempel är kub- och oktaedergraferna dubbla med varandra .

Termen dual används eftersom den här egenskapen är symmetrisk - om H är dual till G så är G dual till H (förutsatt att G är kopplat ). Samma begrepp kan användas för att bädda in grafer i grenrör . Begreppet grafdualitet skiljer sig från kant-vertexdualiteten ( linjediagram ) i en graf och de två bör inte förväxlas.

Egenskaper

På grund av dualitet, för alla resultat som använder antalet ansikten och hörn, kan dessa värden bytas ut.

En graf sägs vara självdual om den är isomorf till dess dubbla graf. Till exempel är tetraedergrafen självdual .

Algebraisk dualitet

Låt G vara en sammanhängande graf. En graf G ★ sägs vara algebraiskt dual till en graf G så att G och G ★ har samma uppsättning kanter, vilken cykel som helst i G är ett snitt av G ★ , och varje snitt av G är en cykel i G ★ . Varje plan graf har en algebraiskt dubbel graf, vilket inte är unikt i det allmänna fallet (den dubbla grafen bestäms av staplingen). Det omvända är också sant – som Hassler visade i sitt planaritetskriterium [2] , är en sammankopplad graf plan om och bara om den har en algebraiskt dubbel graf.

Samma faktum kan uttryckas i termer av matroideori : om M är en grafmatroid av en graf G , så är den dubbla matroiden M en grafmatroid om och endast om G är plan. Om G är plan är den dubbla matroiden grafmatroiden för G :s dubbla graf.

Svag dualitet

Svagt dubbel till en plan graf är en subgraf till den dubbla grafen där hörnen motsvarar de avgränsade ytorna på den ursprungliga grafen. En plan graf är ytterplanar om och endast om dess dual är en skog , och en plan graf är en Halin-graf om och endast om dess svaga dual är dubbelt sammankopplad och yttre plan. För vilken plan graf G som helst , låt G + vara en plan multigraf bildad genom att lägga till en enda vertex v till en obegränsad yta av G och koppla v till alla hörn på den yttre ytan (flera gånger om vertexen förekommer flera gånger på gränsen för ansikte). Nu är G den svagt dualen av den (plana) dualen av G + grafen [3] [4] .

Anteckningar

  1. ↑ Adrian Bondy, USR Murty. kapitel "Planära grafer", Sats 10.28 // Grafteori. - Springer, 2008. - V. 244. - S. 267. - (Examinerade texter i matematik). — ISBN 9781846289699 . - doi : 10.1007/978-1-84628-970-5 .
  2. ↑ Hassler Whitney. Icke-separerbara och plana grafer // Transactions of the American Mathematical Society. - 1932. - T. 34 , nr. 2 . — S. 339–362 . - doi : 10.1090/S0002-9947-1932-1501641-2 .
  3. ↑ Herbert J. Fleischner, D.P. Geller, Frank Harary. Outerplanar grafer och svaga dualer // 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 som hölls i Lagów, Polen, 10–13 februari 1981. - Springer-Verlag, 1983. - Vol 1018. - S. 248-256. — (Föreläsningsanteckningar i matematik). - doi : 10.1007/BFb0071635 .

Länkar