Utente:SilsisScalaZarli/Grafo duale

Grafo duale

Sia G un grafo piano. L'insieme $\mathbb {R} ^{2}-G$, ottenuto togliendo dal piano i verici e gli spigoli di G e' ripartito in insiemi aperti connessi di $\mathbb {R} ^{2}$. La chiusura di ciascuno di questi insiemi dicesi faccia di G. La figura mostra un grafo piano G con le facce f₁, f₂, f₃, f₄, f₅. Denotiamo con $a(G)$ il numero delle facce del grafo piano G. Ogni grafo piano ha una faccia illimitata, che si chiama la faccia esterna; nella figura la faccia esterna di G e' la f₅. Vale il teorema seguente: Sia G un grafo planare e v un suo vertice, scelto arbitrariamente. Allora G puo' essere immerso nel piano in modo che v sia sia sulla faccia esterna dell'immersione. Per definizione di grafo planare e' sempre possibile immergerlo su una sfera, allora esiste nel nostro caso un'immersione di G nella sfera e tale immersione la rappresentiamo con G_S. Sia z un punto interno a una faccia contenente v e sia $t(G_{S})$ l'immagine di $G_{S}$ mediante la proiezione stereografica da z. Il grafo $t(G_{S})$ e' un'immersione planare di G del tipo richiesto, poiche' la faccia contenente z e' proiettata nella faccia esterna di $t(G_{S})$.

Si consideri ora il grafo piano G il cui insieme delle facce e' f₁, f₂, f₃, f₄, f₅, ...f_a, il cui insieme degli spigoli e' e₁, e₂, e₃, e₄, e₅, ...e_a.

Categoria:Teoria dei grafi