Introduzione alla Teoria dei Graﬁlaura/assets/files/pswb/03-IntroGrafi.pdf · Introduzione alla...

Introduzione allaTeoria dei Grafi

Progetto di Sistemi Web-BasedProf. Luigi Laura, Univ. Tor Vergata, a.a. 2010/2011

martedì 15 marzo 2011

Problema delle stre-e di mano

(in versione Facebook):Considerate solo le amicizie all’interno del vostro gruppo di amici. Ovvero, se un vostro “amico” è amico di qualcuno che non è vostro amico, non la conEamo. AFFERMAZIONE: In questo gruppo ristre.o, esistono (almeno) due persone dis6nte che hanno lo stesso numero di amici

2


Problema delle stre-e di mano

L’affermazione è VERA o FALSA?Se è VERA, riusciamo a dimostrarla?!?

Se è FALSA, riusciamo a trovare un controesempio?!?

3


L’affermazione è VERA!

Cenni della dimostrazione:• In un gruppo di N persone, ognuno ha da 0 a N-‐1 amici• A-enzione!: nel gruppo, o c’è quello “amico di tuX” (N-‐1 collegamenE) oppure c’è quello “amico di nessuno” (0 collegamenE)• Supponiamo ci sia l’amico di tuX: abbiamo N persone da classificare in gruppeX con 1,2..,N-‐1 collegamenE: almeno 2 devono finire nello stesso gruppe-o!• Ragionamento analogo se c’è l’amico di nessuno: abbiamo N persone da classificare in gruppeX con 0,1..,N-‐2 collegamenE: almeno 2 devono finire nello stesso gruppe-o!

4


Teoria dei Grafi

• E’ uno strumento indispensabile per l’analisi di reE, e quindi di social network...• ...è fondamentale anche per capire come funziona un moderno motore di ricerca...• ... e, sopra-u-o, è facile! (Almeno la parte che tra-eremo nel corso!)• PS anche i navigatori funzionano con algoritmi basaE sulla Teoria dei Grafi

5


Teoria dei Grafi -‐ Definizioni

Un grafo G=(V,E) consiste in: -‐ un insieme V di ver6ci (o nodi) -‐ un insieme E di coppie di verEci, deX archi o spigoli: ogni arco conne-e due verEci

Esempio 1: V={Insieme delle persone che vivono in Italia}; E={Coppie di persone che si sono stre-e la mano}Esempio 2: V={Insieme delle persone che vivono in Italia}; E={(x,y): Se la persona x ha mandato una mail alla persona y}

6


Teoria dei Grafi -‐ Terminologia

• Esempio 1: relazione simmetrica: Grafo NON orientato• Esempio 2: relazione NON simmetrica: Grafo orientato• n=numero di verEci• m=numero di archi• I verEci L ed H sono ADIACENTI• L’arco (L,H) è INCIDENTE a L• Grado di un nodo è il numero di archi incidenE

7


Esempi

• Grafo NON orientato:Facebook -‐ i nodi sono le persone e gli archi sono le amicizie• Grafo orientato:il Grafo del Web (Webgraph) -‐ i nodi sono le pagine Web e gli archi sono i link (direX) tra le pagine [torneremo a parlare del Webgraph quando parleremo di come funzionano i motori di ricerca...]

8

1 2

3 4 5

6 7

(a)

1

3 4 5

6 7

1 2

3 4

6 7

(b) (c)

1 2

3 4 5

6 7

1 2

3 4 5

6 7

(d) (e)

Figure 1: (a) A strongly connected graph G = (V,E). (b) After removing vertex 2, Gis still strongly connected, so vertex 2 is not a strong articulation point, while (c) afterremoving vertex 5, G is no longer strongly connected, so vertex 5 is a strong articulationpoint. (d) After removing edge (5, 2), G is still strongly connected, so edge (5, 2) is not astrong bridge, while (e) after removing edge (4, 5), G is no longer strongly connected, soedge (4, 5) is a strong bridge. In summary, the strong articulation points in G are vertices3 and 5, and the strong bridges in G are edges (2, 3) and (4, 5).

3


Il problema delle stre-e di mano...

• In realtà, abbiamo dimostrato il seguente teorema della Teoria dei Grafi:

In un Grafo NON orientato, esistono sempre (almeno) due nodi che hanno lo stesso grado.

• Riusciamo a dimostrare il seguente: in un grafo, la somma di tuX i gradi è pari a 2m?

9


Le origini della Teoria dei Grafi:I ponE di Koenigsberg

(materiale preso da wikipedia.it)


Il problema dei ponE

• Nel corso dei secoli è stata più volte proposta la quesEone se sia possibile con una passeggiata seguire un percorso che a-raversi ogni ponte una e una volta soltanto e tornare al punto di partenza.


I ponE di Koenigsberg


Il Teorema di Eulero

• Nel 1736 Leonhard Euler dimostra che la passeggiata ipoEzzata non era possibile:

