Teoria dei Grafi



Un grafo è costituito da:
Un insieme finito di punti, detti nodi o vertici
Un insieme finito di linee, dette archi o spigoli che
uniscono coppie di punti.
Una relazione, detta relazione di incidenza, che ad
ogni spigolo associa i vertici che esso unisce.
Pertanto un grafo può essere rappresentato da un
disegno costituito da punti (vertici) e da linee (spigoli)
che li uniscono a due a due.
Esempi di grafi esistenti ‘in natura’



Una carta stradale può essere presentata come un
grafo i cui nodi sono le città e i cui archi sono le strade
fra una città ed un’altra.
Una molecola può essere rappresentata come un grafo
i cui nodi sono gli atomi che la compongono e i cui
spigoli sono i legami fra gli atomi stessi, determinati
dalle valenze.
Un circuito elettrico può essere rappresentato come un
grafo in cui i nodi sono i componenti (generatori,
resistenze, interruttori) e i cui archi sono i fili elettrici fra
un componente e l’altro.
Concetti di base




Un vertice e uno spigolo da esso uscente si dicono
incidenti. I due vertici incidenti ad uno spigolo si
chiamano anche estremi dello spigolo.
Un laccio è uno spigolo che unisce un vertice a se
stesso. Due spigoli che uniscono la stessa coppia di
vertici si dicono paralleli.
Un grafo privo di lacci e di spigoli paralleli si dice
semplice.
Il grado di un vertice è il numero di spigoli uscenti da
esso.
Esempio
s
E
F
Lo spigolo s forma un
laccio.
A
D
t
C
B
u
G
Gli spigoli t e u sono
paralleli.
I vertici A,B,C hanno grado 3,
E,F,G hanno grado 2, mentre D
ha grado 4.
Il grafo non è semplice, ma se togliessimo gli spigoli s e u
lo diventerebbe.
Grado dei vertici




In un grafo privo di lacci la somma dei gradi dei vertici
è uguale al doppio del numero degli spigoli.
Infatti uno spigolo aumenta di uno il grado dei due
vertici che unisce .
Quindi uno spigolo fa aumentare di 2 la somma dei
gradi dei vertici.
Ne segue che la somma dei gradi dei vertici è un
multiplo di 2.
Grafi isomorfi


Due grafi sono isomorfi se differiscono solo per la
rappresentazione, ma hanno la stessa struttura. In
termini formali:
Due grafi G e H sono isomorfi se esistono una
corrispondenza biunivoca fra i vertici di G e quelli di H
ed una corrispondenza biunivoca fra gli insiemi degli
spigoli di G e quelli di H che conservano la relazione di
incidenza, cioè: ad uno spigolo e ad un vertice incidenti
di G corrispondono uno spigolo ed un vertice incidenti
di H.
Esempio
I due grafi in figura sono isomorfi. (Idea: schiaccia la
faccia superiore del cubo e allarga la faccia inferiore).
Altri esempi
Un’altra coppia di grafi isomorfi. Nel primo vi sono due spigoli
che si intrecciano, nel secondo no. Per avere l’isomorfismo basta
trasformare lo spigolo rosso del grafo di destra nello spigolo
rosso di quello di sinistra.
Altri esempi
I due grafi hanno lo stesso numero di vertici (6) e lo stesso
numero di spigoli (9), ma non sono isomorfi. Perché?
Risposta: il primo grafo ha un solo vertice di grado 4
mentre il secondo ne ha 2 (tali vertici sono colorati in
verde).
Matrici di incidenza



Numeriamo i vertici di un grafo con numeri da
1 a n, ove n è il numero totale dei vertici.
Formiamo una matrice nxn mettendo al posto
i,j il numero di spigoli che uniscono i vertici con
i numeri i e j rispettivamente. La matrice che
otteniamo è detta matrice di incidenza del
grafo.
Vi è una matrice di incidenza per ogni
numerazione dei vertici del grafo.
Esempio
Di seguito sono rappresentati un grafo e la sua matrice
di incidenza
1
2
3
4
0

1
1

2

1 1 2

0 0 0
0 0 1

