Skip to content

Latest commit

 

History

History
515 lines (353 loc) · 9.88 KB

a1. Grafi.md

File metadata and controls

515 lines (353 loc) · 9.88 KB

I grafi sono formati da due insiemi:

  • Insieme dei vertici ($V$)
  • Insieme degli archi ($E$)

$$G=(V,E)$$

Insieme Dei Vertici

$$V={1,2,3,4}$$

Insieme Degli Archi

$$E={(1,2),(1,3),(2,3),(2,4),(3,4)}$$

è formato da coppie di vertici, se le coppie sono ordinate il grafo è orientato, se non sono ordinate il grafo è non orientato.

Tipi Di Grafi

Grafo Bipartito

è un grafo che ha come vertici due insiemi separati, i cui archi collegano solo i vertici di un insieme ai vertici dell'altro, non ci sono collegamenti tra vertici dello stesso sottoinsieme.

![[Grafo bipartito.svg|center]]


$$R=\{1,2,3\}$$
$$L=\{4,5,6\}$$
$$V=\{L\cup R\}$$
$$E=\{(1,4), (4,3), (2,5)\}$$

Mesh

I grafi a maglia possono essere impostati come dei grafi bipartiti

![[Grafo Mesh.svg|center small]]

Aisle Graph (Modello frutteto)

![[Grafo frutteto.svg|center small]]

$$e=[(i,j),(i+1,j)]$$

Reti

![[Grafo rete.svg|center small]]

Dimensione Dei Grafi

$$|V|=n$$

$$|E|=m \begin{cases} |E| \leq \frac {n(n-1)}2 & \text{grafo non orientato}\ |E| \leq n(n-1) & \text{grafo orientato} \end{cases}$$ Un grafo connesso (con tutti i vertici connessi tra loro) non orientato di dimensione $|V|=n$ ha un numero di archi $|E|=\frac {n(n-1)}2$

Grafo Connesso

Un grafo non orientato si definisce connesso se:

$$\forall z,u \in V, z \neq u$$ $$\exists u \sim z$$

title: Path ($\sim$)

Sequenza di vertici tale che ogni coppia di vertici consecutivi è legato da un arco

Alberi

Un grafo connesso che ha il minor numero di archi possibile ($|E| = |V| - 1$) si chiama albero, se si rimuove un arco questo grafo non è più connesso.

![[Pasted image 20230301101608.png| center]]

Se G ha $n-1$ vertici, ma è disconnesso allora non è un grafo.

Memorizzare Un Grafo

$$G=(V,E)$$ ![[Grafo1.svg|center mid]]

Matrice Delle Adiacenze

1 2 3 4
1 0 1 1 0
2 1 0 1 0
3 1 1 0 1
4 0 0 1 0

Lista Delle Adiacenze

|i | $\to$ |lista| | | |---|---|---|---| | 1 | $\to$ | 2 | 3 | | 2 | $\to$ | 1 | 3 | | 3 | $\to$| 1 | 4 | |4| $\to$|3| |

Vettore Delle Adiacenze

Sono 2 vettori:

  • $V$ che contiene la posizione in E in cui è presente il primo arco uscente.
  • $E$ in cui sono scritti quali archi sono collegati
V E
1 1 2
2 3 3
3 4 3
4 - 4

Complessità Di Un Grafo

A seconda se il grafo sia sparso oppure denso la complessità del suo arco varia da $\Theta(n)$ a $\Theta(n^2)$.

L'[[#Esplorare Un Grafo|esplorazione]] di un grafo impiega $\Omega(V+E)$ (complessità intrinseca), ma a seconda della sua struttura dati può costare:

  • Lista delle adiacenze, vettore delle adiacenze $O(V+E)$
  • Matrice delle adiacenze $O(v^2)$

Esplorare Un Grafo

Dato un grafo connesso, esplorare G vuol dire estrarre un albero che esplora tutti i vertici di G

Visita in Profondità (DFS-visit)

Depth First Search visit.

La DFS-visit è preceduta dalla procedura di inizializzazione

initialize(G=(V,E))
	for v in V:
		color(v) = white
		P(v) = nil

