1 Teoria dei grafi Per prima cosa diamo la definizione di grafo. Definizione 1

1 Teoria dei grafi

Per prima cosa diamo la definizione di grafo.

Definizione 1 Un grafo G ´ e costituito da una coppia di insiemi (V, A) dove V ´ e detto insieme dei nodi e A ´ e detto insieme di archi ed ´ e un sottinsieme di tutte le possibili coppie di nodi in V . Se le coppie di nodi sono ordinate, il grafo

´

e detto orientato, se non sono ordinate ´ e detto non orientato.

Esempio 1 Consideriamo un grafo G con insieme di nodi V = {a, b, c, d, e},

mentre l’insieme di archi ´ e il seguente sottinsieme di coppie di nodi in V A = {(a, b); (a, c); (b, c); (b, e); (c, d); (d, b)}

Se tali coppie sono ordinate (e quindi, ad esempio, la coppia (a, b) ´ e diversa dalla coppia (b, a)) il grafo ´ e orientato, altrimenti (e quindi, ad esempio, la coppia (a, b) e la coppia (b, a) sono equivalenti tra loro) il grafo ´ e non orientato.

Per quanto sia in molti casi conveniente mantenere la distinzione tra grafi orien- tati e non orientati, nel seguito ci concentreremo solo sui grafi orientati, osser- vando che per ogni grafo non orientato ne esiste uno orientato equivalente in cui l’insieme di nodi ´ e lo stesso e per ogni coppia non ordinata (i, j) che rappresenta un arco del grafo non orientato si creano due coppie ordinate (i, j) e (j, i) che rappresentano due archi del grafo orientato equivalente. Quindi, se l’esempio visto fosse stato un grafo non orientato, lo avremmo potuto trasformare in uno orientato equivalente con gli stessi nodi ed il seguente insieme di archi

{(a, b); (b, a); (a, c); (c, a); (b, c); (c, b); (b, e); (e, b); (c, d); (d, c); (d, b); (b, d)}

Diamo ora un’altra definizione.

Definizione 2 Dato un grafo orientato G = (V, A) e un arco (i, j) ∈ A diremo che il nodo i ´ e predecessore del nodo j e che il nodo j ´ e successore del nodo i.

Nel grafo dell’esempio, supposto orientato, il nodo a ´ e predecessore del nodo b, mentre b ´ e successore di a. Abbiamo definito un grafo G attraverso la coppia di insiemi V e A. ´ E possibile per´ o rappresentare un grafo anche nei modi seguenti.

Rappresentazione grafica Ad ogni nodo corrisponde un pallino sul piano e ogni arco (i, j) corrisponde ad una linea che congiunge il pallino che rappresenta il nodo i con il pallino che rappresenta il nodo j, su cui si traccia una freccia da i verso j (per grafi non orientati la freccia si omette).

In Figura 1 ´ e mostrata la rappresentazione grafica del grafo dell’esempio.













L L

L L

L L

L























         S

S S

S S

S S

S

a

b

c

d

e

Figura 1:

Tabella 1:

(a, b) (a, c) (b, c) (b, e) (c, d) (d, b)

a 1 1 0 0 0 0

b -1 0 1 1 0 -1

c 0 -1 -1 0 1 0

d 0 0 0 0 -1 1

e 0 0 0 -1 0 0

Liste di adiacenza o rappresentazione analitica Ad ogni nodo si affianca una lista (eventualmente vuota) contenente tutti i suoi successori. Per il nostro esempio le liste di adiacenza sono le seguenti:

a : (b, c) b : (c, e) c : (d) d : (b) e : ∅

Matrice incidenza nodo-arco Si costruisce una matrice con una riga per ogni nodo e una colonna per ogni arco. Nella colonna relativa all’arco (i, j) si mette +1 in corrispondenza della riga i, -1 in corrispondenza della riga j e 0 in corrispondenza di tutte le altre righe. Per il nostro esempio la matrice di incidenza nodo-arco ´ e data in Tabella 1

Introduciamo ora alcune definizioni.

Definizione 3 Un arco (i, i) in cui cio´ e il nodo iniziale e finale coincidono ´ e detto cappio.

Definizione 4 Un grafo privo di cappi e con al pi´ u un arco che congiunge ogni coppia di nodi ´ e detto semplice.

