Connettività

WALK, TRAIL, PATH

2

Walk (passeggiata)

Walk (passeggiata): Una passeggiata è una sequenza di nodi e link che inizia e finisce con un nodo, in cui ogni nodo è incidente allo spigolo che lo precede e allo spigolo che lo segue nella sequenza.

– Open walk: Nodo di partenza diverso da quello di arrivo

– Close walk: Nodo di partenza coincidente con quello di arrivo

• Nei grafi semplici è sufficiente la lista dei nodi • Lunghezza della passeggiata: numero degli spigoli

Length of walk= 8

Trail

• Un trail (percorso) è una passeggiata in cui tutti gli spigoli sono distinti (uno spigolo non può essere attraversato più di una volta)

• Un trail chiuso è detto tour o circuit

Path

• Un path (cammino) è una passeggiata dove sia i nodi sia gli spigoli sono distinti (spigoli e nodi non possono essere attraversati più di una volta)

• Un path chiuso è detto cycle (ciclo)

• La lughezza del path è il numero di spigoli che attraversa

Length of path= 4

Examples

Eulerian Tour

• Un tour che attraversa tutti gli spigoli (una sola volta)

• Konigsberg bridges

Hamiltonian Cycle

• Un ciclo che visita tutti I nodi (una sola volta)

Königsberg

A Königsberg in Prussia c’è un'isola A, chiamata der Kneiphof, e il fiume che la circonda si divide in due rami, come si può vedere in figura; i rami di questo fiume sono muniti di sette ponti a, b, c, d, e, f, g. Circa questi ponti veniva posta questa domanda, si chiedeva se fosse possibile costruire un percorso in modo da transitare attraverso ciascun ponte una e una sola volta. E mi fu detto che alcuni negavano ed altri dubitavano che ciò si potesse fare, ma nessuno lo dava per certo. Da ciò io ho tratto questo problema generale: qualunque sia la configurazione e la distribuzione in rami del fiume e qualunque sia il numero dei ponti, si può scoprire se è possibile passare per ogni ponte una ed una sola volta?

Königsberg

Königsberg

Königsberg

10

Eulero stabilì che un grafo composto soltanto da nodi pari, cioè ciascuno collegato a un numero pari di archi, è sempre percorribile e che si può ritornare al punto di partenza senza sovrapposizioni di percorso (circuito euleriano). Se un grafo contiene nodi pari e soltanto due nodi dispari è ancora percorribile, partendo da uno dei noti dispari per arrivare all'altro, ma non si può più ritornare al punto di partenza. Se contiene invece più di due nodi dispari, non è percorribile senza sovrapposizioni di percorso.

Distanza tra due nodi

11

La distanza (distance) tra due nodi è il numero di spigoli di un

cammino a lunghezza minima che li connette

*Se due nodi sono disconnessi, la distanza è +∞.

Nei grafi orientati il cammino deve seguire la direzione dei

link.

Quindi la distanza tra due nodi A e B può essere diversa da

quella tra B e A.

Un nodo i si dice raggiungibile (reachable) da un nodo j se

esiste un cammino da j a i.

Diametro (diameter) di un grafo: distanza massima tra tutte le

coppie di un grafo D

C

A

B

D C

A

B

Random walk

• Una passeggiata in cui il nodo successivo viene scelto in modo casuale tra i vicini.

– Se il grafo è pesato si possono definire le probabilità in funzione del peso.

Connettività della network

13

Connettività

• Un nodo vi è connesso a un nodo vj (raggiungibile da vj) se esiste un path tra vi e vj.

• Un grafo è connesso se esiste un path tra ogni sua coppia di nodi

• Un grafo è disconnected se non è connesso.

Connettività nei grafi orientati

– Un grafo orientato è strongly connected (fortemente connesso) se esiste un cammino orientato tra ogni coppia ordinate di vertici

Esiste il cammino AB e il cammino BA

– Un grafo orientato è weakly connected (debolmente connesso) se esiste un cammino tra ogni coppia di vertici senza considerare l’orientamento degli archi

15

Connettività: esempi

Componenti connesse

• Componente: sottografo tale che esista almeno un path tra ogni coppia di vertici e non esista alcun altro vertice del grafo connesso ad alcun vertice della componente. – massimale

• Singoletto:componente connessa con un solo vertice

• Ogni vertice appartiene a una e una sola componente

17

Component

• In directed graphs, we have a strongly connected components when there is a path from u to v and one from v to u for every pair (u,v).

• The component is weakly connected if replacing directed edges with undirected edges results in a connected component.

Component Examples:

3 components 3 Strongly-connected components

Esercizio

A

B

C

D

E

F

G

H

20

Quante e quali componenti fortemente connesse? Quante e quali componenti debolmente connesse?

Esercizio: soluzione

A

B

C

D E

F G

H

Weakly connected components

A B C D E

G H F

21

Strongly connected components

Each node within the component can be reached from every

other node in the component by following directed links

Strongly connected components

B C D E

A

G H