0 1 0 
La matrice è simmetrica ed ha 0 sulla diagonale. Come
mai?
Esempio
Vediamo ora come cambia la matrice di incidenza se si
cambia la numerazione dei vertici
3
2
4
1
0

0
2

1

0
0
1
2
1
0
0
1
1

0
1

0 
Il cambio di numerazione è rappresentato dalla legge h(1)=3,
h(2)=2, h(3)=4, h(4)=1.
L’elemento di posto i,j nella vecchia matrice si trova ora al
posto h(i),h(j).
In generale:


Due grafi G e H sono isomorfi se prese
comunque due matrici di incidenza di G e di H
esse sono ottenibili una dall’altra con una
permutazione h degli indici come nell’esempio
precedente.
Questo criterio però, pur essendo corretto, non
è efficiente: se i grafi hanno n vertici, per
verificare se sono isomorfi dovremmo provare
tutte le n! permutazioni degli n indici dei vertici.
Cammini


Un cammino in un grafo è una sequenza finita
A1,s1,A2,s2,…,An,sn,An+1 in cui A1, A2,…,An+1,
sono vertici, e s1 unisce A1 e A2, s2 unisce A2 e
A3,…, sn unisce An e An+1 .
Un grafo è connesso se ogni coppia di vertici è
collegata da un cammino.
Esempio
F
D
A
B
E
C
In figura è rappresentato un grafo connesso. La linea
rossa rappresenta un cammino dal nodo A al nodo B.
Grafi non connessi
B
C
E
F
G
D
A
Nel grafo i vertici sono ripartiti in due classi, A,B,C (colorati in nero) e
D,E,F,G (colorati in rosso). Vertici di classi diverse (uno rosso e uno nero)
non sono uniti da nessuno spigolo.
Tale partizione si chiama sconnessione.
Un grafo che ammette una sconnessione non è connesso.
Grafi connessi e grafi sconnessi



Si può dimostrare che un grafo è connesso se
non ha sconnessioni.
Questo criterio non è però efficiente in quanto
se il grafo ha n vertici le possibili partizioni
dell’insieme dei vertici sono 2n.
Vedremo in seguito un metodo più efficiente
per determinare se un grafo è connesso.
Algoritmo per riconoscere se un
grafo è connesso





Inizia una lista con un vertice V a caso.
Aggiungi alla lista tutti i vertici uniti a V da uno spigolo.
Ripeti ricorsivamente la procedura a partire da
ciascuno dei nuovi vertici introdotti.
Se ad un certo punto la lista contiene tutti i vertici del
grafo, il grafo è connesso.
Se ripetendo il procedimento non si ottengono nuovi
elementi nella lista, ma la lista non contiene tutti i
vertici, il grafo non è connesso.
Esempio
Sia G il grafo la cui matrice di incidenza è
1

0
1

0

0
2
0
1
1 0

0 1
2 0

0 1 
Il vertice 1 è unito al vertice 3, il vertice 2 è
unito al vertice 4, e i vertici 1,2,3,4 sono uniti a se stessi.
Applicando l’algoritmo partendo da 1 aggiungo il vertice 3 alla
lista, ma al passo successivo posso solo aggiungere i vertici 1 e 3
che già fanno parte della lista. Quindi il grafo non è connesso
Esempio
Sia G il grafo la cui matrice di incidenza è
1

0
1

0

0
0
2
1
2
1
1
0
0

1
0

1

Applicando l’algoritmo partendo da 1, aggiungiamo alla lista il
vertice 3.
3 è unito a 2 da due spigoli, quindi aggiungiamo 2 alla lista.
2 è unito a 4 da uno spigolo, quindi aggiungiamo anche 4.
Ora la lista contiene tutti i vertici, e il grafo è connesso.
Ponti di Koenisberg

Un classico problema di Teoria dei Grafi è il
seguente: è possibile partendo da un punto
qualsiasi della città di Koenisberg passare da
tutti i ponti della città una volta ed una sola
tornando al punto di partenza?
Esempio: i ponti di Koenisberg
D
C
B
In figura, A e D rappresentano la riva
destra e la riva sinistra del fiume
Pregel, C e B rappresentano le due
isole e gli archi rappresentano i ponti.
A
Esiste un percorso ciclico che passi con continuità da
tutti gli spigoli una volta ed una sola?
Eulero:




La risposta è NO. Infatti:
Se ci fosse un tale cammino, ogni volta che si arriva ad
un vertice attraverso uno spigolo in entrata, dovrebbe
esserci anche un altro spigolo in uscita, diverso da
quello di entrata.
Quindi il grado di ogni vertice dovrebbe essere in
numero pari.
Invece nel problema dei ponti di Koenisberg i vertici
hanno tutti grado dispari (alcuni 3 e altri 5).
Esempio: i ponti di Koenisberg
D
C
B
A
Il vertice B ha grado 5, mentre gli altri vertici hanno grado 3.
Prima o poi entro in un vertice con un ponte senza disporre
di ponti non ancora utilizzati per uscirne.
Grafi Euleriani



Un circuito è un cammino in cui ogni spigolo
compare al massimo una volta e in cui il punto
di partenza e quello di arrivo coincidono.
Un grafo si dice Euleriano se ammette un
circuito che contiene tutti gli spigoli.
Il grafo dei ponti di Koenisberg non è
Euleriano.
Teorema di Eulero


Un grafo è Euleriano se e solo se ogni suo
vertice ha grado pari.
Osservazione. Un circuito Euleriano può
passare più volte dallo stesso vertice, ma non
dallo stesso spigolo.
Esempio
V
Nel grafo disegnato in figura ogni vertice ha grado pari (2 o 4).
Quindi il grafo è Euleriano. Un circuito Euleriano è qui
rappresentato.
Il fatto che il circuito passi due volte per V è irrilevante.
Il problema del commesso
viaggiatore


Un commesso viaggiatore deve visitare vari
clienti dislocati in diverse città. Alcune di
queste città sono collegate in modo diretto da
una strada.
Ci chiediamo se il commesso viaggiatore può
raggiungere tutti i clienti e tornare al punto di
partenza senza passare due volte per la stessa
città.
Il problema del commesso
viaggiatore



Rappresentiamo le città con dei punti e le
strade fra una città e l’altra come linee che
uniscono i punti che le rappresentano.
Otteniamo così un grafo.
Il problema del commesso viaggiatore è quello
di trovare un cammino che passi una volta ed
una sola da tutti i vertici e torni al punto di
partenza.
Il problema del commesso
viaggiatore
v
Nel grafo di sinistra vediamo rappresentato un percorso che passa da
tutti i vertici una ed una sola volta. Il percorso non è Euleriano perché
non passa da tutti gli spigoli.
Nel grafo di destra un simile percorso non c’è (si è costretti a
passare due volte per il vertice V). Al contrario, il grafo di destra è
Euleriano.
Grafi Hamiltoniani



Un ciclo è un circuito che non passa mai due volte
dallo stesso vertice (salvo quello di partenza che
coincide con quello di arrivo).
Un ciclo è Hamiltoniano se contiene tutti i vertici del
grafo.
Un grafo è Hamiltoniano se ammette un ciclo
Hamiltoniano, cioè se ha un circuito che parte da un
vertice e torna al punto di partenza passando una volta
ed una sola per tutti i vertici del grafo.
Grafi Hamiltoniani e grafi Euleriani


Esiste un semplice criterio per stabilire se un grafo è
Euleriano: le somme degli elementi delle linee della
matrice di incidenza (che corrispondono ai gradi dei
vertici) devono essere tutte numeri pari.
Al contrario, non sono noti criteri per stabilire
rapidamente se un grafo è Hamiltoniano o no. (Provare
tutti i cammini possibili e controllare se sono
Hamiltoniani o no ha complessità esponenziale) (nel
caso peggiore vi sono n! cammini)
Grafi ad albero