Il grafo dell’esempio ` e semplice.

Definizione 5 Due archi che hanno un nodo in comune sono detti adiacenti.

Nell’esempio gli archi (a, b) e (a, c) sono adiacenti.

Definizione 6 Una sequenza di nodi

v ₀ → v 1 → · · · → v r

tali che

(v i −1 , v i ) ∈ A oppure (v i , v i −1 ) ∈ A ∀ i = 1, . . . , r,

viene detta cammino. Il numero r di archi del cammino ´ e detto lunghezza del cammino. Un cammino ´ e detto semplice se nessun arco ´ e percorso pi´ u di una volta, elementare se nessun nodo viene toccato pi´ u di una volta. I cammini elementari sono casi particolari di cammini semplici.

Nell’esempio, il cammino a → b → d → c ´e un cammino elementare di lunghezza 3; il cammino a → b → c → d → b → e ´e semplice ma non elementare (il nodo b ` e toccato pi` u di una volta); il cammino a → c → d →→ b → a → c non ´e n´e semplice (l’arco (a, b) ` e percorso due volte) n´ e elementare.

Definizione 7 Un cammino semplice in cui l’ultimo nodo coincide con il primo viene detto ciclo. Se il cammino ´ e elementare, cio` e tocca tutti i nodi al pi` u una volta a parte il primo e ultimo nodo, si parla di ciclo elementare.

Nell’esempio a → b → c → a ´e un ciclo elementare.

Definizione 8 Un cammino o un ciclo in cui tutti gli archi sono percorsi secon- do il loro orientamento viene detto orientato, altrimenti si dice non orientato.

Nell’esempio il cammino a → b → c ´e orientato mentre il cammino b → a → c ´e non orientato.

Definizione 9 Dati due nodi i e j di un grafo G, se esiste un cammino da i a j, allora si dice che j ´ e accessibile da i.

La relazione tra i nodi ”´ e accessibile da” ´ e una relazione di equivalenza, ovvero soddisfa le tre propriet´ a riflessiva, simmetrica e transitiva. Come tale induce classi di equivalenza nell’insieme dei nodi. Tali classi di equivalenza vengono dette componenti connesse del grafo. Ogni componente connessa ´ e formata da nodi tutti accessibili tra loro ma non accessibili da nodi in altre componenti.

Definizione 10 Se il grafo contiene una sola componente connessa viene detto connesso.

La seguente procedura consente di individuare le componenti connesse di un grafo e quindi anche di stabilire se un grafo ´ e connesso.

Inizializzazione Si ponga W = V e r = 1.

Passo 1 Si selezioni un nodo i ∈ W e si ponga S = {i} e T r = ∅.

Passo 2 Si selezioni un nodo j ∈ S. Si rimuova j da S e si aggiungano in S tutti i nodi che non siano gi´ a contenuti in T r di cui j ´ e predecessore o successore, cio´ e

S = (S \ {j}) ∪ {k 6∈ T r : (k, j) ∈ A o (j, k) ∈ A}.

Si ponga T r = T r ∪ {j}.

Passo 3 Se S = ∅, allora si vada al Passo 4. Altrimenti si ritorni al Passo 2.

Passo 4 Si ponga W = W \ T r . Se W = ∅, allora T 1 , T ₂ , . . . , T _r sono gli insiemi di nodi delle componenti connesse del grafo. Altrimenti si ponga r = r + 1 e si ritorni al Passo 1.

Come esercizio si applichi la procedura per verificare che il grafo dell’esempio ´ e connesso.

Definizione 11 Un nodo j ´ e detto fortemente accessibile da i se esiste un cammino orientato da i a j.

Si noti che la relazione tra nodi ”´ e fortemente accessibile da” non ´ e una rela- zione di equivalenza. In particolare non vale per essa la propriet´ a di simmetria (nell’esempio e ´ e fortemente accessibile da b ma il viceversa non ´ e vero).

Definizione 12 Un grafo in cui ogni nodo ´ e fortemente accessibile da tutti gli altri ´ e detto fortemente connesso.

