Duální graf
Z Wikipedie, otevřené encyklopedie
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.
[editovat] 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
