4/25/2015E. Giovannetti -- OI09.1 Olimpiadi di Informatica 2010 Giornate preparatorie Dipartimento...

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.


Definizioni preliminari


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.


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}


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


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.


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.


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


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


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



•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



•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



•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


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


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).



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


A

BC

F

D E

Es.: D è raggiungibile da A ma non viceversa


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



A

BC

F

D E

A

BC

F

D E

Questo grafo non orientato NON è connesso.

Esempio

G


Se G è un grafo orientato, definiamo G fortemente connesso se esiste un cammino da ogni vertice ad ogni altro vertice.


Ad es. questo grafo orientato è fortemente connesso.

A

BC

F

D E

A

BC

F

D E


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.


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


grafo aciclico = grafo senza cicli


Ad es. questo grafo orientato non è aciclico, …

A

BC

F

D E

A

BC

F

D E


Un grafo orientato aciclico è spesso chiamato DAG (Directed Acyclic Graph).

A

BC

F

D E


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.


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.



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).



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);}


4/25/2015E. Giovannetti -- OI09.1 Olimpiadi di Informatica 2010 Giornate preparatorie Dipartimento...

Documents

Transcript of 4/25/2015E. Giovannetti -- OI09.1 Olimpiadi di Informatica 2010 Giornate preparatorie Dipartimento...