Dobbelt graf

Dualen af ​​en plan graf er en graf, hvor hjørnerne svarer til grafens flader ; to hjørner er forbundet med en kant, hvis og kun hvis de tilsvarende flader på grafen har en fælles kant. For eksempel er kube- og oktaedergraferne dobbelte i forhold til hinanden .

Udtrykket dual bruges, fordi denne egenskab er symmetrisk - hvis H er dual til G , så er G dual til H (forudsat at G er forbundet ). Det samme begreb kan bruges til at indlejre grafer i manifolds . Begrebet grafdualitet adskiller sig fra kant-vertex-dualiteten ( linjegraf ) i en graf, og de to bør ikke forveksles.

Egenskaber

• Den dobbelte graf er en pseudograf : den kan have sløjfer og flere kanter.
• Dualen af ​​en plan graf er en plan multigraf .
• Hvis G er en forbundet graf, og hvis G ′ er dualen af ​​G , så er G dualen af ​​G ′.
• Da den dobbelte graf afhænger af stakningsmetoden , kan der være flere dobbelte (ikke-isomorfe) til den samme plane graf . På figuren er de røde grafer ikke isomorfe, fordi den øverste har grad 6 (yderside). Men hvis grafen er 3-forbundet , som Whitney viste , er foldningen unik, og derfor er den dobbelte graf også unik [1] .

På grund af dualitet, for ethvert resultat, der bruger antallet af ansigter og hjørner, kan disse værdier udveksles.

En graf siges at være selvdual, hvis den er isomorf i forhold til dens dobbeltgraf. For eksempel er tetraedergrafen selvdual .

Algebraisk dualitet

Lad G være en sammenhængende graf. En graf G ★ siges at være algebraisk dual til en graf G , således at G og G ★ har det samme sæt kanter, enhver cyklus i G er et snit af G ★ , og enhver snit af G er en cyklus i G ★ . Enhver plan graf har en algebraisk dobbeltgraf, som ikke er unik i det generelle tilfælde (den dobbelte graf bestemmes af stablingen). Det modsatte er også sandt - som Hassler viste i sit planaritetskriterium [2] , er en forbundet graf plan, hvis og kun hvis den har en algebraisk dobbelt graf.

Det samme faktum kan udtrykkes i termer af matroide teori : hvis M er en grafmatroide af en graf G , så er den dobbelte matroide M en grafmatroide, hvis og kun hvis G er plan. Hvis G er plan, så er den dobbelte matroide grafen for G 's dobbelte graf.

Svag dualitet

Svagt dual til en plan graf er en undergraf af den dobbelte graf, hvor hjørnerne svarer til de afgrænsede flader af den oprindelige graf. En plan graf er ydreplanar, hvis og kun hvis dens dual er en skov , og en plan graf er en Halin-graf, hvis og kun hvis dens svage dual er dobbelt forbundet og ydreplanar. For enhver plan graf G , lad G + være en plan multigraf dannet ved at tilføje et enkelt toppunkt v til en ubegrænset flade af G og forbinde v til alle hjørner på den ydre flade (flere gange, hvis toppunktet optræder flere gange på grænsen af ansigt). Nu er G den svage dual af den (plane) dual af G + grafen [3] [4] .

Noter

1. ↑ Adrian Bondy, USR Murty. kapitel "Planære grafer", Sætning 10.28 // Grafteori. - Springer, 2008. - V. 244. - S. 267. - (Kandidattekster i matematik). — ISBN 9781846289699 . - doi : 10.1007/978-1-84628-970-5 .
2. ↑ Hassler Whitney. Ikke-adskillelige og plane 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 og svage 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 afholdt i Lagów, Polen, 10.-13. februar 1981. - Springer-Verlag, 1983. - Vol. 1018. - S. 248-256. — (Forelæsningsnotater i matematik). - doi : 10.1007/BFb0071635 .

Links

• Weisstein, Eric W. Dual graph  (engelsk) på Wolfram MathWorld- webstedet .
• Weisstein, Eric W. Self-dual graph  (engelsk) på Wolfram MathWorld -webstedet .