Lezione n° 16: 5-6 Maggio 2009 - Teoria dei grafi: definizioni di base - Problema dellalbero...
-
Upload
settimio-rocca -
Category
Documents
-
view
215 -
download
1
Transcript of Lezione n° 16: 5-6 Maggio 2009 - Teoria dei grafi: definizioni di base - Problema dellalbero...
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
Lezioni di Ricerca OperativaCorso di Laurea in Informatica ed Informatica Applicata
Università di Salerno
2
Teoria dei GrafiConcetti 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 ...
3
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
...
4
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.
5
Un esempio: G=(V,E)
v1
v5
v3
v2
v4
e1
e2
e3
e4
e5
e6
e7
V v v v v v 1 2 3 4 5, , , ,
E e e e e e e e 1 2 3 4 5 6 7, , , , , ,
e v v e v v1 1 5 2 1 2 , ,
6
Definizioni di base: un arco (v,v) è detto loop due nodi u,vV sono detti adiacenti (u,v)E due archi e,fE 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)={zV: z adiacente a v} è detto
intorno di v in G l’insieme di archi (v)={eE: e incide su v} è detto
stella di v in G (v) è detto grado del nodo v
7
Grafi e Sottografi
H=(W,F) è detto sottografo di G=(V,E) WV e
FE
H=(W,F) è detto sottografo indotto da W in G=(V,E)
WV e (u,v)F implica che u,vW e (u,v)E
8
Esempiov1
v5
v3
v2
v4
e1
e2
e3
e4
e5
e6
e7
G=(V,E)
v1
v5
v3
v2
e1
e2
sottografo di G
9
Esempio
v1
v5
v3
v2
e1
e2
e3
e4
e5
e6
e7
G=(V,E)
v1
v5
3v
v2
e1
e2
e3e6
sottografo indotto di G
5321 ,,, vvvvW
4v
10
Grafi bipartiti e grafi completi
G è detto grafo bipartito se esiste una partizione di
V=V1V2 tale che:
V1V2=
e=(u,v)E se uV1 allora vV2 oppure se uV2
allora vV1
Esempio
grafo bipartito grafo non bipartito
11
G è detto completo contiene tutti i possibili archi,
ovvero (v)=n-1 vV
il massimo numero di archi di un grafo completo è
dato da2
)1(
2
nnn
Esempio
grafo completo
12
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,ejE
vh vkeiCoda Testa
L’arco ei si dice uscente da vh ed entrante in vk
13
Esempio v1
v4v3
v2
e1 e2
e3
e6e4
e5
grafo orientato
Fs(v)={uV: (v,u) E} è detto stella uscente di vBs(v)={uV: (u,v) E} è detto stella entrante di vS(v)= Fs(v)Bs(v) è detto stella di vle definizioni di sottografo e sottografo indotto di un
grafo orientato sono analoghe a quelle date per i grafi
non orientati
14
Grafi connessi e componenti connesse
Dato G=(V,E) un nodo vV si dice connesso ad un
nodo zV se esiste un cammino (orientato o non) tra v
e z in G vV è connesso a v (riflessività) vV è connesso a zV zV è connesso a vV
(simmetria) se vV è connesso a zV e zV è connesso a uV
vV è connesso a uV (transitività)
15
L’insieme V può essere partizionato in sottoinsiemi
Ci={vV:v è connesso a z, zCi}
Il sottografo indotto da Ci in G è detto componente
connessa di G Se G possiede una sola componente connessa si dice
connesso (v,zV v è connesso a z)Esempio
componenticonnesse
grafo connesso
16
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
circuito euleriano12
3
4
5
67
8
17
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
18
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 eE=V-1 G è aciclico e connettendo due nodi non adiacenti
con un arco si ottiene un grafo con un unico ciclo G è connesso eE=V-1
19
Dato un albero T=(V,E), si dice foglia vV tale
che(v)=1 Se V2 allora esistono almeno due foglie
foglie di un albero
20
Dato G=(V,E), si dice albero ricoprente (spanning
tree) di G un albero T=(W,F) con W=V ed FE (è un
sottografo di G)
un albero ricoprente
21
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,...,mIl problema: determinare l’albero ricoprente di G con il
minimo costo associato.
Esempio7
144 10
9178
132
11 12
6
13
16
155