Si noti che l’esistenza in un grafo di un ciclo orientato che tocca tutti i nodi del grafo ` e condizione necessaria e sufficiente per garantire che il grafo sia fortemente connesso. Il grafo del nostro esempio non ´ e fortemente connesso (come gi´ a osservato b e anche tutti gli altri nodi del grafo non sono fortemente accessibili da e).

Definizione 13 Un grafo si dice completo se esiste un arco tra ogni coppia di nodi.

Il nostro grafo non ´ e completo. Ad esempio, non c’´ e alcun arco tra a ed e. Lo

´

e invece il grafo G = (V, A) con

V = {a, b, c, d}

e

A = {(a, b); (c, a); (a, d); (b, c); (d, b); (c, d)}

Definizione 14 Dato un grafo G = (V, A) e un sottinsieme A ⁰ ⊆ A, un grafo G ⁰ = (V, A ⁰ ) ´ e detto grafo parziale di G. Dati V ⁰⁰ ⊆ V e

A ⁰⁰ ⊆ A(V ⁰⁰ ) = {(i, j) ∈ A : i ∈ V ⁰⁰ , j ∈ V ⁰⁰ }

il grafo G ⁰⁰ = (V ⁰⁰ , A ⁰⁰ ) viene detto sottografo di G. In particolare, se A ⁰⁰ = A(V ⁰⁰ ) il sottografo viene detto sottografo indotto da V ⁰⁰ .

Nell’esempio G ⁰ = (V, A ⁰ ) con

A ⁰ = {(a, b); (b, c); (b, e); (c, d); (d, b)}

´

e un grafo parziale di G, mentre G ⁰⁰ = (V ⁰⁰ , A ⁰⁰ ) con V ⁰⁰ = {a, b, d} e A ⁰⁰ = {(a, b)}

´

e un sottografo di G. Se invece si considera G ⁰⁰ = (V ⁰⁰ , A ⁰⁰ ) con V ⁰⁰ = {a, b, d} e A ⁰⁰ = {(a, b); (d, b)}

questo ´ e il sottografo di G indotto da V ⁰⁰ .

Definizione 15 Un grafo G = (V, A) si dice bipartito se l’insieme V pu´ o essere partizionato in due sottinsiemi V 1 e V 2 (quindi V 1 ∪ V 2 = V e V 1 ∩ V 2 = ∅) tali che

∀ (i, j) ∈ A : i ∈ V 1 , j ∈ V 2 oppure i ∈ V 2 , j ∈ V 1 .

Un grafo bipartito si dice completo se per ogni coppia di nodi in V ₁ e V ₂ esiste un arco che li congiunge.

Vale la seguente osservazione.

Osservazione 1 Un grafo ´ e bipartito se e solo se non contiene cicli di lunghezza dispari.

La seguente procedura consente di stabilire se un grafo ´ e bipartito.

Passo 1 Si selezioni un nodo i ∈ V e si ponga T 1 = C 1 = {i} e T 2 = C 2 = ∅ Passo 2 Si ponga

T 2 = {k ∈ V \ C 2 : ∃ i ∈ T 1 tale che (i, k) ∈ A oppure (k, i) ∈ A}

Sia C 2 = C 2 ∪ T 2 . Passo 3 Si ponga

T ₁ = {k ∈ V \ C 1 : ∃ i ∈ T 2 tale che (i, k) ∈ A oppure (k, i) ∈ A}

Sia C ₁ = C ₁ ∪ T 1 .

Passo 4 Se C ₁ ∩ C 2 6= ∅, allora il grafo non ´e bipartito. Altrimenti si vada al Passo 5.

Passo 5 Se C 1 ∪ C 2 = V e T 1 = T 2 = ∅, allora il grafo ´e bipartito con V 1 = C 1

e V 2 = C 2 . Altrimenti si ritorni al Passo 2.

Nel nostro esempio selezionando inizialmente il nodo a e ponendolo in T 1 e C 1

avremo

C ₁ a C 2

con T 1 = {a}. Al Passo 2 avremo

C ₁ a C 2 b c con T ₂ = {b, c} e C 2 = {b, c}. Al Passo 3 avremo

C 1 a e d c C ₂ b c

con T ₁ = {e, d, c} e C 1 = {a, e, d, c}. Al Passo 4 notiamo che C 1 ∩ C 2 = {c} 6= ∅ e quindi possiamo concludere che il grafo non ´ e bipartito.

Definizione 16 Sia dato un grafo G = (V, A) con card(V ) = n dove card(V ) denota la cardinalit´ a (il numero di elementi) dell’insieme V . Si dice che G ´ e un albero se soddisfa le seguenti condizioni (equivalenti tra loro)

1. G ´ e privo di cicli e connesso;

2. G ´ e privo di cicli e card(A) = n − 1;

3. G ´ e connesso e card(A) = n − 1;

4. esiste un unico cammino che congiunge ogni coppia di nodi.

Ad esempio, il grafo G = (V, A) con

V = {a, b, c, d, e} A = {(a, b); (b, c); (c, e); (e, d)}

illustrato in Figura 2, ´ e un albero. Vale la seguente osservazione.

Osservazione 2 Dato un albero, l’aggiunta di un solo arco crea esattamente un ciclo.

Definizione 17 Sia dato un grafo connesso G = (V, A). Si definisce albero di

supporto o spanning tree di G un grafo parziale T = (V, A T ) di G (quindi con

A T ⊆ A) che ´e un albero.

E E E E E E

, ,

, ,

, ,

,

, XX XX XX















a

b

c

d

e

Figura 2: Un albero G.

Si noti che un albero di supporto di G deve contenere tutti i nodi di G e che in virt´ u del punto 2. (o del punto 3.) della Definizione 16, si dovr´ a avere card(A T ) = card(V ) − 1.

Esempio 2 Sia dato il grafo G = (V, A) con

V = {a, b, c, d} A = {(a, b); (b, c); (b, d); (a, d); (c, d)}

illustrato in Figura 3. Un albero di supporto di G ´ e il sottografo T ₁ = (V, A _T

₁

) con

A T

₁

= {(b, c); (b, d); (a, d)}

un altro ´ e il sottografo T ₂ = (V, A _T

₂

) con

A T

₂

= {(a, b); (b, c); (c, d)}

I due alberi di supporto di G sono illustrati in Figura 3.

La seguente procedura consente di individuare un albero di supporto di un grafo connesso.

Inizializzazione Si indichino con e 1 , . . . , e m , m = card(A), gli archi del grafo G = (V, A). Si ponga i = 1 e A T = ∅.

Passo 1 Se (V, A T ∪ {e i }) non contiene cicli, allora si ponga A T = A T ∪ {e i }, altrimenti si lasci A T invariato.

Passo 2 Se card(A _T ) = card(V ) − 1, allora (V, A T ) ` e un albero di supporto per il grafo G, altrimenti si ponga i = i + 1 e si ritorni al Passo 1.

