Grafo dual

Em teoria dos grafos, um grafo dual G' de um grafo planar G é um grafo que tem um vértice por cada região (face) de G, e uma aresta por cada aresta em G que une duas regiões adjacentes.

O grafo G é dual de G', e vice-versa.

Non-iso dual graphs

Grafo autodual

Um grafo autodual é aquele que é isomorfo ao seu dual.

Propriedades

Sendo dois grafos planares G=(V,E) e G'=(V',E'), cujos conjuntos de regiões sejam R e R' , respetivamente, tem-se:

• |E'| = |E|
• |V'| = |R|
• |R'| = |V|

Ligações externas

• «Dual graph definition from MathWorld»