F

Weakly connected components: every node can be reached from

every other node by following links in either direction

A

B

C

D E

F G

H

La matrice di adiacenza di una rete con più componenti è diagonale a blocchi

Network Science: Graph Theory

Bridges

• I ponti (bridges) sono archi la cui rimozione aumenta il numero di componenti connesse

Breadth-First Search (BFS)

La visita in ampiezza breadth-first-search (BFS) di un grafo dato un vertice sorgente s consiste nella esplorazione sistematica di tutti i vertici raggiungibili da s in modo tale da esplorare tutti i vertici che hanno distanza k prima di iniziare a visitare quelli che hanno distanza k+1

Breadth-First Search (BFS)

BFS parte da un nodo, ne visita tutti i primi vicini e quindi i vicini dei vicini …

Breadth-First Search (BFS)

1. Nodo sorgente: etichetta 0

2. Assegnare a tutti suoi vicini etichetta 1 ed inserirli in una coda

3. Togliere dalla coda il primo nodo (etichetta n in generale, 1 al primo passo). Cercare tutti i suoi vicini che non abbiano etichetta, assegnare etichetta n+1 ed inserirli nella coda

4. Ripetere il passo 3 finché non si visiti il nodo di destinazione o la coda sia vuota.

5. La distanza tra il nodo sorgente e quello di destinazione è l’etichetta di questo ultimo

1.Nodo iniziale: 0

Network Science: Graph Theory Network Science: Graph Theory

1 1 1

1

2

2

2 2

2

3

3

3

3

3

3

3

3

4 4

4

4

4

4

4

4

Network Science: Graph Theory

0

Calcolo delle distanze

Network Science: Graph Theory

1 1 1

1

2

2

2 2

2

3

3

3

3

3

3

3

3

4 4

4

4

4

4

4

4

Distanza tra nodo 0 e nodo 4:

1.Parti dal nodo 0.

2.Trova tutti I nodi adiacenti al nodo 0, assegna distanza 1 e poni in una coda

Network Science: Graph Theory

0 1 1

1

Calcolo delle distanze

Network Science: Graph Theory

1 1 1

1

2

2

2 2

2

3

3

3

3

3

3

3

3

4 4

4

4

4

4

4

4

Network Science: Graph Theory

0 1 1

1

2

2

2 2

2

Network Science: Graph Theory

1

1

Calcolo delle distanze

Distance between node 0 and node 4:

1.Repeat until you find node 4 or there are no more nodes in the queue.

2.The distance between 0 and 4 is the label of 4 or, if 4 does not have a label, infinity.

FINDING DISTANCES: BREADTH FIRST SEARCH

Network Science: Graph Theory

0 1 1

1

2

2

2 2

2

3

3

3

3

3

3

3

3

4 4

4

4

4

4

4

4

BFS per la ricerca delle componenti connesse

1. Si effettui una BFS con nodo iniziale random e si etichetti tutti i nodi visitati con n=1

2. Se il numero di nodi con etichetta 1 è uguale al numero di nodi N del grafo, il grafo è connesso, altrimenti passo 3

3. nn+1. Si effettui una estrazione casuale tra i nodi non etichettati di un nodo j e lo si etichetti con n. Si effettui una BFS con nodo iniziale j e si etichetti tutti i nodi visitati con n. Si torni al passo 2.

Algoritmo di Dijkstra

Ricerca del cammino a lunghezza minima e della distanza tra due nodi in grafi pesati

• Dijkstra’s Algorithm

– Grafi pesati con pesi non negativi

– Trova il cammino minimo da un nodo fissato s a tutti gli altri nodi del grafo

– Restituisce I cammini minimi e la loro lunghezza

4-33

Algoritmo di Dijsktra

1 Inizializzazione:

2 N' = {u}

3 per tutti i nodi v

4 se v è adiacente a u

5 allora D(v) = c(u,v)

6 altrimenti D(v) = +∞

7

8 Ciclo

9 determina un w non in N' tale che D(w) sia minimo

10 aggiungi w a N'

11 aggiorna D(v) per ciascun nodo v adiacente a w e non in N' :

12 D(v) = min( D(v), D(w) + c(w,v) )

13 /* il nuovo costo verso v è il vecchio costo verso v oppure

14 il costo del cammino minimo noto verso w più il costo da w a v */

15 Finché N’ = N

Esercizio

34

u

y x

w v

z

2

2

1

3

1

1

2

5

3

5

4-35

Algoritmo di Dijkstra: esempio

passo

0

1

2

3

4

5

N'

u

ux

uxy

uxyv

uxyvw

uxyvwz

D(v),p(v)

2,u

2,u

2,u

D(w),p(w)

5,u

4,x

3,y

3,y

D(x),p(x)

1,u

D(y),p(y) +∞ 2,x

D(z),p(z) +∞ +∞

4,y

4,y

4,y

u

y x

w v

z 2

2

1 3

1

1

2

5 3

5 Shortest paths: uv uw ux uxy uxyz