Grafo dual

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
O grafo G é dual de G', e vice-versa.

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|

Ligações externas[editar | editar código-fonte]

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.