Grafi: Introduzione e Rappresentazione PDF

Indice 1. Definizione 2. Terminologia Grafi...

Indice 1. Definizione 2. Terminologia Grafi: introduzione, rappresentazione 3. Rappresentazione Corso di Algoritmi e strutture dati Corso di Laurea in Informatica Docenti: Ugo de’Liguoro, András Horváth Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 1/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 2/ 39 Sommario 1. Definizione Obiettivo: I definizione astratta: un grafo G = (V , E) consiste in I introdurre la definizione I un insieme V di vertici (nodi) I un insieme E di coppie di vertici (archi, spigoli): ogni arco connette due vertici I imparare la terminologia I V rappresenta un insieme di oggetti I confrontare diversi modi di rappresentare un grafo I E rappresenta relazione tra questi oggetti I due tipi di grafi: I orientati I non orientati (non diretti) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 3/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 39  1. Esempi 1. Storia I Esempio I: Ponti di Königsburg - 1736: V = {persone che vivono in Italia}, C E = {coppie di persone che si sono strette la mano} D A I Esempio II: V = {persone che vivono in Italia}, B E = {(x, y ) tale che x ha inviato una mail a y } È possibile partire da A e ritornare in A attraversando tutti i ponti esattamente una volta? C A D B Euler dimostrò che la passeggiata non era possibile. (Il grafo è un multigrafo perché ci sono due archi fra A e C e fra A e B.) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 5/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 6/ 39 2. Terminologia 2. Terminologia I relazione simmetrica (coppie non ordinate) → grafo non orientato I relazione non simmetrica (coppie ordinate) → grafo orientato (esempio II) (esempio I) B B C C A A F F D E D E I V = {A, B, C, D, E, F } I V = {A, B, C, D, E, F } I E = {(A, B), (A, D), (B, C), (D, C), (E, C), (D, E), (D, A)} I E = {(A, B), (A, D), (B, C), (C, D), (C, E), (D, E)} I (A, D) e (D, A) denotano due archi diversi I (A, D) e (D, A) denotano lo stesso arco Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 7/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 39  2. Terminologia 2. Terminologia I in un grafo orientato, I un vertice x si dice adiacente a y se e solo se (y , x) ∈ E un arco (x, y ) è incidente da x in y B C A B C A F D E F I B è adiacente ad A D E I C è adiacente a B, a D e ad E I A è adiacente a D e viceversa I (A, B) è incidente da A a B I B non è adiacente a D I (A, D) è incidente da A in D I F non è adiacente ad alcun vertice I (D, A) è incidente da D in A Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 9/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 39 2. Terminologia 2. Grado I in un grafo non orientato, la relazione di adiecenza è simmetrica I in un grafo non orientato: I il grado di un vertice è il numero di archi che da esso si dipartono B I in un grafo orientato: C I il grado entrante (uscente) di un vertice è il numero di archi incidenti in (da) esso A I il grado di un vertice è la somma del suo grado entrante e del suo grado uscente F D E I B è adiacente ad A e viceversa I A è adiacente a D e viceversa I F non è adiacente ad alcun vertice Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 11/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 39  2. Peso 2. Sottografo I associamo ad ogni arco un peso I sia G = (V , E) un grafo I grafo pesato: (G, W ) dove I un sottografo di G è un grafo H = (V ∗ , E ∗ ) tale che V ∗ ⊆ V e E ∗ ⊆ E I G è un grafo I poichè H è un grafo, deve valere che E ∗ ⊆ V ∗ × V ∗ I W è la funzione peso: W : E → R dove R è l’insieme dei numeri reali B 3 B 4 C C A A 4.5 F F 1.2 7.5 D E E -2.3 D I W ((A, B)) = 3, W ((D, E)) = −2.3, W ((C, F )) = ∞ I V ∗ = {A, C, D, E}, E ∗ = {(A, D), (D, E), (E, C)} Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 14/ 39 2. Cammino in grafo non orientato 2. Cammino in grafo orientato I sia G = (V , E) un grafo I sia G = (V , E) un grafo orientato I un cammino nel grafo G è una sequenza di vertici v1 , v2 ,..., vn tale che I un cammino nel grafo G è una sequenza di vertici v1 , v2 ,..., vn tale che (vi , vi+1 ) ∈ E per 1 ≤ i < n (vi , vi+1 ) ∈ E per 1 ≤ i < n I la lunghezza del cammino è il numero totale di passaggi ad un vertice al altro B (uno in meno del numero di vertici) C A B C 3 A 4 3 4 2 F 1 2 5 F 5 D E D E 1 6 I D, E, C, D, A, D è un cammino nel G I A, D, C, B, A, D, E è un cammino nel G di lunghezza 6 I D, E, C, B, A, D non è un cammino nel G Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 15/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 39  2. Cammino in grafo non orientato 2. Raggiungibilità I un cammino è un cammino semplice se tutti suoi vertici sono distinti I se esiste un cammino p tra i vertici x e y , si dice che y è raggiungibile da x e (compaiono una sola volta nella sequenza) eccetto al più il primo e l’ultimo si scrive x → y che possono essere lo stesso B C B A C A 4 3 F D E 1 2 5 F I A è raggiungibile da C e viceversa D E I per definizione: A è raggiungibile da A 6 I in un grafo non orientato la relazione di raggiungibilità è simmetrica I non confondere raggiungibilità con adiacenza I A, D, C, B, A, D, E è un cammino non semplice I (Cormen et alii usa invece di →) I A, D, C, B, A è un cammino semplice Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 17/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 18/ 39 2. Raggiungibilità 2. Grafo connesso I se esiste un cammino p tra i vertici x e y , si dice che y è raggiungibile da x e I se G è un grafo non orientato, definiamo G connesso se esiste un cammino si scrive x → y da ogni vertice ad ogni altro vertice B B C C A A F F D E D E I C è raggiungibile da A ma A non è raggiungibile da C I questo grafo è connesso I in un grafo orientato la relazione di raggiungibilità non è simmetrica Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 19/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 39  2. Grafo connesso 2. Grafo fortemente connesso I se G è un grafo non orientato, definiamo G connesso se esiste un cammino I se G è un grafo orientato, definiamo G da ogni vertice ad ogni altro vertice fortemente connesso se esiste un cammino da ogni vertice ad ogni altro vertice B B C C A A F F D E D E I questo grafo non è connesso I questo grafo è fortemente connesso Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 21/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 22/ 39 2. Grafo fortemente connesso 2. Grafo debolmente connesso I se G è un grafo orientato, definiamo G I se G è un grafo orientato, definiamo G debolmento connesso se il grafo fortemente connesso se esiste un cammino da ogni vertice ad ogni altro vertice ottenuto da G dimenticando la direzione degli archi è connesso B B C C A A F F D E D E I questo grafo non è fortemente connesso I questo grafo è debolmente connesso I non esiste cammino da F ad A Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 23/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 24/ 39  2. Ciclo 2. Grafo aciclico I in un grafo orientato un ciclo è un cammino x1 ,..., xn con n > 2 e x1 = xn I un grafo senca cicli è detto aciclico I in un grafo non orientato un ciclo è un cammino x1 ,..., xn con n > 2 e x1 = xn B che non attraversa lo stesso arco due volte di seguito C A B C A F F D E D E I questo grafo non è aciclico perché esiste il ciclo A, D, A I un grafo orientato aciclico è spesso chiamato directed acyclic graph (DAG) I il cammino A, B, C, D, A è un ciclo Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 25/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 26/ 39 2. Grafo completo 2. Grafo completo I un grafo completo è un grafo che ha un arco tra ogni coppia di vertici I un grafo completo è un grafo che ha un arco tra ogni coppia di vertici B B C C A A F D E D E I questo grafo non è completo I questo grafo è completo   n n(n − 1) I numero di archi in un grafo completo con n vertici: = 2 2 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 27/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 28/ 39  2. Albero libero 2. Albero radicato I un albero libero è un grafo non orientato, connesso, aciclico I un albero radicato è un grafo non orientato, connesso, aciclico con un vertice designato ad essere radice B C B A C A F F D E D E radice I libero si riferisce al fatto che non è definito quale vertice è la radice Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 29/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 30/ 39 2. Foresta 3. Matrice di adiacenza, grafo non orientato I una foresta è un grafo non orientato, aciclico ma non necessariamente B connesso C A B C A F F D E G D E A 0 1 0 1 0 0 B 1 0 1 0 0 0  C 0 1 0 1 1 0 I questo grafo è una foresta che contiene due alberi 1 se (x, y ) ∈ E M(x, y ) = D 1 0 1 0 1 0 I un albero è una foresta 0 altrimenti E 0 0 1 1 0 0 F 0 0 0 0 0 0 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 32/ 39  3. Lista di adiacenza, grafo non orientato 3. Matrice di adiacenza, grafo orientato L(x) è la lista di adiacenza del vertice x e contiene ogni y tale che (x, y ) ∈ E B A B D C B A C A B A C F C B D E F D A C E D E D E E D C A 0 1 0 1 0 0 B 0 0 1 0 0 0 F  C 0 0 0 0 0 0 1 se (x, y ) ∈ E M(x, y ) = D 1 0 1 0 1 0 0 altrimenti E 0 0 1 0 0 0 F 0 0 0 0 0 0 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 33/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 34/ 39 3. Lista di adiacenza, grafo orientato 3. Matrice di adiacenza, grafo pesato L(x) è la lista di adiacenza del vertice x e contiene ogni y tale che (x, y ) ∈ E 3 4 B A B D C B A C 4.5 A B C 7.5 F 1.2 C D E -2.3 F D A C E E E A 0 3 0 1.2 0 0 D C B 3 0 4 0 0 0 F M(x, y ) = W (x, y ) C 0 4 0 4.5 7.5 0 D 1.2 0 4.5 0 −2.3 0 E 0 0 7.5 −2.3 0 0 F 0 0 0 0 0 0 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 35/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 36/ 39  3. Lista di adiacenza, grafo pesato 3. Possibili operazioni, grafo non orientato L(x) è la lista di adiacenza del vertice x e contiene ogni coppia (y , w) tale che in caso di lista di liste di adiecenza: (x, y ) ∈ E e w = W ((x, y )) operazione tempo di esecuzione A B 1.2 D 2.3 grado(x) O(δ(x)) 1.2 B A 5 C B C 5 archiIncidenti(x) O(δ(x)) sonoAdiacenti(x, y ) O(min(δ(x), δ(y ))) C 2.3 -2 aggiungiVertice(x) O(1) 4 F D A 4 C -2 E 1.8 4 aggiungiArco(x, y ) O(1) D E E C 4 rimuoviVertice(x) O(m) 1.8 rimuoviArco(x, y ) O(δ(x) + δ(y )) F dove δ(x) è il numero degli adiacenti di x, dove n è il numero di vertici e m è il numero di archi Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 37/ 39 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 38/ 39 3. Possibili operazioni, grafo non orientato in caso di matrice di adiecenza: operazione tempo di esecuzione grado(x) O(n) archiIncidenti(x) O(n) sonoAdiacenti(x, y ) O(1) aggiungiVertice(x) O(n2 ) aggiungiArco(x, y ) O(1) rimuoviVertice(x) O(n2 ) rimuoviArco(x, y ) O(1) dove n è il numero di vertici Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 39/ 39