Un grafo ad albero è un grafo connesso e privo
di cicli.
Si noti che un grafo ad albero è semplice,
poiché un laccio o una coppia di spigoli
paralleli formano un ciclo.
Si può dimostrare che un grafo semplice e
connesso è ad albero se e solo se il numero v
dei vertici supera di uno il numero s degli
spigoli, cioè v=s+1.
Esempi
Il grafo di sinistra è ad albero, quello di destra no.
Conta il numero dei vertici e degli spigoli di entrambi. Cosa
osservi?
Esempi
Nonostante le apparenze, il grafo di sinistra è ad albero,
essendo isomorfo a quello di destra.
Visita di un grafo


Il problema generale è quello di accedere
all’informazione contenuta nei vari nodi di un grafo
utilizzando gli spigoli del grafo stesso per spostarci da
un nodo all’altro. Ad esempio: Come posso visitare il
sito dell’Università di Siena accedendo a tutte le
informazioni in esso contenute?
Vi sono due modi standard per visitare un grafo: la
visita in profondità e la visita in larghezza.
Visita in profondità



L’idea è quella di procedere il più possibile lungo un
ramo del grafo. Quando non è più possibile procedere,
si torna indietro e si riparte da capo. Per semplicità
supporremo che il grafo sia connesso.
Durante il procedimento formiamo due liste: una lista A
dei vertici ancora da visitare e una lista B dei vertici
che sono già stati visitati, ma da cui si possono
raggiungere vertici ancora da visitare.
I vertici che non appartengono a nessuna delle due
liste sono quelli già trattati, e quindi non ce ne
dobbiamo più preoccupare.
Visita in profondità


All’inizio la lista A comprende tutti i vertici e la
lista B è vuota.
Il procedimento termina quando la lista A è
vuota, cioè quando non ci sono più vertici da
visitare.
Visita in profondità
1.
2.
3.




Sia V il primo vertice della lista A. Visita V.
Aggiungi V alla lista B e toglilo dalla lista A.
Fintanto che la lista A non è vuota, ripeti il seguente:
Sia W il primo elemento della lista B.
Se non esistono vertici V nella lista A uniti a W da uno
spigolo, cancella W dalla lista B.
Ripeti finché trovi un V nella lista A unito al primo elemento
W della lista B da uno spigolo. Sia V il primo di questi
Visita V, togli V dalla lista A ed aggiungilo all’inizio della lista
B.
Esempio
Il precorso di visita in profondità di un grafo.
1
2
4
3
5
7
6
Visita in larghezza


L’idea è quella di procedere con una ricerca
ramificata. Invece di andare avanti finchè
possibile in un’unica direzione, si fa un passo
alla volta in tutte le direzioni.
Anche in questo caso supporremo che il grafo
sia connesso.
Visita in larghezza




Anche questa volta useremo due liste, la lista A
dei vertici in lista di attesa, e la lista B dei
vertici già visitati.
Supporremo data anche una lista C di tutti i
vertici.
All’inizio le liste A e B sono entrambe vuote.
Il procedimento termina quando la lista B
comprende tutti i vertici.
Visita in larghezza
1.
2.
3.



Sia V il primo vertice di C.
Poni V nella lista A.
Fintanto che B è diverso da C ripeti il seguente
procedimento:
Sia V il primo vertice della lista A.
Visita V e aggiungilo alla lista B.
Togli V dalla lista A e aggiungi, in fondo alla lista A,
tutti i nodi uniti a V da uno spigolo e che non sono né
nella lista A né nella lista B.
Esempio
1
2
3
4
7
5
6
Il percorso di visita dello stesso grafo in larghezza
Spanning tree
Gli spigoli utilizzati durante la visita di un grafo formano un albero che passa
per tutti i vertici. Un albero con questa proprietà viene detto spanning tree
2
1
4
3
5
7
6
Spanning tree ottenuto con una visita in profondità
Esempio
Spanning tree dello stesso grafo ottenuto con una visita in larghezza
1
2
4
3
5
7
6
Grafi etichettati


Consideriamo ora dei grafi in cui ogni spigolo
ha un’etichetta numerica, che possiamo
pensare come il costo necessario per
percorrerlo.
Ad esempio, in una carta stradale i vertici sono
le città, gli spigoli sono le strade fra una città e
l’altra, e le etichette delle strade sono le loro
lunghezze in chilometri.
Commesso viaggiatore, seconda
versione


Un commesso viaggiatore deve visitare vari
clienti dislocati in varie città, unite fra loro da
strade.
Questo secondo commesso, più furbo del
precedente, non si preoccupa di passare due
volte dalla stessa città, ma piuttosto di visitare
tutti i clienti e di tornare a casa percorrendo
meno strada possibile.
Commesso viaggiatore 2


La situazione questa volta è rappresentata con
un grafo etichettato. I nodi sono le città, gli
spigoli sono le strade fra una città e l’altra, e le
etichette sono le lunghezze delle strade.
Il problema è ora quello di trovare un cammino
che, passando da tutti i vertici del grafo, torni al
punto di partenza, e che renda minima la
somma delle etichette degli spigoli del
cammino stesso.
Algoritmo greedy


Greedy in inglese significa goloso. Un
algoritmo greedy è un algoritmo che cerca di
ottenere subito il massimo possibile, senza
preoccuparsi di seguire strategie a lungo
termine (meglio un uovo oggi che una gallina
domani).
Come vedremo, nel problema del commesso
viaggiatore l’algoritmo greedy non sempre
fornisce la soluzione migliore.
Algoritmo greedy



Parti da un nodo V.
Ad ogni passo, parti dal nodo W a cui sei
arrivato e scegli lo spigolo più corto (di
etichetta minima) fra quelli che connettono W
con un nodo U che non hai ancora visitato.
Visita tale nodo U.
Se ogni nodo unito a W da uno spigolo è già
stato visitato, torna al nodo precedente.
Algoritmo greedy
Il seguente esempio mostra che l’algoritmo greedy non
è sempre il migliore
2
A
C
4
D
3
7
E
3
3
2
A
4
B
C
4
D
3
7
E
3
3
4
B
Il percorso suggerito dall’algoritmo greedy è ADECBA che ha
lunghezza 2+3+7+3+4=19
Il percorso ABCDEA ha lunghezza 4+3+4+3+3=17
Commesso viaggiatore 2


Non è noto (e forse non esiste) nessun
algoritmo rapido per trovare il minimo cammino
che partendo da un vertice passa per tutti i
nodi e torna al punto di partenza.
L’algoritmo che consiste nel provare tutti i
cammini richiede tempo n!, ove n è il numero
dei vertici.
Minimum spanning tree



Ci proponiamo ora di visitare un grafo etichettato, in cui
le etichette numeriche sugli spigoli denotano il costo
per passare da un estremo all’altro.
Anzicché effettuare una visita in profondità o in
larghezza, cerchiamo la visita di costo minimo.
L’albero costituito dagli spigoli utilizzati durante una
tale visita è l’albero di costo minimo che passa per tutti
i vertici. Esso è detto minimum spanning tree.
Algoritmo greedy per il minimum
spanning tree





L’idea è quella di aggiungere di volta in volta lo spigolo
meno costoso fra quelli che non sono superflui.
Uno spigolo è superfluo se insieme agli altri già
introdotti forma un ciclo.
Algoritmo: Fintanto che esiste un nuovo spigolo non
ancora introdotto che non crea un ciclo, ripeti la
seguente procedura:
Aggiungi lo spigolo di costo minimo fra quelli non
ancora introdotti che non creano cicli.
L’algoritmo termina appena aggiungendo un qualunque
nuovo spigolo si crea un ciclo.
Minimum spanning tree



L’algoritmo produce il minimum spanning tree.
Sia infatti M il minimum spanning tree, e sia T
l’albero prodotto dall’algoritmo. Supponiamo
per assurdo che siano diversi.
Sia s il minimo spigolo di M che non è in T.
Siano s1,…,sn gli spigoli di M di costo minore
di s. Essi sono anche in T.
Sia t lo spigolo di T introdotto subito dopo
s1,…,sn . Si ha che t ha costo minore di s.
Minimum spanning tree




