Duální graf

G' je duální graf ke grafu G

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

Tento matematický článek je příliš stručný nebo neobsahuje důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte.