Grafo dual
Aspeto
Este artigo não cita fontes confiáveis. (Agosto de 2020) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/ba/Duals_graphs.svg/300px-Duals_graphs.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7b/Noniso_dual_graphs.svg/300px-Noniso_dual_graphs.svg.png)
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.
Grafo autodual
[editar | editar código-fonte]Um grafo autodual é aquele que é isomorfo ao seu dual.
Propriedades
[editar | editar código-fonte]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|