1.1 Base di cicli

Introduciamo ora il concetto di base di cicli. Dato un ciclo in un grafo G = (V, A)

ad esso possiamo associare un vettore di dimensione pari a card(A) nel modo

seguente:

E E E E E E ,

, ,

, ,

, , Z ,

Z Z

Z Z

Z Z

Z Z

Z Z

Z Z

Z ,

, ,

, ,

, ,

,

, E

E E E E E

#

#

#

#

#

#

#

#

#

# 













a

b

c

d

a

b

c

d

a

b d

c G

T1 T2

Figura 3: Un grafo G e due suoi alberi di supporto T 1 e T 2 .

1. fisso un orientamento del ciclo;

2. la componente del vettore corrispondente ad un arco (i, j) ∈ A sar´a pari a:

• +1 se l’arco (i, j) viene attraversato dal ciclo nel suo stesso verso.

• -1 se l’arco (i, j) viene attraversato dal ciclo nel verso opposto al suo.

• 0 se l’arco (i, j) non viene attraversato dal ciclo.

Dato il grafo G = (V, A) con

V = {a, b, c, d, e}, e

A = {(a, b); (a, c); (a, e); (c, b); (d, c); (e, d)}

e il ciclo

a → c → d → e → a

con orientamento corrispondente a quello dell’arco (a, c), a tale ciclo associo il vettore

(a, b) (a, c) (a, e) (c, b) (d, c) (e, d)

0 1 −1 0 −1 −1

Se avessi scelto come orientamento quello opposto all’arco (a, c) il vettore sa- rebbe stato il seguente

(a, b) (a, c) (a, e) (c, b) (d, c) (e, d)

0 −1 1 0 1 1

cio´ e uguale al precedente cambiato di segno. La matrice le cui righe sono costi- tuite dai vettori associati a tutti i cicli di un grafo viene detta matrice dei cicli del grafo. Nell’esempio sopra vi sono tre cicli con matrice dei cicli che (a meno di moltiplicazioni per -1 delle righe) ´ e data da

(a, b) (a, c) (a, e) (c, b) (d, c) (e, d)

0 1 −1 0 −1 −1

1 −1 0 −1 0 0

1 0 −1 −1 −1 −1

Il rango di tale matrice, ovvero il massimo numero di vettori riga relativi ai cicli tra loro linearmente indipendenti, ´ e detto numero ciclomatico del grafo ed

´