L'obiettivo è quello di estrarre un albero di copertura radicato nel primo vertice passato alla procedura dfs-visit.

un vertice è:

  • white: non visitato
  • gray: visitato
  • black: visitati tutti gli archi

Ogni volta che tocco un vertice mai esplorato vado a esplorare tutti i vertici a esso connessi.

dfs-visit(G=(V.E), u):
	color(u) = grey
	for v in Adj(u):
		if color(v) == white:
			(u,v) in T
			P(v) = u
			dfs-visit(G, v)
		else if v != P(u):
			(u,v) in B
		else
			(u, v) in T
	color(u) = black


- Un grafo connesso è un __albero__ se _non esistono_ archi in $B$.
- Un grafo connesso ha un __ciclo__ se _esistono_ archi in $B$

Grafo Orientato

Esplorazione di $G,; v \in V$, visibilità di $v$ in $G$

dfs-visit(G, v, time):
	color(v) = gray
	time++;
	d(v) = time
	for u in adj(v):
		if color(u) == white:
			(v, u) in T
			P(u) = v
			dfs-visit(G, u, time)
		if color(u) == gray:
			(v, u) in Backward
		if color(u) == black and d(v) < d(u): 
			(v, u) in Forward
		else:
			(v, u) in Cross
	color(v) == black
	time++
	f(v) = time


- Un grafo connesso _senza cicli_ (senza archi Backward) si dice __Direct Acyclic Graph (DAG)__
- Un grafo orientato aciclico ha almeno un __sink__, cioè un vertice senza archi uscenti.

Sort Topologico O Linearizzazione

è un ordinamento dei vertici: $\forall e= (u,v)$ $u$ precede $v$ nell'ordinamento dei vertici

sort-topologico(G, DAG)
	1. DFS(G)
	2. inserisci in testa ad una lista L ogni nodo che diventa nero
	3. return L

repeat
	sia s un sink in G

title: Chiedere a qualcuno slide 12 [[topologicalsort-sinkuniversale-cfc.pdf]]





Cercare un sink in G rappresentato dalla matrice delle adiacenze

```ad-check
title: Soluzione semplice (non cerca sink universale)

	t = 1
	trovato = false
	while t < |v| and !trovato:
		if !sink-test(G, t):
			t++
		else:
			trovato = true
	return t

	sink-test(G, t):
		j = 1
		while j <= n and G[t, j] == 0: 
			j++
		return !(G[t, j] == 1)

La complessità nel worst case è $O(v^2)$ 
```

Sink Universale

trova-sink-universale(G):
	i = 1
	j = 1
	while (j <= n) && (i <= n):
		if G[i, j] == 1:
			i++
		else:
			j++
	if i > n:
		return false
	else:
		return test-sink(G, j)

L'algoritmo appena proposto non funziona per trovare un sink singolo, ma solo per il sink universale

Componenti Fortemente Connesse

Per ogni coppia $(u, v) \in V$ di vertici esiste un cammino $u \to v$ che li lega

![[fortemente_connesso.svg|center]] $$(2,4) \to2,3,4$$ $$(4,2)\to4,5,1,2$$

Conta CFC

dfs(G = (V, E)):
	for v in V:
		color(v) = white
		P(v) = nil
	num_cc = 0
	for i = 1:|v|
		if color(i) == white:
			num_cc++
			dfs-visit(G, i)

num_cc indica le componenti connesse

Associare a Ogni Vertice La Componente Connessa

Basta chiamare dfs-visit passando il valore di num_cc

dfs-visit(G, i, num_cc)


![[esempio.svg|center]]

| | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| color| g | g | g | g | g | g|
|P| nil | 1 | 2 | 3 | 4 | 5 |
|

```ad-missing
title: Riguardare 15-03-2023

Grafo Delle Componenti Fortemente Connesse (C.F.C.)

i vertici sono componenti fortemente connesse e gli archi sono gli archi del grafo originario che vanno da una CFC a un'altra.

$$G^{scc} = {V;E}$$ ![[componenti.svg|center mid]]


Una componente fortemente connessa corrisponde a un albero i cui vertici sono i vertici della componente fortemente connessa



Per disegnare questo grafo mi interessano solo gli archi che vanno da vertici appartenenti a componenti fortemente connesse


title: supponiamo per assurdo che il grafo non sia un DAG

![[non_dag.svg|center]]

```ad-failure