Un qualsiasi grafo è percorribile se e solo se ha tu5 i nodi di grado pari, o due di essi sono di grado dispari; per percorrere un grafo "possibile" con due nodi di grado dispari, è necessario par:re da uno di essi, e si terminerà sull’altro nodo dispari.


Variazioni Si precisa quindi che sulla riva se-entrionale della ci-à sorge lo Schloß, il castello per chi non conoscesse ancora la parola tedesca, del principe Blu e che sulla riva meridionale sorge quello del principe Rosso; i due principi sono fratelli, ma è un caso dei fratelli-‐coltelli; sull'isola orientale vi è la Kirche, la chiesa, sede del Vescovo; infine nell'isola centrale si trova una Gasthaus, un'osteria. Come si vedrà poi le relazioni fra i notabili della ci-à, tra i quali va realisEcamente considerato anche l'oste, non sono sempre facili.Seguendo con a-enzione l'ordine cronologico dei faX, bisogna ricordare che molE abitanE della ci-à avevano l'abitudine la sera di tra-enersi alquanto alla Gasthaus e quindi di tentare l'impresa chiamata passare i ponE; alcuni poi tornavano a festeggiare la loro riuscita con ulteriori libagioni, ma senza riuscire a spiegare in modo soddisfacente come a loro dire erano riusciE e senza saper ripetere la passeggiata alla luce del giorno.


Variazioni


L'o.avo ponte del principe Blu Il principe Blu, dopo aver analizzato il sistema dei ponE ci-adini con l'aiuto della teoria dei grafi, si convince dell'impossibilità di passare i ponE. Decide allora di costruire di nascosto un o-avo ponte che gli perme-a la sera di passare i ponE partendo dal suo Schloß e finendo alla Gasthaus dove potersi vantare della sua riuscita; e inoltre fa in modo che il principe Rosso non riesca a fare altre-anto a parEre dal suo Schloß.


Il nono ponte del principe Rosso Il principe Rosso, imbufalito per la mossa del fratello, capisce che può reagire solo dopo aver studiato la teoria dei grafi; dopo un a-ento studio anche lui decide di costruire di nascosto un altro ponte che consenta a lui di traversare i ponE in modo di raggiungere dal suo Schloß la Gasthaus e qui prendere per i fondelli il fratello al quale diventa impossibile passare i ponE alla sua maniera.


Il decimo ponte del Vescovo

Il Vescovo ha dovuto assistere alla dispendiosa contesa ci-adina con crescente irritazione. Essa ha portato alla formazione di due facinorose fazioni e ha fa-o crescere il numero degli eccessivi frequentatori della Gasthaus, con danno della quiete pubblica. Quindi anche lui, dopo un accurato studio della teoria dei grafi, decide di costruire un decimo ponte che consenta a tuX i ci-adini di passare tuX i ponE e fare ritorno alla propria casa tra i tranquilli affeX familiari.


Soluzioni


http://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.pnghttp://it.wikipedia.org/wiki/File:Koenigsberg_Bridges_Variations_Problem.png

Grafi per modellare reE sociali

• I grafi sono da sempre lo strumento usato per la modellazione di reE sociali (o social networks).• Nota bene: le social networks esistono da prima di Internet!

21


Grafo delle amicizie

• I nodi sono le persone, gli archi sono le amicizie (conoscenze?) tra le persone.• Quanta distanza c’è tra due persone?• La distanza è il più breve cammino tra le due persone.• Quanto sono lunghi i cammini in questo grafo?

22


Esperimento di Milgram

Nel 1967, Milgram fece il seguente esperimento (voleva scoprire qual’era la probabilità che due persone scelte a caso si conoscessero):• Diede delle leCere a persone di Omaha (Nebraska) e Wichita (Kansas), desHnate a residenH di Boston (Massachussets).• Le buste potevano essere passate solo a conoscenH.• Tra le buste che giunsero a desHnazione, la media dei passaggi di mano fu 5.5.• Questo condusse alla nascita dell’idea dei SEI GRADI DI SEPARAZIONE

23


Small World Phenomenon

O “fenomeno di mondo piccolo”: nonostante una rete sia numerosa (abbia un gran numero di nodi), il diametro (= massima distanza minima =massimo cammino minimo) è piccolo!

24


Esempi di Small World Phenomenon

• Numero di Erdős: i nodi della rete sono autori di arEcoli di matemaEca, e c’è un arco tra due autori se hanno lavorato insieme in un arEcolo• Numero di Bacon (Kevin): i nodi della rete sono a-ori cinematografici, e c’è un arco tra due a-ori se hanno lavorato insieme in un film

25


Numero di Erdős

• Esiste, sul sito della AMS, un “calcolatore del numero di Erdős”:

26


Numero di Erdős

• Esiste, sul sito della AMS, un “calcolatore del numero di Erdős”:

27


Numero di Bacon

28


Numero di Bacon

29


Altri “numeri”...

• Numero di Erdős-‐Bacon: somma del numero di Erdős con il numero di Bacon (sono in pochi che lo hanno!)• Numero di Morphy: distanza in parEte di scacchi con Paul Morphy• Numero di Shusaku: distanza in parEte di GO con Honinbo Shusaku

