Lezioni di Ricerca Operativa
Corso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
Lezione n° 16: 5-6 Maggio 2009
- Teoria dei grafi: definizioni di base
- Problema dell’albero ricoprente a costo minimo
Anno accademico 2008/2009
Prof. Cerulli – Dott.ssa Gentili
Teoria dei Grafi
Concetti fondamentali
I grafi sono un mezzo per rappresentare relazioni binarie
Ad esempio:
 due città connesse da una strada
 due calcolatori connessi in una rete telematica
 due persone legate da una relazione di parentela
(come, padre-figlio)
 due persone che condividono una stanza
 il collegamento tra due componenti elettronici
 un’operazione che deve essere eseguita da una
certa macchina
 ...
2
I grafi possono essere usati come strumento per
modellare in maniera schematica un vastissimo numero
di problemi decisionali.
Ad esempio:
 determinare il percorso più breve che connette
due città
 determinare come connettere nella maniera più
economica (più efficiente) un insieme di
calcolatori in una rete telematica
 assegnare un insieme di operazioni ad un insieme
di macchine
 determinare il percorso più conveniente da far
percorrere ad una flotta di veicoli commerciali per
effettuare delle consegne e quindi rientrare al
deposito
 ...
3
Definizioni fondamentali
Grafo non orientato
Un grafo non orientato G=(V,E) è dato da una coppia
di insiemi finiti:

V={v1,...,vn} l’insieme degli n Nodi di G

E={e1,..,em}VxV l’insieme degli m Archi non
orientati di G
Ogni arco non orientato di G corrisponde ad una
coppia non ordinata di nodi di G ek=(vi,vj).
La presenza di un arco tra una coppia di nodi indica
una relazione tra i nodi stessi.
4
Un esempio: G=(V,E)
e2
v1
v2
e6
e1
v5
e3
e5
v3
e7
e4
v4
V  v1, v 2 , v 3 , v 4 , v 5 
E  e1, e 2 , e 3 , e 4 , e 5 , e 6 , e7 
e 1   v 1, v 5 
e 2   v 1, v 2 

5
Definizioni di base:

un arco (v,v) è detto loop

due nodi u,vV sono detti adiacenti  (u,v)E

due archi e,fE sono detti adiacenti  e=(v,w) ed
f=(v,u)

un arco f=(u,v)E si dice incidente su u e su v

l’insieme di nodi N(v)={zV: z adiacente a v} è detto
intorno di v in G

l’insieme di archi d(v)={eE: e incide su v} è detto
stella di v in G

d(v) è detto grado del nodo v
6
Grafi e Sottografi

H=(W,F) è detto sottografo di G=(V,E)  WV e
FE

H=(W,F) è detto sottografo indotto da W in G=(V,E)
 WV e (u,v)F implica che u,vW e (u,v)E
7
Esempio
v1
e1
v5
e2
e3
v2
e6
e5
v3
e7
e4
v4
G=(V,E)
v1
e1
e2
v2
v3
v5
sottografo di G
8
Esempio
e1
e3
e4
v5
v1
e1
v2
e2
v1
e2
e3
e6
e5
v3
e7
v4 G=(V,E)
v2
e6
v3
W  v1, v2 , v3 , v5 
v5
sottografo indotto di G
9
Grafi bipartiti e grafi completi
G è detto grafo bipartito se esiste una partizione di
V=V1V2 tale che:

V1V2=

"e=(u,v)E se uV1 allora vV2 oppure se uV2
allora vV1
Esempio
grafo bipartito
grafo non bipartito
10

G è detto completo  contiene tutti i possibili archi,
ovvero  d(v)=n-1 "vV

il massimo numero di archi di un grafo completo è
dato da
 n  n(n  1)
  
2
 2
Esempio
grafo completo
11
Grafi orientati

G=(V,E) è detto orientato se, dato V={v1,...,vn},
l’insieme degli archi E={e1,..,em} è formato da coppie
ordinate di nodi.
Per un grafo orientato si ha che ei=(vk,vh)ej=(vh,vk)
ei,ejE
vh
Coda
ei
vk
Testa
L’arco ei si dice uscente da vh ed entrante in vk
12
Esempio
e3
v1
e1
v4
e2
v2
e4
e6
e5
v3
grafo orientato
Fs(v)={uV: (v,u) E} è detto stella uscente di v

Bs(v)={uV: (u,v) E} è detto stella entrante di v

S(v)= Fs(v)Bs(v) è detto stella di v

le definizioni di sottografo e sottografo indotto di un

grafo orientato sono analoghe a quelle date per i grafi
non orientati
13
Grafi connessi e componenti connesse

Dato G=(V,E) un nodo vV si dice connesso ad un
nodo zV se esiste un cammino (orientato o non) tra v
e z in G

vV è connesso a v (riflessività)

vV è connesso a zV  zV è connesso a vV
(simmetria)

se vV è connesso a zV e zV è connesso a uV
 vV è connesso a uV (transitività)
14

L’insieme V può essere partizionato in sottoinsiemi
Ci={vV:v è connesso a z, "zCi}

Il sottografo indotto da Ci in G è detto componente
connessa di G

Se G possiede una sola componente connessa si dice
connesso ("v,zV v è connesso a z)
Esempio
componenti
connesse
grafo connesso
15
Cammini e circuiti euleriani
 Un cammino euleriano è un percorso che passa per
ogni arco una sola volta
 Un circuito euleriano è un cammino euleriano chiuso
Esempio
8
3
6
1
7
circuito euleriano
2
5
4
16
Alberi
 Un grafo è aciclico se non contiene cicli (orientati o
non)

Un albero è un grafo connesso ed aciclico

Ogni grafo aciclico è in generale l’unione di alberi e
viene detto foresta
Esempio
grafo aciclico
(foresta)
grafo non aciclico
albero
17
Dato
G=(V,E),
le
seguenti
affermazioni
sono
equivalenti:

G è un albero

ogni coppia di nodi di G è connessa da un unico
cammino

G è aciclico eE=V-1

G è aciclico e connettendo due nodi non adiacenti
con un arco si ottiene un grafo con un unico ciclo

G è connesso eE=V-1
18

Dato un albero T=(V,E), si dice foglia vV tale
ched(v)=1

Se V2 allora esistono almeno due foglie
foglie di un albero
19

Dato G=(V,E), si dice albero ricoprente (spanning
tree) di G un albero T=(W,F) con W=V ed FE (è un
sottografo di G)
un albero ricoprente
20
Il Problema del Minimo Albero Ricoprente
(Minimum Spanning Tree Problem)
 Si considera un grafo G=(V,E)
 Ad ogni arco ei, i=1,...,n di G è associato un costo ci,
i=1,...,m
Il problema: determinare l’albero ricoprente di G con il
minimo costo associato.
14
4 10
7
Esempio
8
11
9
17
3
2 1 16
12
6
13
5 15
21