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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.