e indicato con ν(G), mentre un sottinsieme dei cicli i cui corrispondenti vettori riga formano una base dell’insieme dei vettori riga viene detto base di cicli. Nel nostro esempio si pu´ o verificare che il numero ciclomatico ´ e pari a 2 e che i due cicli che si riferiscono alle prime due righe della matrice formano una base di cicli. Si noti che la scelta dell’orientamento dei cicli per la costruzione dei vettori riga non incide sul numero ciclomatico, in quanto moltiplicare una riga di una matrice per -1 non ne modifica il rango. Esistono vari modi per determinare il numero ciclomatico e una base di cicli. La seguente procedura ne ´ e un esempio.

1. Individuare le componenti connesse

G i = (V i , A i ) i = 1, . . . , p del grafo G = (V, A), dove

∪ ^p i=1 V _i = V V _i ∩ V j = ∅ se i 6= j e

∪ ^p i=1 A i = A A i ∩ A j = ∅ se i 6= j

2. Per ogni componente connessa individuare uno spanning tree T _i = (V _i , A ⁰ _i ).

Si noti che si dovr´ a avere

card(A ⁰ _i ) = card(V i ) − 1

3. Aggiungendo un arco in A i \ A ⁰ i si ottiene un unico ciclo che apparterr´ a

alla base di cicli. Ripetendo questo per tutti gli archi in A _i \ A ⁰ i e per tutte

le p componenti connesse, tutti i cicli ottenuti in questo modo formano

una base di cicli.

Si noti che il numero ciclomatico ´ e pari al numero di cicli della base e quindi sar´ a pari a

ν(G) =

p

X

i=1

card(A i \ A ⁰ i ) =

p

X

i=1

[card(A i ) − card(V i ) + 1] =

=

p

X

i=1

card(A i ) −

p

X

i=1

card(V i ) + p da cui

ν(G) = card(A) − card(V ) + p.

Nel nostro esempio si pu´ o verificare che p = 1, mentre card(A) = 6 e card(V ) = 5 da cui ν(G) = 6 − 5 + 1 come gi´a precedentemente osservato. Sempre nell’esempio, se considero l’albero di supporto con gli archi

(a, b) (a, c) (a, e) (e, d) aggiungendo l’arco (c, b) ottengo il ciclo

a → c → b → a e aggiungendo l’arco (d, c) ottengo il ciclo

a → e → d → c → a

I due cicli ottenuti in questo modo formano una base di cicli.

1.2 Grafi planari e topologicamente planari

Introduciamo ora il concetto di grafo topologicamente planare. La denomina- zione topologicamente planare si riferisce alle sole rappresentazioni grafiche dei grafi. Una rappresentazione grafica di un grafo si dice topologicamente planare se il grafo ´ e connesso e se gli archi non hanno punti di contatto diversi dai nodi del grafo. Data la rappresentazione grafica di un grafo in Figura 4, essa non

´

e topologicamente planare in quanto gli archi (a, d) e (b, c) hanno un punto di contatto diverso dai nodi. D’altro canto la rappresentazione grafica in Figura 5 dello stesso grafo ´ e topologicamente planare. Definiremo un grafo planare se ammette almeno una rappresentazione grafica toplogicamente planare. Il grafo G = (V, A) con

V = {a, b, c, d}

e

A = {(a, b); (a, c); (a, d); (b, c); (c, d); (d, b)}

di cui le Figure 4 e 5 sono due distinte rappresentazioni grafiche, ´ e planare

in quanto ammette almeno una rappresentazione topologicamente planare (ad

esempio, quella in Figura 5). Dal disegno possiamo subito stabilire se una

rappresentazione grafica ´ e topologicamente planare. Pi´ u complicato ´ e stabilire

se dato un grafo esso ´ e planare. Avremo bisogno di alcune definizioni.

Q Q

Q Q

Q Q

Q Q

Q Q

Q Q

Q

























a

b

c

d

Figura 4:

Q Q

Q Q

Q Q

Q Q

Q Q

Q Q

Q

a

b

c

d

Figura 5:

Definizione 18 Sia dato un grafo G = (V, A) ed un suo arco (i, j) ∈ A. L’ope- razione di contrazione dell’arco (i, j) consiste nel trasformare il grafo G = (V, A) nel grafo G = (V ⁰ , A ⁰ ) dove i nodi i e j sono sostituiti da un unico nodo s ij , cio´ e

V ⁰ = (V \ {i, j}) ∪ {s ij }

