Multigrafo duale
Definizione[modifica | modifica wikitesto]
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 (inclusa la faccia illimitata) e assegniamogli 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 è anch'essa una raffigurazione piana planare di un multigrafo che chiamiamo G*.
La costruzione è tale che si hanno
- una corrispondenza biunivoca fra spigoli di M e spigoli di M*,
- una corrispondenza biunivoca fra vertici di M* facce 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 l'uso del termine "duale". Questo isomorfismo corrisponde alla equivalenza delle rispettive immersioni nella sfera.
Duali di cammini e cappi multipli[modifica | modifica wikitesto]
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.
Duali di grafi poliedrali[modifica | modifica wikitesto]
Nel caso in cui G è il grafo (planare) associato a un poliedro convesso, allora G* è il grafo associato al corrispondente poliedro duale.