30


Conseguenze dello SWP• Se la distanza tra tuX è piccola, il numero di persone a distanza “molto” piccola è numeroso!

31


Visualizzazione di ReE Sociali

• Per renderci conto del piccolo diametro, possiamo provare a visualizzare la mappa dei nostri social network!• Tante reE sociali hanno reso disponibili dei tool per poterle visualizzare• Tra queste: Facebook, Twi-er, LinkedIn...

32


LinkedIn Maps

33


Twi-er (MenEonMap)

34


Facebook Social Graph

35


Facebook Social Graph

36


Problema del PosEno Cinese

(Chinese Postman Problem)Un posEno (cinese) pigro, deve consegnare la posta a un insieme di strade. Dal momento che è pigro, vuole trovare il più breve percorso che:• inizi e finisca nello stesso punto (ovvero, sia un ciclo);• percorra tu-e le strade almeno una volta.

37



Se il grafo amme-e un ciclo euleriano, allora questo è la soluzione oXma:• inizia e finisce nello stesso punto (nodo)• percorre tu-e le strade (archi) una sola volta

38



Applicazioni praEche:• pianificazione di percorsi minimi;• problemi di ispezione/pulizia di sistemi distribuiE (e.g., reE ele-riche, telefoniche, ferroviarie, stradali)

39


Problema dei tre nemici

(o anche problema delle tre case e tre forniture)Tre nemici hanno le case vicine. Si devono allacciare a tre forniture: acqua, luce e gas. Siccome non vogliono avere discussioni, decidono di me-ere i cavi in maniera da evitare incroci. E’ possibile?

40



Esempio:

41



Applicazioni praEche:• problemi di posa in opera di reE ele-riche/tubature• problemi di disegno di circuiE integraE

42


Problema del commesso viaggiatore

• Dato un insieme di ci-à collegate da strade, qual’è il percorso più breve che le visita tu-e una sola volta?

43


Problema del commesso viaggiatore“Researchers Forge New Optimal Path For Traveling Salesman Problem”

“HOUSTON, Texas, June 8, 1998 -- Rice University researchers David Applegate, Robert Bixby and William Cook, and Vasek Chvatal of Rutgers University have determined a breakthrough solution to the Traveling Salesman Problem (TSP), a method for finding an optimal path for a salesman to take when traveling through a specified number of cities.

The researchers have solved the TSP for 13,509 U.S. cities with populations of more than 500 people, a dramatic step beyond their previous record of 7,397 cities, set in 1994.”

44


Problema del commesso viaggiatore

45


Colorazione di mappe

• Quale è il numero minimo di colori necessari a colorare una qualunque carta geografica (passata, presente e futura) in modo che due staE/regioni adiacenE non abbiano mai lo stesso colore?

46



• Passaggio da una mappa a un grafo:

• Il problema diventa equivalente alla colorazione di grafi: dato un grafo, è possibile colorare i suoi nodi con k colori in maniera che nodi adiacenE abbiano colori diversi?

47



48

Mappa degli StaH UniH colorata con 4 colori



• Per esercitarsi:

49


Teorema dei qua-ro colori

• Per colorare una qualsiasi mappa, bastano qua-ro colori.• La conge-ura è del 1852, di Francis Guthrie che si accorse che per colorare una mappa dell’europa bastavano 4 colori• 1879 Kempe lo dimostra• 1890 Heawood trova un errore nella dimostrazione di Kempe, e dimostra che 5 colori bastano sempre...

50


Teorema dei qua-ro colori

• ... viene finalmente dimostrato nel 1977 da parte di Kenneth Appel e Wolfgang Haken, due matemaEci dell'Università dell'Illinois, grazie a un complesso algoritmo.• L’algoritmo riduce le infinite mappe a 1936 configurazioni che vengono provate (a forza bruta) da un calcolatore.• Migliaia di ore di calcolo, più di 500 pagine di dimostrazione.

51


http://it.wikipedia.org/wiki/1977http://it.wikipedia.org/wiki/1977http://it.wikipedia.org/w/index.php?title=Kenneth_Appel&action=edit&redlink=1http://it.wikipedia.org/w/index.php?title=Kenneth_Appel&action=edit&redlink=1http://it.wikipedia.org/w/index.php?title=Wolfgang_Haken&action=edit&redlink=1http://it.wikipedia.org/w/index.php?title=Wolfgang_Haken&action=edit&redlink=1

E per colorare un grafo?

• ... bastano sempre qua-ro colori?

52


Rompicapo: il salto del cavallo

• Riuscite, muovendo secondo le regole degli scacchi, a scambiare di posto i due cavalli neri con i due cavalli bianchi?

53


Rompicapo: il salto del cavallo

• Il problema è riconducibile a un problema equivalente su grafi:

54


Introduzione alla Teoria dei Graﬁlaura/assets/files/pswb/03-IntroGrafi.pdf · Introduzione alla...

Documents

Transcript of Introduzione alla Teoria dei Graﬁlaura/assets/files/pswb/03-IntroGrafi.pdf · Introduzione alla...