e gli archi sono gli stessi di A per quel che riguarda gli archi che non hanno come estremi i e j, l’arco (i, j) viene soppresso e ogni arco che ha come uno dei due estremi i oppure j sostituisce tale estremo con il nodo s _ij (ad esempio l’arco (k, i) ´ e sostituito con (k, s _ij )). Quindi

A ⁰ = {(k, h) ∈ A : k 6= i, j, h 6= i, j}∪{(s ij , h) : h 6= i, j, (i, h) ∈ A o (j, h) ∈ A}∪

∪{(k, s ij ) : k 6= i, j, (k, i) ∈ A o (k, j) ∈ A} \ {(i, j)}

In Figura 6 ´ e riportato il risultato della contrazione dell’arco (a, b).











hhhhhh











 B

B B

B B

        































hhhh hhhh

a

b c Sab c

d

e d e

Figura 6:

Definizione 19 Indichiamo con K 5 un grafo completo con 5 nodi, ovvero un grafo con 5 nodi ed un arco che congiunge ogni coppia di nodi distinti (si veda la Figura 7).

 







 c

c c

c c

A

A A

A A

A





















E E E E E E E E E E















 Q

Q Q

Q Q

Q Q

Q Figura 7:

Definizione 20 Indichiamo con K _3,3 un grafo bipartito con 3 nodi in ciascuna delle due parti della bipartizione (card(V ₁ ) = card(V ₂ ) = 3)e un arco che con- giunge ogni coppia di nodi delle due parti V ₁ e V ₂ della bipartizione (si veda la Figura 8).

Siamo ora pronti ad enunciare il teorema di Kuratowski che caratterizza i grafi planari.

Teorema 1 Un grafo connesso ´ e planare se e solo se esso stesso ed ogni grafo

ottenuto da esso tramite contrazione di archi non contengono una K 5 o una

K 3,3 .

















@

@

@

@

@

@

@ H H

H H H

H H H H

H H H H

H ,

, , , , , , , ,













@

@

@

@

@

@

@

 

 



 

 

 

 

 

Figura 8:











 c

c c

c c A

A A

A A

A





















E E E E E E E E E E















 Q

Q Q

Q Q

Q Q

Q















b b

b b b

b

c c

c c

c















B B

B B

B

((( ((( (

Figura 9:

Come esercizio si dimostri che il grafo in Figura 9 non ´ e planare.

Data una rappresentazione grafica di un grafo G topologicamente planare, le porzioni di piano limitate individuate dagli archi del grafo vengono dette facce finite del grafo, mentre la restante parte del piano viene detta faccia infinita del grafo. Gli archi che delimitano una faccia finita formano un ciclo della base di cicli del grafo. Quindi, il numero ciclomatico coincide con il numero di facce finite del grafo. In Figura 10 sono mostrate le 3 facce finite e la faccia infinita di un grafo topologicamente planare. Quindi il numero ciclomatico del grafo ´ e 3, ottenibile anche attraverso la formula

card(A) − card(V ) + p = 7 − 5 + 1 = 3,

mentre i cicli a → b → c → a, b → d → c → b e c → d → e → c, i cui archi delimitano le facce finite, formano una base di cicli.

A un grafo topologicamente planare G si pu´ o associare un grafo duale G ⁰ , il

quale ha tanti nodi quante sono le facce (quelle finite pi´ u quella infinita) del grafo G (nell’esempio in Figura 10 sono 3+1=4) e tanti archi quanti sono gli archi di G (nell’esempio sono 7). Per ogni arco (i, j) di G si costruisce un arco

" " " " "

C C

C C

C C Z

Z Z

Z Z

Z a a

a a a a

a a

"

"

"

"

"

"

"

H H H H

H H H

a

b

d

e c

faccia infinita faccia finita

faccia finita

faccia finita

Figura 10:

di G ⁰ che congiunge le due facce che sono separate da tale arco. Nell’esempio l’arco (d, e) separa la faccia finita delimitata dagli archi (c, d) (d, e) (c, e) e la faccia infinita del grafo G e quindi in G ⁰ avremo un arco che congiunge i nodi di G ⁰ corrispondenti a queste due facce. I nodi (cerchi) e gli archi (tratteggiati) del duale del nostro esempio sono mostrati in Figura 11.

d d

d

d

" " " " "

C C

C C

C C Z

Z Z

Z Z

Z a a

a a a a

a a

"

"

"

"

"

"

"

H H H H

H H H

a

b

d

e c

Figura 11: