Grafo duale

Da Wikipedia, l'enciclopedia libera.
G′ è il grafo duale di G

Nella teoria dei grafi il grafo duale di un grafo planare (o in generale di un grafo raffigurato su una varietà) G è un nuovo grafo G′ che ha un nodo per ogni regione di G ed un arco per ogni arco di G (due nodi di G′ sono connessi da un arco se e solo se le due corrispondenti regioni di G sono separate da un arco).

Proprietà[modifica | modifica sorgente]

  • Il duale di un grafo planare G è un grafo planare G′ (che può avere cappi e multiarchi anche se G era semplice).
  • Se G è un grafo connesso e G′ è il suo duale, allora G è il duale di G′.
G′ e G″ sono grafi duali di G, ma non sono isomorfi.
  • Un grafo duale non è unico, nel senso che dipende dalla scelta della raffigurazione del grafo di partenza: due distinte rappresentazioni di G possono dare lugo a grafi duali G′ e G″ non isomorfi (come nell'immagine in basso, dove G′ ha un nodo di grado 6 e G″ no).


matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica