Топ-100
Indietro

ⓘ Multigrafo duale. Consideriamo un multigrafo planare M e una sua raffigurazione piana planare R. A questa raffigurazione si associa una cosiddetta raffigurazion ..




Multigrafo duale
                                     

ⓘ Multigrafo duale

Consideriamo un multigrafo planare M e una sua raffigurazione piana planare R. A questa raffigurazione si associa una cosiddetta raffigurazione duale R * nel modo seguente. Scegliamo un punto in ogni faccia di R e assegnamogli il ruolo di vertice del nuovo grafo; per ogni spigolo e in R introduciamo un nuovo spigolo di R * collegando i due vertici che in R * corrispondono alle due facce di R che sono incidenti in e. Inoltre raffiguriamo questo spigolo R * in modo che intersechi e esattamente in un punto e non intersechi nessun altro spigolo di R. La raffigurazione R * così ottenuta è anchessa una raffigurazione piana planare di un multigrafo che chiamiamo G *.

La costruzione è tale che si hanno

  • una corrispondenza biunivoca fra vertici di M * facce di M
  • una corrispondenza biunivoca fra spigoli di M e spigoli di M *,
  • una corrispondenza biunivoca fra facce di M * e vertici di M.

Si osserva poi che il multigrafo M ** duale di M * è isomorfo con M: la trasformazione per dualità fra multigrafi astratti è quindi una involuzione e questo giustifica luso del termine "duale". Questo isomorfismo corrisponde alla equivalenza delle rispettive immersioni nella sfera.

                                     

1. Duali di cammini e cappi multipli

Si osserva che il multigrafo duale di un grafo cammino è un multigrafo multicappio, multigrafo con un solo nodo e tanti cappi quanti sono gli spigoli del cammino. Dualmente il multigrafo duale di un multigrafo multicappio è un grafo cammino.

Più in generale se un multigrafo M presenta un sottocammino massimale, cioè una sequenza di spigoli consecutivi con le estremità di grado superiore a 2 ed i rimanenti vertici di grado 2, gli spigoli del multigrafo M * corrispondenti costituiscono una classe di spigoli paralleli. Viceversa ad una classe di spigoli paralleli di M corrisponde un sottocammino massimale di M *.

Se invece M presenta un sottocammino pendente massimale, M * presenta un nodo con più cappi. Dualmente a un nodo con più cappi corrisponde un sottocammino pendente massimale.