Post on 03-May-2015
04/11/23 E. Giovannetti -- OI09. 1
Olimpiadi di Informatica 2010Giornate preparatorie
Dipartimento di InformaticaUniversità di Torino
marzo 2010
9 – Grafi e algoritmi sui grafi: introduzione.(versione 11/04/23)
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 2
Eulero: il problema dei ponti di Königsberg(la città del filosofo Kant, in Prussia; oggi Kaliningrad, in Russia)
16
3
4
2
7
5A
B
C
D
A
B
C
D
È possibile partire da A e ritornare in A attraversando tutti i ponti esattamente una volta? Eulero dimostrò che no, dando con ciò inizio alla Teoria dei Grafi.
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 3
Definizioni preliminari
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 4
Che cos'è un grafo ? Definizioni.
Un grafo (semplice) G = (V, E) è costituito da: •un insieme V di nodi (o vertici, ingl. vertices, sing. vertex);•un insieme E di archi (o spigoli, ingl. edges), ognuno dei quali è (costituito da) una coppia di nodi distinti, detti estremi dell’arco.
Vi sono due generi di grafi:•non orientati (undirected): gli archi non hanno un verso, cioè, formalmente, sono coppie non ordinate;
•orientati (directed): gli archi hanno ciascuno un verso, cioè sono coppie ordinate; i due estremi sono detti:•nodo uscente o coda: è il primo elemento della coppia;•nodo entrante o testa: è il secondo elemento della coppia.
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 5
Esempio: grafo non orientato
V = {A, B, C, D, E, F}
E = {{A,B}, {A,D}, {B,C}, {C,D}, {C,E}, {D,E}}A
BC
D E
F
(B, C) e (C, B) denotano lo stesso arco, che in realtà è l'insieme {B, C} {C, B}
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 6
Esempio: multigrafo.
A
BC
D E
F
non possono esistere archi distinti con gli stessi estremi
NO !
un “grafo” in cui sono permessi archi distinti con gli stessi estremi è un multigrafo
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 7
Esempio: grafo orientato
A
BC
F
V = {A, B, C, D, E, F}
E ={(A,B), (A,D), (B,C), (C,B), (D,C), (E,C), (D,E)}
D E
(B,C) e (C,B) denotano due archi fra loro distinti
coda
coda
testatesta A è la coda dell’arco
(A,D)D è la testa dell’arco (A,D)D è la coda dell’arco (D,E)ecc.
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 8
Esempio: multi-grafo orientato
A
BC
D E
F
ma non possono esistere archi distinti con la stessa coda e la stessa testa
NO !
un “grafo orientato” in cui sono permessi archi distinti con la stessa coda e la stessa testa è un multigrafo orientato.
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 9
Grafi non orientati: terminologia.
•l'arco {A, B} è incidente sui nodi A e B;•i nodi A e B sono adiacenti:A è adiacente a B, B è adiacente ad A;
•i nodi adiacenti a un nodo A si chiamano anche i vicini di A;
•grado di un nodo = numero degli archi incidenti sul nodo; esempio: il nodo B ha grado (B) = 3;
A B
B
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 10
Grafi orientati: terminologia.
•l'arco {A, B} è:•incidente sui nodi A e B, •uscente da A, entrante in B;
•il nodo B è adiacente ad A, ma A non è adiacente a B.•i nodi adiacenti a un nodo A si chiamano anche i vicini di A;•grado di un nodo = numero degli archi incidenti sul nodo;
•grado uscente = numero degli archi uscenti dal nodo;•grado entrante = numero degli archi entranti nel nodo;
esempio: il nodo B ha:
•grado uscente out(B) = 1, grado entrante in(B) = 2,
•grado totale (B) = out(B) + in(B) = 3,
A B
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 11
Grafi: terminologia (sommario)
•sottografo di un grafo G = grafo che si ottiene da G non considerando degli archi, e/o non considerando dei nodi né gli archi incidenti su di essi.
A
BC
F
D E
A
BC
F
D
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 12
Grafi: terminologia (sommario)
•sottografo di un grafo G = grafo che si ottiene da G non considerando degli archi, e/o non considerando dei nodi né gli archi incidenti su di essi.
AC
D
AC
D
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 13
Grafi: terminologia (sommario)
•sottografo indotto da un insieme di nodi:dato un grafo G, il sottografo indotto da un sottoinsieme V' di nodi di G è il sottografo di G costituito dai nodi di V' e dagli archi di G che connettono tali nodi. Esempio: nel grafo sottostante, il sottografo indotto dall'insieme di nodi {A, C, D} è:
A
BC
F
D E
A
BC
F
D
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 14
Grafi: terminologia (sommario)
•sottografo indotto da un insieme di nodi:dato un grafo G, il sottografo indotto da un sottoinsieme V' di nodi di G è il sottografo di G costituito dai nodi di V' e dagli archi di G che connettono tali nodi. Esempio: nel grafo sottostante, il sottografo indotto dall'insieme di nodi {A, C, D} è:
AC
D
AC
D
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 15
Sia G = (V, E) un grafo. Un cammino nel grafo è una sequenza di nodi <w1, w2, ..., wn> tale che (wi, wi+1) E per 1 i n–1.
Definizione con esempio
A
BC
F
D E
A
BC
F
D E
Es. A, B, C, E è un cammino nel grafo
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 16
A
BC
F
D E
Es. la lunghezza del cammino A, B, C, E è 3.
Il cammino <w1, w2, ..., wn> contiene i vertici w1, w2,…, wn e gli archi (w1,w2) (w2,w3) ...(wn-
1,wn).La lunghezza del cammino è il numero totale di archi che collegano i vertici della sequenza (uno in meno del numero di vertici).
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 17
Definizione con esempio
Se esiste un cammino p tra i vertici v e w, si dice che w è raggiungibile da v tramite p
Es.: A è raggiungibile da D e viceversa
wvp
A
BC
F
D E
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 18
A
BC
F
D E
Es.: D è raggiungibile da A ma non viceversa
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 19
Se G è un grafo non orientato, definiamo G connesso se esiste un cammino da ogni vertice ad ogni altro vertice. Ad es. questo grafo non
orientato è connesso.
A
BC
F
D E
A
BC
F
D E
Definizione con esempio
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 20
A
BC
F
D E
A
BC
F
D E
Questo grafo non orientato NON è connesso.
Esempio
G
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 21
Se G è un grafo orientato, definiamo G fortemente connesso se esiste un cammino da ogni vertice ad ogni altro vertice.
Definizione con esempio
Ad es. questo grafo orientato è fortemente connesso.
A
BC
F
D E
A
BC
F
D E
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 22
A
BC
F
D E
Esempio
A
BC
F
D E
Ad es. questo grafo orientato NON è fortemente connesso. Infatti, non esiste cammino da C a B, né da E ad A, ecc. Tuttavia è debolmente connesso.
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 23
Un ciclo in un grafo è un cammino w1, w2, …, wn di lunghezza almeno 1, tale che w1 = wn.
Definizione
il cammino A, B, C, E, D, A è un ciclo;
A
BC
F
D E
A
BC
F
D E
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 24
grafo aciclico = grafo senza cicli
Definizione con esempio
Ad es. questo grafo orientato non è aciclico, …
A
BC
F
D E
A
BC
F
D E
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 25
Un grafo orientato aciclico è spesso chiamato DAG (Directed Acyclic Graph).
A
BC
F
D E
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 26
A
BC
F
D E– 2.3
34
7.51.24.5
Definizione con esempio.
grafo pesato: ad ogni arco è associato un peso, costituito da un numero reale.
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 27
RappresentazioneLa rappresentazione più comoda è tramite•liste di adiacenza: per ogni nodo si tiene la lista dei nodi ad esso adiacenti.Se gli N nodi di un grafo sono rappresentati dagli interi da 0 a N-1, il grafo può essere realizzato come un vettore di vettori, ad esempio:
0
12
5
3 4
20
1
2
3
4
5
1
3
2
1
0
1 3
grado
2
0 4
2 4
5
5
Rappresentazione
•In molti esercizi la struttura-grafo è data implicitamente dalla struttura-dati caratteristica del problema e non deve essere costruita esplicitamente.
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 28
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.41 29
Visita di grafi e algoritmi sui grafi (sommario)
•visita in ampiezza (iterativa con uso di coda);su grafi pesati:•cammini minimi da un nodo: algoritmo di Dijkstra (uso di coda con priorità);
•minimo albero di copertura: algoritmo di Prim (uso di coda con priorità);
•minimo albero di copertura: algoritmo di Kruskal (uso di struttura union-find);
•visita in profondità (iterativa con uso di pila, o ricorsiva);•ordinamento topologico;•componenti fortemente connesse.
Albero di visita
•Durante la visita di un grafo si costruisce implicitamente un albero, detto albero di visita. Se richiesto dall’applicazione, tale costruzione può essere effettuata esplicitamente (nei problemi olimpici di solito non è necessaria).
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 30
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.41 31
Visita in profondità ricorsiva.
Come negli alberi, la visita in profondità si può realizzare molto semplicemente in modo ricorsivo.Occorre però marcare i nodi che vengono visitati.
visitaInProfondità (il grafo G a partire dal nodo s) { marca tutti i nodi di G come non visitati; T = albero vuoto; visitaRic(s); } // la procedura visita il sottografo di G connesso con s.
visitaRic (dal nodo u) { inizia_visita(u); marca u come visitato; for each (nodo v adiacente a u) if (v è non visitato) { aggiungi v come figlio di u nell’albero T; visitaRic(v); } termina_visita(u); }
Visita di tutto il grafo
Se il grafo non è connesso, la procedura precedente non visita i sottografi non connessi con il nodo di partenza. La visita di tutto il grafo si ottiene semplicemente iterando la visita ricorsiva sui nodi di partenza non ancora visitati:
visitaTutti(grafo G) { marca tutti i nodi di G come non visitati; T = foresta vuota; for each (nodo u del grafo G) if (u è non visitato) visit(G, u);}
11/04/23 19:56 E. Giovannetti - AlgELab-09-10 - Lez.40 32