Duální graf

Duál rovinného grafu je graf , ve kterém vrcholy odpovídají plochám grafu ; dva vrcholy jsou spojeny hranou právě tehdy, když odpovídající plochy grafu mají společnou hranu. Například grafy krychle a osmistěnu jsou vzájemně duální .

Termín duální se používá, protože tato vlastnost je symetrická - pokud H je duální k G , pak G je duální k H (za předpokladu , že G je připojeno ). Stejný pojem lze použít pro vkládání grafů do manifoldů . Pojem duality grafu je odlišný od duality hrany-vrchol ( čárový graf ) grafu a tyto dva by se neměly zaměňovat.

Vlastnosti

• Duální graf je pseudograf : může mít smyčky a více hran.
• Duál rovinného grafu je rovinný multigraf .
• Je-li G souvislý graf a je-li G ′ duál G , pak G je duál G ′.
• Protože duální graf závisí na metodě vrstvení , může existovat několik duálních (neizomorfních) ke stejnému rovinnému grafu . Na obrázku nejsou červené grafy izomorfní, protože horní má stupeň 6 (vnější strana). Pokud je však graf 3-souvislý , jak ukázal Whitney , je fold jedinečný, a proto je jedinečný i duální graf [1] .

Díky dualitě lze tyto hodnoty zaměnit pro jakýkoli výsledek využívající počet ploch a vrcholů.

O grafu se říká, že je samoduální, pokud je izomorfní ke svému duálnímu grafu. Například čtyřstěnný graf je samoduální .

Algebraická dualita

Nechť G je souvislý graf. O grafu G ★ se říká , že je algebraicky duální ke grafu G tak, že G a G ★ mají stejnou sadu hran, každý cyklus v G je řez G ★ a jakýkoli řez G je cyklus v G ★ . Každý rovinný graf má algebraicky duální graf, který není v obecném případě jedinečný (duální graf je určen vrstvením). Platí to i naopak – jak ukázal Hassler ve svém kritériu rovinnosti [2] , souvislý graf je rovinný právě tehdy, když má algebraicky duální graf.

Stejný fakt lze vyjádřit pomocí teorie matroidů : jestliže M je grafový matroid grafu G , pak duální matroid M je grafový matroid právě tehdy, když G je rovinný. Je-li G rovinné, pak duální matroid je grafový matroid duálního grafu G.

Slabá dualita

Slabě duální k rovinnému grafu je podgraf duálního grafu, ve kterém vrcholy odpovídají ohraničeným plochám původního grafu. Rovinný graf je vnějši rovinný právě tehdy, když jeho duál je les , a rovinný graf je Halinův graf právě tehdy, když jeho slabě duální je dvojitě propojený a vnější rovinný. Pro libovolný rovinný graf G nechť G + je rovinný multigraf vytvořený přidáním jediného vrcholu v k neohraničené ploše G a připojením v ke všem vrcholům vnější plochy (několikrát, pokud se vrchol objeví vícekrát na hranici tvář). Nyní G je slabý duál (rovinného) duálu G + graf [3] [4] .

Poznámky

1. ↑ Adrian Bondy, USR Murty. kapitola "Planární grafy", Věta 10.28 // Teorie grafů. - Springer, 2008. - V. 244. - S. 267. - (Absolventské texty z matematiky). — ISBN 9781846289699 . - doi : 10.1007/978-1-84628-970-5 .
2. ↑ Hassler Whitney. Neoddělitelné a rovinné grafy // Transactions of the American Mathematical Society. - 1932. - T. 34 , čís. 2 . — S. 339–362 . - doi : 10.1090/S0002-9947-1932-1501641-2 .
3. ↑ Herbert J. Fleischner, D. P. Geller, Frank Harary. Mimoplanární grafy a slabé duály // Journal of the Indian Mathematical Society. - 1974. - T. 38 . — S. 215–219 .
4. ↑ Maciej M. Sysło, Andrzej Proskurowski. Teorie grafů: Sborník z konference konané v Lagówě, Polsko, 10.–13. února 1981. - Springer-Verlag, 1983. - Vol. 1018. - S. 248-256. — (Poznámky z matematiky). - doi : 10.1007/BFb0071635 .

Odkazy

• Weisstein, Eric W. Duální graf  (anglicky) na webových stránkách Wolfram MathWorld .
• Weisstein, Eric W. Self-dual graph  (anglicky) na webových stránkách Wolfram MathWorld .