Essendo M connesso, gli estremi di t sono uniti da un
cammino in M.
Almeno uno spigolo u di tale cammino non è in T,
altrimenti aggiungendo t a tale cammino avremmo un
ciclo in T.
Sia v un tale spigolo. Si vede subito che v ha costo
maggiore di t.
Rimpiazzando in M lo spigolo v con t otteniamo uno
spanning tree di costo inferiore. Raggiungiamo così un
assurdo.
Esempio
Vogliamo determinare il minimum spanning tree del grafo
disegnato sotto
B
2
A
1,5
C
7
G
3,5
4
K
6,5
6
D
2,5
3
5
H
4,5
5,5
F
E
Gli spigoli introdotti sono: BC, BA, AD, DE, FH, DF, DG, GK.
Esempio
Il minimum spanning tree del grafo è disegnato sotto in rosso
1,5
7
2
4
3,5
6,5
6
2,5
5
3
5,5
4,5
Esempio
1,2
E
3,5 1
A
2,5
4
B
.
F
1,6
1,5
D
G
3,8
C
3
Un altro esempio di minimum spanning tree. L’ordine
degli spigoli è: DE, EF, DG, AD, BC, CD.
Colorazioni


Un famoso problema matematico è quello di
dimostrare che una qualsiasi carta geografica può
essere colorata con quattro colori in modo che due
qualunque stati confinanti abbiano colori diversi.
(Problema dei quattro colori).
Se rappresentiamo gli stati con dei nodi e i confini fra
due stati come uno spigolo che unisce i nodi
corrispondenti, il problema diventa quello di colorare i
nodi di un grafo con quattro colori in modo che due
nodi uniti da uno spigolo abbiano colori diversi.
Problema generale


Siano dati un grafo G ed un numero n. E’
possibile colorare G con n colori in modo che
due qualunque vertici uniti da uno spigolo
abbiano colori diversi? Se si può il grafo G
viene detto n-colorabile.
Per ogni n, esiste un grafo che non è n
colorabile. Basta prendere n+1 vertici e unirli a
due a due in tutti i modi possibili. Per colorarlo
ho bisogno di n+1 colori.
2-colorabilità




Un grafo è 2-colorabile se e solo se non ha cicli con un
numero dispari di elementi.
Algoritmo: coloro il primo vertice V di rosso; coloro i
vertici raggiungibili da V con uno spigolo in blu.
Coloro i vertici raggiungibili con uno spigolo da questi
ultimi in rosso.
Etc, etc…, a fasi alterne uso il rosso e il blu finché non
ho colorato tutti i vertici.
Esempi
?
Una 2-colorazione del grafo di sinistra e un tentativo
fallito di 2-colorazione del grafo di destra
3-colorabilità
?
Un grafo 3-colorabile..
e un grafo non 3 - colorabile
n-colorabilità





Per n>2 non sono noti criteri rapidi per decidere se un
grafo è n-colorabile.
Un ovvio algoritmo consiste nel provare tutte le
possibili n-colorazioni.
Una n-colorazione può essere pensata come una
funzione dall’insieme dei nodi all’insieme degli n colori.
Se i nodi sono k le possibili colorazioni sono nk.
Il procedimento esaustivo che consiste nel provare
tutte le colorazioni è pertanto molto lento.
Grafi orientati


In un grafo orientato gli spigoli sono linee con
un verso che va da un vertice all’altro.
La funzione di incidenza associa ad ogni
spigolo orientato una coppia ordinata di vertici,
uno dei quali è il primo estremo, e l’altro il
secondo estremo.
Esempio
3
2
5
6
4
1
Un esempio di grafo orientato
Esempi di grafi orientati



I flow chart, che sono schemi di programma costituiti
da istruzioni elementari e connessioni fra le stesse
rappresentate da frecce che fanno passare da
un’istruzione all’altra.
Gli automi a stati finiti, che sono macchine per il
riconoscimento di linguaggi, costituite da stati di
accettazione e stati di rifiuto, e frecce da uno stato ad
un altro etichettate con una lettera dell’alfabeto.
Una freccia da p a q etichettata con la lettera a
significa: se sei nello stato p e leggi la lettera a passa
nello stato q e leggi la prossima lettera
Come cambia la teoria se si passa
ai grafi orientati?