Esistendo l'arco B, l'intero grafo diventa una componente fortemente connessa, non rendendolo più un $G^{scc}$

```

Grafo Trasposto

Grafo con tutti gli archi invertiti

 ![[trasposto.svg|center]]


ho trovato un albero radicato in 1
1 2 3 4 5 6
color g g g g g g
P nil 3 1 nil nil nil
d 1 3 2 7 9 11
h 6 4 5 8 10 12 

Se calcolo il traspoto di un $G^{scc}$ ottengo un __reverse sort topologico__

Quadrato Di Un Grafo

Vogliamo calcolare il grafo $G^2$ che ha gli stessi vertici di $G$ ma ha come vertici $E^2$

$$G^2=(V, E^2)$$

$$e \in E \iff e = e_1 e_0, e_1 \in E, e_0 \in E$$ $$(i, j) \in E^2 \implies (i, w) \in E \wedge (w, j) \in E$$ ![[immagini/Algoritmi/Untitled Diagram.svg|center big]]

Il calcolo di $G^2$ richiama il calcolo del prodotto di due matrici: $$P = A \cdot B$$

$$P_{ij}= \sum_{k=1}^n{a_{ik} \odot b_{kj}} $$

square( G ):
	for r = 1:n
		for c = 1:n
			G2[r, c] = 0
			for k = 1:n
				if G[r, k] and G[k, c]:
					G2[r, c] = G2[r, c] or 1

title: Calcolo di $G^*$ 

$$G^* = G \cup G^2$$

	g-star( G ):
		G2 = square(G)
		for r = 1:n
			for c = 1:n
				GS[r, c] = G[r, c] or G2[r, c]


	star(G, GS):
		for r = 1:n
			for c = 1:n
				GS[r, c] = G[r, c]
				for k = 1:n
					if G[r, k] and G[k, c]:
						GS = GS[r, c] or 1

Breadth First Search

BFS(G, s * source):
	for v in V:
		color(v) = white
		P(v) = nil
	color(s) = gray
	EnQueue(Q, s)
	while (Q not empty):
		u = DeQueue(Q)
		for v in adj(u):
			if color(v) = white:
				(u, v) in T
				P(v) = u
				color(v) = gray
				EnQueue(Q, v)
		color(u) = black

collapse: open
title: Calcolo della distanza

	BFS(G, s * source):
		for v in V:
			color(v) = white
			P(v) = nil
			d(v) = infinite
		color(s) = gray
		d(s) = 0
		EnQueue(Q, s)
		while (Q not empty):
			u = DeQueue(Q)
			for v in adj(u):
				if color(v) = white:
					(u, v) in T
					P(v) = u
					color(v) = gray
					d(v) = d(u) + 1
					EnQueue(Q, v)
			color(u) = black



- d(v) dipende solo dalla sorgente
- d è __crescente__
- BFS(G, s) visita ogni vertice raggiungibile da s
- dist(s, s) = 0 = d(s)
- dist(s, v) = distanza da s a v = d(v)

Diametro

Dato un grafo G trovare il diametro di Gs

![[Untitled Diagram 1.svg|center]]

for u,v in VxV:
	if d(u, v) > max:
		max = d(u, v)
return max

Archi Nella BFS

Gli archi sono denominati rispetto alla loro posizione dei loro estremi in T:

  • back verso antenato
  • forward verso discendente
  • cross altrimenti

Nel grafo non orientato esistono solo gli archi cross

Euler Tour

visit(G, L, v):
	C = 0
	u in v
	while dist(u) > 0:
		let w in adj(u)
		delete (u, w)
		dist(u)--
		add u to C
		if dist(u) > 0:
			add u to L
		u = w
	return C

euler-tour(G):
	T = 0
	L = any vertex in G
	while L != 0:
		remove v from L
		C = visit(G, L, v)
		if location in T = nil:
			T in C
		else:
			introduce C before  locator of v in T