Duální graf

Technology

12 hours ago

Author

G* je duální graf ke grafu G Dva červené grafy jsou duální k modrým, ale nejsou izomorfní Jako duální graf nějakého rovinného grafu G se v teorii grafů označuje takový graf G*, jehož vrcholy odpovídají stěnám grafu G a hrany vedou mezi každou dvojicí stěn, které sdílejí společnou hranu.

Vlastnosti

duálnost je symetrická vlastnost, tzn. je-li G* duální ke G, pak G je duální ke G* * duální graf každého rovinného grafu je taktéž rovinný * duální graf není určený jednoznačně, to znamená, že pro jeden rovinný graf může existovat více duálních grafů, které nejsou navzájem isomorfní (je to dáno tím, že uspořádání duálního grafu závisí na konkrétním nakreslení tohoto grafu, jichž může být několik) * duální grafy jsou často multigrafy (viz obrázek), protože dvě stěny mohou sdílet více než jednu společnou hranu