ELEMENTI DI TEORIA DEI GRAFI · Un ulteriore rappresentazione di un grafo può essere ottenuta...

ELEMENTI DI TEORIA DEI GRAFI

VINCENZO C. NARDOZZA

La Teoria dei Grafi è uno dei pochi settori della Matematica che abbia unadata di nascita precisa: il primo lavoro sui Grafi fu scritto dal matematico svizzeroLeonardo Eulero, ed apparve nel 1736. Il lavoro di Eulero cominciò con la soluzionedel cosiddetto Problema dei ponti di Königsberg, che esamineremo nel corso dellenote.

1. Concetti di base

Definizione 1.1. Siano V 6= ∅, E insiemi e sia I ⊆ V × E. La terna ordinata(V,E,I ) si dice un grafo se

∀ e ∈ E ∃!{v, w} ∈P2(V ) tale che

{vI e

wI e.

In tal caso, gli elementi di V si dicono vertici, gli elementi di E si dicono spigoli ela relazione I si dice relazione di incidenza vertice-spigolo.

Osservazione 1.2. Ricordiamo che P2(V ) = {A ⊆ V | |A| = 2}. Quindi• non consideriamo grafi le strutture in cui siano presenti self-loops;• non escludiamo che più spigoli possano essere incidenti con la stessa coppia

di vertici.

I grafi che considereremo saranno solo finiti, cioè |V | , |E| <∞.E’ possibile raffigurare graficamente un grafo in modo naturale: ogni vertice è

rappresentato da un punto in un piano, e uno spigolo da una linea che congiunge ivertici ad esso incidenti.

Esempio 1.3. Sia V = {1, 2, 3, 4}, E = {e1, e2, e3, e4, e5, e6} e sia assegnate leincidenze

1Ie1e2e6

, 2I

e1e2e3e4

, 3Ie3e5e6

, 4Ie4e5

Allora possiamo rappresentare la situazione con il disegno seguente:

3 4

21

e1

e2

e4

e5

e6 e3

Definizione 1.4. Sia G = (V,E,I ) un grafo. Il grafo si dice semplice se ognicoppia di vertici individua al più uno spigolo.

1

2 VINCENZO C. NARDOZZA

Definizione 1.5. Un grafoG = (V,E,I ) si dice diretto se è assegnata una funzionef : E → V × V tale che

∀ e ∈ E, f(e) = (u, v)⇒

u 6= v

uI e

vI e

.

Il vertice u si dice il vertice iniziale di e, il vertice v quello finale.

Definizione 1.6. Un grafo G = (V,E,I ) si dice pesato se è assegnata una funzionew : E → R. In tal caso, w(e) si dice il peso dello spigolo e, e la funzione w è dettala funzione peso del grafo.

Definizione 1.7. Sia G = (V,E,I ).• Il numero |V | si dice l’ordine del grafo;• il numero |E| si dice la taglia del grafo;• se v ∈ V , il numero d(v) := |{e ∈ E | vI e}| si dice il grado del vertice v;• un vertice v si dice pari se d(v) è pari; altrimenti si dice dispari;• un vertice di grado 0 si dice un vertice isolato;• i vertici u, v ∈ V si dicono adiacenti se esiste e ∈ E avente u, v come vertici;• gli spigoli e1, e2 ∈ E si dicono adiacenti se esiste un vertice v ∈ V incidente

con entrambi.

Esempio 1.8. Il grafo

•

• •

•

è semplice, i vertici sono tutti a due a due adiacenti, gli spigoli non sono tuttiadiacenti, i vertici del grafo hanno tutti ordine 3.


•

••

è non semplice, ha due vertici di grado 3 e uno di grado 2.

Esempio 1.10. Assegnando f : E → V × V si può rendere il grafo precedente ungrafo diretto:

•

••

Esempio 1.11. Possiamo rendere il grafo pesato, assegnando in qualche modo unpeso a ognuno dei suoi spigoli. Per esempio

•

••2 4

1

7

Ciò equivale a scrivere esplicitamente la funzione w : E → R.

ELEMENTI DI TEORIA DEI GRAFI 3

Teorema 1.12. (Primo Teorema della Teoria dei Grafi)La somma dei gradi dei vertici di un grafo è il doppio della sua taglia; in altritermini

|E| = 1

2

∑v∈V

d(v).

Dimostrazione. Nella somma dei gradi dei vertici, ogni spigolo contribuisce unavolta per ciascuno dei suoi due estremi, quindi due volte in tutto. �

Corollario 1.13. In ogni grafo c’è un numero pari di vertici dispari.

Esempio 1.14. Non ci può essere alcun grafo di 7 vertici in cui cinque abbianogrado 1 e due abbiano grado 2.

Definizione 1.15. Un grafo si dice regolare di grado d se tutti i suoi vertici hannogrado d.

Esempio 1.16. Il grafo••

• •

è un grafo regolare di grado 1 di ordine 4. Il grafo••

• •

è un grafo regolare di grado 2 di ordine 4.

Definizione 1.17. Sia G = (V,E,I ) un grafo di ordine n. Si dice che G è il grafovuoto di ordine n (e lo indicheremo con En) se |E| = 0; si dice che G è il grafocompleto di ordine n (e lo indicheremo con Kn) se

(1) G è semplice;(2) i vertici di G sono tutti a due a due adiacenti.

Esempio 1.18. Di seguito ci sono i grafi completi di ordine 6 6:

•

K1

• •

K2

•

• •K3

••

• •

K4

••

• •

•

K5

•

••

•

• •

K6

Lemma 1.19. Per ogni n > 1 il grafo Kn è regolare di grado n− 1 e di taglia(n2

).

Definizione 1.20. Un grafo G = (V,E,I ) si dice bipartito se esistono V1, V2 ⊆ Vtali che


(1) V1, V2 6= ∅;(2) V1 ∪ V2 = V e V1 ∩ V2 = ∅;(3) i vertici di V1 sono a due a due NON adiacenti, e così pure i vertici di V2.

In tal caso gli insiemi V1, V2 si dicono i partiti del grafo.


•

• •

•

non è bipartito. I grafi

• •

• • •,

•

• •

•

sono bipartito.

Definizione 1.22. Si dice che un grafo è bipartito completo se(1) G è semplice;(2) G è bipartito;(3) ogni vertice di un partito è adiacente a ogni vertice dell’altro partito di G.

In tal caso, se |V1| = m e |V2| = n allora indichiamo il grafo con Km,n.

Esempio 1.23. I grafi bipartito dell’esempio precedente sono completi, e precisa-mente sono i grafi K2,3 e K2,2, rispettivamente.

Definizione 1.24. Sia G = (V,E,I ) un grafo, e siano u, v ∈ V . Si dice percorsoda u a v in G ogni sequenza (finita)

u = v0, e1, v1, e2, v2, . . . , vk−1, ek, vk = v

tale che(1) v1, . . . , vk−1 ∈ V ;(2) e1, . . . , ek ∈ E;

(3) vi−1vi

I ei per ogni i = 1, . . . , k.

In tal caso il numero k si dice la lunghezza del percorso. Il percorso si dice chiusose u = v.

Definizione 1.25. Sia u = v0, e1, v1, e2, v2, . . . , vk−1, ek, vk = v un percorso nelgrafo.

• Il percorso si dice un cammino se gli spigoli e1, . . . , ek sono a due a duedistinti;

• un cammino chiuso si dice un ciclo (o anche un circuito);• il percorso si dice un arco se i vertici v0, . . . , vk−1, vk sono a due a due

distinti, a parte eventualmente v0 = vk, nel qual caso si dice un arco chiuso.

Teorema 1.26. Un grafo G di ordine > 2 è bipartito se e solo se non contienecicli di lunghezza dispari.


Osservazione 1.27. Se G è bipartito, è ovvio che non contiene cicli di lunghezzadispari: se u, e1, v1, e2, v2, . . . , ek, vk = u è un ciclo e, diciamo, u ∈ V2, allorav1, v3, v5, . . . sono tutti in V1. Ma se k fosse dispari, allora u = vk ∈ V1, assurdo.

L’altra implicazione è il vero contenuto del Teorema, ma omettiamo la suadimostrazione in questa sede.

Definizione 1.28. Un grafo G = (V,E,I ) si dice connesso se

∀ {u, v} ∈P2(V ) esiste un percorso da u a v.

Osservazione 1.29. E’ facile vedere che in realtà G è connesso se due qualunquevertici di G sono collegati da un cammino.

Definizione 1.30. Sia G = (V,E,I ) un grafo, e sia u ∈ V un suo vertice.Poniamo:

• Vu := {v ∈ V | esiste in G un percorso da u a v};• Eu := {e ∈ E | i vertici di e sono entrambi in Vu};• Iu = (Vu × Eu) ∩I .

La terna Gu = (Vu, Eu,Iu) è un grafo connesso che include il vertice u, ed è dettola componente connessa di u in G.

Teorema 1.31. Ogni grafo è unione di componenti connesse. In particolare ilgrafo è connesso se ha un’unica componente connessa.

In termini molto informali, un grafo è connesso se “tirando via” uno dei suoivertici, viene via l’intero grafo.

2. Grafi Euleriani e Hamiltoniani

Nel seguito, riteniamo fissato un grafo G = (V,E,I ).

Definizione 2.1. Un cammino in G si dice euleriano se esso include tutti gli spigolidi G. Un ciclo euleriano si dice anche una linea di Eulero del grafo.

Definizione 2.2. Diciamo che G è Euleriano se è un grafo connesso che ammetteuna linea di Eulero.

Ai fini dell’eulerianità, la connessione può essere sostituita da una condizione piùsemplice:

Lemma 2.3. Sia G un grafo di ordine > 2 avente un cammino euleriano. AlloraG è connesso ⇐⇒ G è privo di vertici isolati.

Dimostrazione. E’ ovvio che se G è connesso allora non può avere vertici isolati.Viceversa, ogni componente connessa di G non può essere ridotta a un solo punto(non ci sono punti isolati) e quindi deve contenere almeno uno spigolo. Tale spigolodeve comparire tra gli spigoli del cammino euleriano, e quindi i suoi vertici devonoessere collegati ai vertici di tutte le altre componenti connesse. In definitiva, ci puòessere una sola componente connessa. �

Osservazione 2.4. Dobbiamo notare che il grafo E1 = K1 è connesso, ma è fattoda un vertice isolato.

D’altra parte, l’esistenza di un cammino euleriano non garantisce la connessione:il grafo • • • di ordine 3 ha un cammino euleriano, ma non è connes-so. Tuttavia se il grafo ammette un cammino euleriano, allora le sue componenti


connesse saranno costituite da al più un grafo connesso non banale mentre le altresaranno costituite ciascuna da un singolo vertice isolato. 2

Osservazione 2.5. Se G è privo di vertici isolati e ammette una linea di Eulero,allora necessariamente tutti i suoi vertici sono pari. Infatti, essendo la linea diEulero un ciclo, allora tutti i vertici di G sono toccati almeno una volta dalla linea,e ogni volta che si tocca uno dei vertici vi si entra e vi si esce da spigoli diversi.Questa considerazione in realtà può essere invertita, anche se la cosa non è affattobanale:

Teorema 2.6. (di Eulero, 1736)Se G è privo di vertici isolati e di ordine > 2, allora

G è Euleriano ⇐⇒ G è connesso e tutti i vertici di G sono pari.

Corollario 2.7. Siano u e v vertici distinti di un grafo G privo di vertici isolati.Allora

il grafo ammette un camminoeuleriano da u a v

⇐⇒ u e v sono gli unici vertici disparidi G e G è connesso.

Possiamo tornare a parlare del problema dei ponti di Königsberg: la città èattraversata da un fiume tra le cui sponde si forma un’isoletta. Le sponde e l’isolettasono collegate da sette ponti in tutto, come nella figura seguente:

Il problema è: esiste un punto della città dal quale partire per una passeggiata chepassi per ciascuno dei sette ponti esattamente una volta e che termini nel puntoiniziale? Più in generale, è possibile effettuare una passeggiata che permetta dipassare su ciascuno dei sette ponti esattamente una volta?

Entrambi i problemi possono essere riformulati schematizzando la situazione conil grafo sovrimposto alla figura. Una soluzione al primo problema corrisponde alloraall’esistenza di una linea di Eulero nel grafo. Dato che ciascuno dei vertici ha gradodispari, tale problema non ha soluzione.

Il secondo problema chiede se il grafo ammette un cammino euleriano, ma l’esitoè esattamente lo stesso a causa del corollario al Teorema di Eulero.

In maniera illusoriamente simile al concetto di grafo euleriano possiamo intro-durre la seguente definizione:

Definizione 2.8. Un cammino in un grafo si dice hamiltoniano se tocca tutti ivertici del grafo, ciascuno esattamente una volta. Un cammino hamiltoniano chiusosi dice una linea di Hamilton. Un grafo si dice hamiltoniano se ammette una lineadi Hamilton.

Naturalmente, un grafo hamiltoniano è connesso. In particolare, un grafo hamil-toniano non può avere vertici isolati.

Esempio 2.9. Il grafo K4 è hamiltoniano, e così sono tutti i grafi completi Kn pern > 2. Si noti che K4, invece, non è euleriano. Invece, il grafo


•

••

• •

•

è un grafo connesso, ammette un cammino euleriano ma non uno hamiltoniano.Se cancelliamo il vertice di grado 1 e il relativo spigolo otteniamo un grafo che èeuleriano, non hamiltoniano, ma che ammette un cammino hamiltoniano.

Osservazione 2.10. Le definizioni di grafo euleriano e grafo hamiltoniano sonosolo apparentemente molto simili. E’ degno di menzione il fatto che invece nonesiste un risultato simile al teorema di Eulero che caratterizzi i grafi hamiltoniani.

3. Rappresentazioni e sottografi

Benchè sia abbastanza naturale rappresentare un grafo tramite un disegno, vatenuto in mente che un grafo è un insieme di dati strutturato, e il disegno che fac-ciamo per rappresentare le informazioni contenute nel grafo non è necessariamenteunico. In genere, anzi, più disegni possono essere associati allo stesso grafo.

Esempio 3.1. Il grafo K3,3 può essere rappresentato con i seguenti due disegni:

v1 v2 v3

v4 v5 v6

1

23

4

5 6

Con ciò si intende dire che le informazioni contenute nel primo disegno sono esat-tamente le stesse contenute nel secondo, pur essendo i disegni nettamente diversi.La seguente definizione precisa meglio cosa dobbiamo intendere quando diciamoche due disegni sono rappresentazioni dello stesso grafo.

Definizione 3.2. Siano G = (U,E,I ) e H = (V, F,J ) grafi. I grafi G e H sidicono isomorfi se esiste una funzione ϕ : U ∪ E → V ∪ F tale che

(1) ϕ è bigettiva;(2) ϕ(U) = V , ϕ(E) = F ;(3) ∀u ∈ U, ∀ e ∈ E risulta

uI e ⇐⇒ ϕ(u)Jϕ(e).

Osservazione 3.3. Se G e H sono isomorfi, allora in particolare si ha che• G e H hanno lo stesso ordine;• G e H hanno la stessa taglia;• per ogni v ∈ U si ha d(v) = d(ϕ(v));• per ogni n ∈ N ci sono in G e H lo stesso numero di vertici di grado n;• per ogni n ∈ N, G e H hanno lo stesso numero di cammini di lunghezza n.

Tuttavia, nessuna di queste richieste è sufficiente a garantire che due grafi sianoisomorfi.

Osservazione 3.4. In termini informali, possiamo pensare che due disegni rappre-sentino lo stesso grafo (ovvero, grafi isomorfi) se è possibile modificare uno dei dueallungando o muovendo gli spigoli o i vertici, senza però effettuare tagli o cambidelle incidenze, fino a ottenere il secondo disegno:


Va pertanto tenuta bene in mente la distinzione tra i concetti di grafo (struttura)e rappresentazione del grafo (disegno).

Un altro modo di rappresentare un grafo è il seguente:

Definizione 3.5. Sia G = (V,E,I ) un grafo di ordine n, e fissiamo un ordinetotale su V ; diciamo, V = {v1, . . . , vn}.

Si dice matrice di adiacenza del grafo la matrice

A = (aij) ∈Mn(N) ove aij =∣∣∣∣{e ∈ E ∣∣∣∣ vivj I e

}∣∣∣∣ ,cioè aij è il numero di spigoli che hanno come vertici vi e vj .

Osservazione 3.6. Possiamo registrare le seguenti proprietà della matrice di adia-cenza di un grafo:

• è una matrice quadrata avente 0 come entrate della diagonale principale;• è una matrice simmetrica (cioè AT = A);• il grafo che rappresenta è semplice ⇐⇒ A è una matrice a entrate in{0, 1};• la somma delle entrate della riga i è il grado d(vi).

Teorema 3.7. Siano G = (V,E,I ) e G′ = (V ′, E′,I ′) grafi rappresentati dallematrici di adiacenza A = (aij) e A′ = (a′ij) rispettivamente.

I grafi sono isomorfi se e solo se |V | = |V ′| = n ed esiste una permutazioneσ ∈ Sn tale che a′ij = aσ(i)σ(j) per ogni 1 6 i 6 j 6 n.

Osservazione 3.8. In altri termini, due grafi sono isomorfi se e solo se la matricedi adiacenza di uno dei due può essere ottenuta dall’altra con scambi simultanei dirighe e colonne.

Molte altre proprietà di un grafo possono essere dedotte a partire da una sua ma-trice di adiacenza, ma ciò esula dai nostri scopi. Alcune di tali proprietà, comunque,saranno esaminate tra gli esercizi.

Un ulteriore rappresentazione di un grafo può essere ottenuta tramite un’altramatrice:

Definizione 3.9. Sia G = (V,E,I ) un grafo di ordine m e taglia n, in cui siastato fissato un ordine totale sia in V che in E. Si dice matrice di incidenza delgrafo la matrice I = (bij) ∈Mm×n(N) definita da

bij =

{1 se viI ej

0 altrimenti.

A parte gli isomorfismi della struttura algebrica grafo, è bene chiarire quali sonole sottostrutture:

Definizione 3.10. Sia G = (V,E,I ) un grafo. Un sottografo di G è un grafoG′ = (V ′, E′,I ′) tale che


(1) V ′ ⊆ V , E′ ⊆ E, I ′ ⊆ I ;(2) ogni spigolo e ∈ E′ ha i suoi vertici in V ′.

In pratica G′ viene ottenuto da G cancellando alcuni vertici e alcuni spigoli, mastando attenti a che gli spigoli rimanenti abbiano ancora entrambi i vertici in V ′.

4. Alberi

La seguente definizione isola una categoria molto importante di grafi:

Definizione 4.1. Si dice albero ogni grafo semplice, connesso e privo di cicli.

Sono molte le qualità che caratterizzano un albero, e ciascuna di esse sottolineauno tra gli aspetti peculiari di un grafo di questo tipo:

Teorema 4.2. Sia G = (V,E,I ) un grafo semplice. Sono equivalenti:(1) G è un albero;(2) G è privo di cicli, ma aggiungendo un qualunque spigolo il grafo risultante

ha un ciclo;(3) comunque scelti due vertici u, v del grafo, esiste un unico cammino da u a

v;(4) G è connesso, ma cancellando un qualunque spigolo il grafo risultante non

è più connesso;(5) G è privo di cicli e la sua taglia è |V | − 1;(6) G è connesso e la sua taglia è |V | − 1.

Esempio 4.3. Vediamo i possibili alberi distinti di ordine “piccolo” (n 6 5):

n = 1 •n = 2 • •n = 3 • • •

n = 4 • • • • , • • ••

n = 5 • • • • • , • • ••

•,

•

•••

•

Nell’elenco qui sopra, su ciascuna riga gli alberi rappresentati sono a due a due nonisomorfi, e quelli elencati esauriscono tutte le classi di isomorfismo degli alberi didato ordine.

Definizione 4.4. Sia G = (V,E,I ); un sottografo T di G si dice un alberogeneratore di G se

(1) T è un albero;(2) V (T ) = V (G).

Osservazione 4.5. Naturalmente un grafo G possiede un albero generatore ⇐⇒G è connesso. In realtà G possiede esattamente un albero generatore ⇐⇒ G èesso stesso un albero.

Definizione 4.6. Sia G un grafo pesato connesso, w la sua funzione peso, e T unsuo albero generatore. T si dice di peso minimale se per ogni altro albero generatore


S di G risulta ∑e∈E(T )

w(e) 6∑

e∈E(S)

w(e).

Teorema 4.7. (Algoritmo di Kruskal)Sia G un grafo pesato connesso; si costruisca un sottografo T di G nel modoseguente:

(1) tra gli spigoli non marcati di G e che non formano un ciclo con quelli giàmarcati, si marchi uno di peso minimo;

(2) se gli spigoli già marcati toccano tutti i vertici diG, il grafo T è costituito daivertici di G e dagli spigoli marcati. Altrimenti, si torna al punto precedente.

Il grafo T ottenuto al termine della procedura è un albero generatore di peso mini-male di G.

5. Grafi Planari

In questa sezione, i grafi considerati saranno solo semplici e connessi.

Esempio 5.1. (Problema dei servizi)Tre famiglie, i Verdi, i Bianchi e i Rossi, hanno pari diritto di accesso a tre servizifondamentali: la Farmacia, il Pozzo d’acqua potabile, e la Macelleria. A causadi dissapori precedenti, ciascuna famiglia vuole evitare di incontrare un membrodelle altre mentre si reca presso tali servizi. E’ possibile tracciare degli itinerariper ciascuna famiglia che consenta di usufruire dei servizi senza che si incroci ilpercorso di un’altra famiglia?

Rappresentiamo ogni famiglia e ogni servizio con un punto:

P

M F

V

B R

vogliamo collegare ognuno dei vertici V,B,R con ciascuno dei vertici P , M , F , equindi ottenere un grafo. Sappiamo anche già che il grafo ottenuto sarà isomorfo algrafo bipartito completo K3,3. Tuttavia se procedessimo direttamente otterremmouna rappresentazione del grafo che presenta degli incroci tra gli spigoli, situazioneche vogliamo evitare se cerchiamo una risposta al problema dei servizi:

P

M F

V

B R

Perciò, se vogliamo rispondere al problema, la cosa che dobbiamo chiederci è: esisteuna rappresentazione di K3,3 in cui gli spigoli si intersechino esclusivamente neivertici del grafo?

Il problema dei servizi è un esempio di una intera classe di problemi sui grafi,che ruotano tutti attorno alla seguente


Definizione 5.2. Un grafo si dice planare se fra le sue rappresentazioni graficheve ne è almeno una in cui gli spigoli si intersecano esclusivamente nei vertici.

Esempio 5.3. Il grafo K4 è planare perchè dalla rappresentazione solita si puòottenere una planare come segue:

•

• •

• •

• •

•

In realtà, se un grafo è planare, non c’è bisogno di avere forme strane per glispigoli:

Teorema 5.4. Ogni grafo planare ammette una rappresentazione grafica poligona-le, cioè una rappresentazione planare in cui gli spigoli sono segmenti.

Esempio 5.5. Avevamo già visto che il grafo (planare) K4 ha anche la seguenterappresentazione poligonale

•

•

• •

Quando si ha un grafo planare, di cui scegliamo una rappresentazione poligonale,il piano in cui è rappresentato viene suddiviso in regioni i cui bordi sono poligoni,costituiti dagli spigoli del grafo. Tali regioni hanno un nome particolare:

Definizione 5.6. Sia G un grafo planare e sia D una sua rappresentazione graficapoligonale. Diciamo faccia del grafo ogni regione del piano massimale rispetto allaproprietà che due suoi punti qualunque possono essere collegati tramite una linea(una curva) che NON attraversi alcuno spigolo del grafo.


•

•

• •

individua 4 facce. Il grafo

• •

••

•

• •

individua invece 7 facce.

Osservazione 5.8. E’ importante includere la regione “esterna” F∞ al grafo trale facce, essenzialmente per due motivi: perchè le formule diventano più semplici(primo motivo) e perchè tra le rappresentazioni poligonali del grafo ne esistonosempre alcune in cui la faccia esterna diventa interna, e viene sostituita da unafaccia che, precedentemente, era interna (secondo motivo).


Esempio 5.9. Le seguenti sono due rappresentazioni isomorfe dello stesso grafo:

3 1

24

5

6 7

•

3

1 2

76 5

4

•

Il punto • marcato è interno alla faccia individuata dai vertici 1, 2, 3. Solo che nelprimo caso essa è una faccia interna, nel secondo la faccia esterna.

Osservazione 5.10. La causa di ciò è che un grafo è planare se e solo se ammet-te una rappresentazione data da una sequenza di regioni confinanti su una sfera:tramite la rappresentazione stereografica si passa da un grafo planare a una mappasferica e viceversa.

Più esplicitamente, c’è una corrispondenza biunivoca tra i punti del piano e ipunti della superficie di una sfera privata del polo Nord N e poggiante sul pianostesso. La rappresentazione stereografica è la funzione che a un punto del piano as-socia il punto sulla superficie sferica ottenuto intersecando la stessa con il segmentodi estremi il punto dato ed N .

Per esempio, nella figura al punto P del piano corrisponde il punto R sullasuperficie sferica e, viceversa, al punto Q sulla superficie sferica corrisponde il puntoP ′ sul piano.

In questa maniera, le regioni individuate dalle facce del grafo diventano regioniconfinanti sulla superficie sferica e, tra esse, è inclusa anche quella che, nel piano,è la faccia F∞. 2

Teorema 5.11. (Formula di Eulero)Sia G un grafo planare, D una sua rappresentazione poligonale e sia F l’insiemedelle facce del grafo. Allora

|F |+ |V (G)| = |E(G)|+ 2.

Corollario 5.12. Il numero delle facce di un grafo planare è indipendente dallaparticolare rappresentazione poligonale.

Definizione 5.13. SiaG un grafo planare e D una sua rappresentazione poligonale.Se F è una faccia del grafo, indichiamo con b(F ) il numero di spigoli del grafodelimitanti F .

Teorema 5.14. Il grafo K3,3 non è planare.


Dimostrazione. Supponiamo per assurdo che K3,3 sia planare. Allora avrà unarappresentazione poligonale avente un certo insieme F di facce. Calcoliamo ilnumero

b =∑F∈F

b(F ).

Assegnata una faccia F ∈ F , il numero b(F ) è il numero di “lati” del poligono chedelimita F ; ognuno di tali spigoli separa non più di due facce distinte, e quindi saràcontato in tutto al più 2 volte nel computo di b. Dato che in K3,3 ci sono 9 spigoli,e ognuno di essi può essere contato al più due volte, si ha b 6 2 · 9 = 18.

D’altra parte, il grafo K3,3 è bipartito e quindi non contiene cicli di lunghezza3 (cosiddetti triangoli). Questo vuol dire che nessuna delle sue facce può essere untriangolo, pertanto b(F ) > 4 per ogni F ∈ F . Ma allora si ha

b =∑F∈F

b(F ) >∑F∈F

4 = 4 |F | .

Dalla formula di Eulero, si ha

|F | = |E|+ 2− |V | = 9 + 2− 6 = 5,

e quindi b > 20, contrariamente al fatto che deve essere b 6 18. �

Osservazione 5.15. Ci può essere una grafo planare in cui uno spigolo separameno di due facce? Non dovrebbe essere automatico che ciascuno spigolo separidue facce di un grafo planare?

La risposta è NO: basta prendere un qualunque albero di ordine n > 1 per avereun grafo con una sola faccia! In tal caso, è b = b(F∞) = n− 1, e ciascuno spigolo èil bordo di una sola faccia. 2

Possiamo ora riconsiderare il problema dei servizi: Dato che il grafo K3,3 non èplanare, il problema non ha soluzioni.

Teorema 5.16. Sia G un grafo planare di ordine > 3. Allora

|E| 6 3 |V | − 6.

Inoltre, la limitazione è raggiunta se e solo se tutte le facce del grafo sono triangoli.

Dimostrazione. Come prima, sia F l’insieme delle facce del grafo G e calcoliamo ilnumero

b =∑F∈F

b(F ).

Ogni spigolo di G separa al più due facce, e quindi b 6 2 |E|.Ora, o tutte le facce del grafo sono delimitate da almeno tre lati, oppure ce ne è

una delimitata da meno di tre lati. In tal caso il grafo è necessariamente l’albero diordine 3, e si ha 2 6 9− 6, e la formula vale. Allora, possiamo supporre che tuttele facce siano delimitate da almeno 3 lati, cioè b(F ) > 3 per ogni F ∈ F . Pertanto

b =∑F∈F

b(F ) > 3 |F | .

Di nuovo, dalla formula di Eulero, si ha |F | = |E|+ 2− |V | e quindi

2 |E| > b > 3 |F | = 3 |E|+ 6− 3 |V | ,

che dà la formula asserita. �


Osservazione 5.17. Può ben accadere che la formula sia rispettata ma che il grafonon sia planare! Ciò accade per K3,3, per esempio.

Corollario 5.18. Il grafo K5 non è planare.

Dimostrazione. Il grafo K5 ha 5 vertici e 10 spigoli. Se fosse planare, dovrebbeessere 10 6 3 · 5− 6 = 9, e ciò non è. �

A margine, senza dimostrazione, registriamo anche il seguente risultato:

Teorema 5.19. Se G è un grafo planare di ordine > 3 e privo di triangoli, allora|E| 6 2 |V | − 4.

Osservazione 5.20. Dal risultato appena dato consegue che il grafo K3,3 non puòessere planare: è privo di triangoli, ha ordine > 3 ma ha 9 spigoli, mentre dovrebbeaverne al più 8. 2

Un importante risultato di Kuratowski getta un po’ di luce sulla difficile questionedella planarità di un grafo. Senza scendere nei dettagli, i “genitori” dei grafi nonplanari sono precisamente i grafi K3,3 e K5, cioè un grafo è non planare se e solose possiede un sottografo che è ottenuto da K3,3 o K5 tramite una serie finita dicerte operazioni dette suddivisioni. Perciò i due grafi presentati, K3,3 e K5, sonola vera ostruzione alla planarità.


6. Esercizi

Esercizio 6.1. Sedici persone sono sedute attorno a un tavolo circolare, e ciascunadi esse stringe la mano ai primi due sulla sua destra e ai primi due sulla sua sinistra.Quante strette di mani sono state scambiate, in totale?

Esercizio 6.2. Se G è un grafo semplice con n vertici, qual è il numero massimodi spigoli che può avere?

Esercizio 6.3. Si provi che se G è un grafo semplice di ordine > 2 allora tra i suoivertici ce ne sono almeno due che hanno lo stesso grado.

Questo fatto continua a essere vero se rimuoviamo l’ipotesi che il grafo siasemplice?

Esercizio 6.4. Siano

V = {x, y, z, t, w}E = {{x, y}, {y, z}, {z, t}, {w, y}, {t, w}, {x, w}, {y, t}},

e si consideri la relazione ∀ v ∈ V, e ∈ E:

vI e ⇐⇒ v ∈ e.

(1) Si provi che la struttura G = (V,E,I ) è un grafo, e se ne dia una rappre-sentazione grafica.

(2) Posto V ′ = {y, z, w}, E′ = {{y, w}, {y, z}}, la struttura (V ′, E′,I ′)(dove I ′ = I ∩ (V ′ × E′)) è un sottografo di G?

(3) Similmente, considerando V ′′ = {x, y, z} ed E′′ = {{x, y}, {y, z}, {y, w}}si ha un sottografo di G?

Esercizio 6.5. Disegnare, se possibile, un grado regolare di grado h ed ordine nnei seguenti casi:

(1) n = 3 e h = 2;(2) n = 4 e h = 2, 3;(3) n = 5 e h = 2, 3, 4;(4) n = 6 e h = 2, 3, 4, 5;(5) n = 7 e 2 6 h 6 6;(6) n = 8 e 2 6 h 6 7;(7) n = 9 e 2 6 h 6 8.

Giustificare la risposta nel caso in cui un siffatto grafo non esista. Quali dei grafiottenuti sono completi?

Esercizio 6.6. Esiste un grafo di ordine 13 i cui vertici v1, . . . , v13 abbiano iseguenti gradi:

∀ 1 6 i 6 13 d(vi) =

{3 se i è dispari4 se i è pari

?

Esercizio 6.7. Sia G un grafo semplice, di ordine n > 2 e non connesso. Qualepuò essere, al massimo, la sua taglia?

Esercizio 6.8. G è un grafo con n > 1 vertici e con m < n− 1 spigoli. Può essereconnesso?


Esercizio 6.9. Quanti cammini distinti hanno vertice finale c nel grafo

a

b

c d

e?

Esercizio 6.10. Stabilire quali tra i seguenti grafi sono isomorfi, motivando larisposta:

• • •

• •

••

•

• •

• •

• • •

Esercizio 6.11. Stabilire se i due grafi seguenti sono isomorfi:

• •

••

•

•

••

•

• ••

•••

•••

Esercizio 6.12. Sia V = {v1, v2, v3, v4, v5} e consideriamo la funzione f : V → V

definita da f ≡(v1 v2 v3 v4 v5v4 v3 v4 v5 v4

). Si ponga E = {{v, f(v)} | v ∈ V }, con la

ovvia relazione I di incidenza.(1) Si tracci una rappresentazione del grafo e si scriva una matrice di adiacenza

del grafo G = (V,E,I );(2) si determini il grado di ogni vertice di G;(3) definita la funzione g : E → V × V tramite g({v, f(v)}) = (v, f(v)), si

rappresenti il grafo orientato (G, g) così ottenuto.

Esercizio 6.13. Esiste un grafo di ordine 40 in cui i vertici v1, v2, . . . , v40 abbianogrado dato da d(vi) = i (i = 1, . . . , 40) ?

Esercizio 6.14. Esiste un grafo di ordine 12 in cui i gradi dei vertici v1, . . . , v12

siano dati da d(vi) =

{1 se i è dispari2 se i è pari

?

Esercizio 6.15. Se G è un grafo in cui tutti i vertici hanno grado > 2, allora Gdeve contenere almeno un ciclo. Provare o confutare questa affermazione.

Esercizio 6.16. Si provi che se Km,n è regolare allora m = n.

Esercizio 6.17. Si dica, motivando la risposta, se K4 è un sottografo di K4,4.

Esercizio 6.18. Si disegnino tutti gli alberi non isomorfi di ordine 6 e 7, giusti-ficando sia la completezza dell’elenco sia il fatto che i suoi grafi sono tutti a due adue non isomorfi.

Esercizio 6.19. Si provi che ogni albero di ordine > 2 è bipartito.

Esercizio 6.20. Si dica, motivando la risposta, se i due alberi


•••

•• • •

•••

sono o no isomorfi.

Esercizio 6.21. Si disegnino, se possibile,(1) un albero di ordine 5 avente un vertice di grado 4 e quattro di grado 1;(2) un albero di ordine 5, con due vertici di grado 1 e tre vertici di grado 2.

Esercizio 6.22. Stabilire quali tra le seguenti sono una coppia di grafi isomorfi:

(a)••• •••

••

• •

••

(b)••

• •

••

••

••

••

(c)••

••

••

••

••

••

Esercizio 6.23. Esiste un albero in cui due vertici hanno grado 2, tre vertici hannogrado 3, quattro vertici hanno grado 4 e tutti gli altri vertici hanno grado 1? Senon esiste, perchè? Se esiste, qual è il suo ordine?

Esercizio 6.24. Un grafo bipartito completo del tipo K1,n si dice stella (o ancheun asterisco). Si provi che un grafo bipartito completo Km,n è un albero ⇐⇒ ilgrafo è una stella.

Esercizio 6.25. Si provi che se un albero ha taglia pari allora possiede almeno unvertice pari.

Esercizio 6.26. I vertici di grado 1 di un albero si dicono foglie. Si provi che seun albero T ha un vertice di grado k e nessun vertice di grado > k allora T haalmeno k foglie.

Esercizio 6.27. Un grafo semplice si dice una foresta se ogni sua componenteconnessa è un albero. Una foresta avente k componenti connesse si dice una k-foresta. Si provi che una k-foresta di ordine n ha taglia n− k.

Esercizio 6.28. Sia G un grafo connesso. Si provi cheG è un albero ⇐⇒ G possiede un unico albero generatore.


Esercizio 6.29. Si considerino i seguenti grafi pesati:

•

•

•

• •

•

•

5

2

7

4

6

7

4

5

3

6

3 2

•

• •

•

• •

•

•

•

9

8

7 12

11

10

1

3

2

5

4 6

Per ciascuno di essi si determini un albero generatore di peso minimale e si decidase esso è unico o meno.

Esercizio 6.30. Stabilire quali, tra i seguenti grafi, sono euleriani o posseggonocammini euleriani. Per tali grafi, determinare una linea di Eulero o un camminoeuleriano rispettivamente.

•

• •

• •

•

• •

• • • •

• •

• • •

• •

Esercizio 6.31. Trovare, se esiste, una rappresentazione planare per i seguentigrafi:

•

•

•

•

••

••

•

•

• •

•

• • •

• • • •

•

•

•

••


Esercizio 6.32. Dato il grafo planare

•

•

•

•

•

• •

F1

F2

F3

F4

F5

F6

, dare delle rappre-

sentazioni poligonali dello stesso grafo in cui le facce esterne siano, di volta in volta,F1, . . . , F5.

Esercizio 6.33. Trovare una rappresentazione poligonale del grafo planare

• • • • • • •

Esercizio 6.34. Supponiamo che G sia regolare di grado 3. Se G è planare, quantefacce deve avere?

Esercizio 6.35. Si provi che i grafi

•

•

•

•

•

• •

••

•

•

•

•

• •

•

NON sono isomorfi.

Esercizio 6.36. Si provi che i seguenti grafi sono isomorfi:

•

•

•

• •

•

•

•

•

•

• •

•

•

Esercizio 6.37. Quante sono le mosse di un Re su una scacchiera, secondo leregole degli scacchi?

Esercizio 6.38. Si provi che un grafo regolare di grado 3 ha un numero pari divertici.

Esercizio 6.39. Si scrivano le matrici di adiacenza dei seguenti grafi:


••

••

•

••

•

• •

•• •

••

•

• •

Esercizio 6.40. Si disegnino i grafi le cui matrici di adiacenza sono le seguenti:

0 1 0 1 0 1 01 0 0 1 0 1 00 0 0 1 0 1 01 1 1 0 0 1 00 0 0 0 0 0 11 1 1 1 0 0 10 0 0 0 1 1 0

,

0 1 1 0 0 1 1 01 0 0 1 1 0 0 11 0 0 1 1 0 0 10 1 1 0 0 1 1 00 1 1 0 0 1 1 01 0 0 1 1 0 0 11 0 0 1 1 0 0 10 1 1 0 0 1 1 0

.

Sono grafi regolari?

Definizione 6.1. Se a = (aij) ∈ Mn(F ), si dice traccia di a l’elemento tr (a) :=∑ni=1 aii ∈ F , cioè l’elemento ottenuto sommando gli elementi della diagonale

principale di a.

Esercizio 6.41. Sia a la matrice di adiacenza di un grafo G di ordine n. Si proviche

|E(G)| = 1

2tr(a2).

Esercizio 6.42. Un ciclo di lunghezza 3 in un grafo è detto un triangolo. Si proviche se a è la matrice di adiacenza di un grafo semplice, allora il numero di triangolidel grafo è 1

6 tr(a3).

Esercizio 6.43. Quanti spigoli e quanti triangoli sono presenti nel grafo seguente?

• • • • •

• • • • •

ELEMENTI DI TEORIA DEI GRAFI · Un ulteriore rappresentazione di un grafo può essere ottenuta...

Documents

Transcript of ELEMENTI DI TEORIA DEI GRAFI · Un ulteriore rappresentazione di un grafo può essere ottenuta...