Matrice di incidenza: al posto i,j della matrice,
metto il numero di spigoli orientati che vanno
dal vertice i al vertice j.
La matrice di incidenza non è necessariamente
simmetrica, in quanto possono esserci spigoli
orientati da i a j senza che vi siano spigoli
orientati da j a i.
Esempio
Un grafo orientato ..
3
2
4
1
e la sua matrice di incidenza
0

1
0

0

0 0 1

0 1 0
0 0 0

1 1 0 
Come si vede la matrice non è simmetrica
Cammini in un grafo orientato



In un grafo orientato i cammini devono
procedere nella direzione delle frecce.
Un grafo è connesso se per ogni coppia di suoi
vertici A e B esistono sia un cammino da A a B
che un cammino da B ad A.
Si noti che è possibile che esista un cammino
da A a B, ma non un cammino da B ad A.
Grafi orientati connessi


Una sconnessione di un grafo orientato è una
suddivisione dei vertici del grafo in due insiemi
disgiunti A e B tale che o non esistono frecce
da A a B o non esistono frecce da B ad A.
Si può dimostrare che un grafo orientato è
connesso se e solo se non ha sconnessioni.
Esempio
Un cammino in un grafo orientato
3
2
5
6
4
1
Nota: mentre è possibile andare da 1 a 6 con un cammino,
non vi sono cammini da 6 a 1. Quindi il grafo non è
connesso.
Esempio
Un esempio di grafo orientato connesso
3
2
6
4
1
5
Altro esempio di grafo connesso
• Consideriamo il grafo orientato la cui matrice di
incidenza è
0

0
1

1

1
0
0
0
1
0
0
0
1

1
1

0

• Ci chiediamo se il grafo sia connesso o no.
Altro esempio di grafo connesso
0

0
1

1

1
0
0
0
1
0
0
0
1

1
1

0 
Dalla prima riga vedo che posso andare da 1 a 2
Dalla seconda riga vedo che posso andare da 2 a 3.
Dalla terza vedo che posso andare da 3 a 4
Dall’ultima riga vedo che posso andare da 4 a 1
Alberi orientati
Un albero orientato è un grafo orientato in cui:
 Se al posto degli spigoli orientati sostituiamo spigoli
non orientati, otteniamo un grafo ad albero.
 Ad ogni vertice arriva al massimo una freccia.
 In un albero orientato, esiste uno ed un solo nodo a cui
non arrivano frecce. Tale nodo è detto radice.
 Esistono poi nodi da cui non partono frecce. Tali nodi
sono detti foglie.
Un esempio di albero orientato
Un albero orientato. I nodi colorati in verde sono le
foglie, mentre il nodo marrone è la radice.
Applicazioni





Gli alberi orientati hanno molte applicazioni che
non trattiamo per mancanza di tempo:
Rappresentazione di termini o di formule di un
linguaggio.
Rappresentazione di dimostrazioni logiche.
Alberi di sequenze finite.
Basi di dati.
Conclusioni



Chi si aspettava una ricetta matematica per risolvere
tutti i problemi di bioinformatica è sicuramente rimasto
deluso.
Tuttavia non era questo lo scopo del corso. La
matematica non dà una ricetta per risolvere i nostri
problemi, ma insegna ad affrontarli razionalmente.
Chi ha assimilato bene i concetti esposti durante il
corso dovrebbe essere in grado di applicare le
tecniche usate ad esempio per il gioco del Lotto a
svariate situazioni che si incontrano nella ricerca
scientifica.
Conclusioni
Per concludere, in questo corso spero di avere
mostrato un metodo, quello matematico, che può
essere utilizzato con profitto in varie aree della ricerca
scientifica, fra cui la bioinformatica.
Augurandomi che possiate metterlo a frutto, con
l’aiuto dei colleghi più esperti di me in biologia e
in informatica, vi lascio con una citazione
dantesca:
… e sei venuto in parte
dov’io più oltre non discerno
….
Non aspettar mio dir più, né mio cenno.