Marco Pagnin, Page 9 Author

Tratto dall'esame del 27/05/2017 di Algoritmi e Strutture Dati (M. Pelillo)

MyAlgorithm( A )
1. n = rows(A) /* determina il numero di vertici del grafo */
2. let B an n x n matrix /* alloca memoria per una matrice B n x n */
3. for i = 1 to n
4.   for j = 1 to n
5.     b[i,j] = 0
6.     for k = 1 to n
7.       b[i,j] = b[i,j] + a[i,k]*a[k,j]
8. for i = 1 to n
10.  for j = i + 1 to n
11.     if a[i,j]*b[i,j] <> 0 then
12.return FALSE
13.return TRUE

Evidentemente l'algoritmo è composto da due parti: nella prima si crea una matriche di dimensioni uguali alla matrice di adiacenza e si fa un calcolo.
Nella seconda, si verifia la matrice ottenuta in modo che se lo stesso elemento nella matrice di adiacenza e nella matrice calcolata contiene 1 si restituisca FALSE.

Esempio

La matrice di adiacenza corrispondente è la seguente:

	A	B	C	D	E
A	-	1	0	0	1
B	1	-	1	1	1
C	0	1	-	0	0
D	0	1	0	-	1
E	1	1	0	1	-

---

• i = 1
• j = 1
• k = 1 ⇒ 5

Matrice a

Matrice a

	A	B	C	D	E
A	-	1	0	0	1
B	1	-	1	1	1
C	0	1	-	0	0
D	0	1	0	-	1
E	1	1	0	1	-

---

Matrice b, k = 1

	A	B	C	D	E
A	0
B
C
D
E

Matrice b, k = 2

	A	B	C	D	E
A	1
B
C
D
E

Matrice b, k = 3

	A	B	C	D	E
A	1
B
C
D
E

Matrice b, k = 4

	A	B	C	D	E
A	1
B
C
D
E

Matrice b, k = 5

	A	B	C	D	E
A	2
B
C
D
E

---

In effetti, quanti vertici collegati ha A in comune con A stesso? Due, cioè B ed E. Procediamo.

• i = 1
• j = 2
• k = 1 ⇒ 5

Matrice a

Matrice a

	A	B	C	D	E
A	-	1	0	0	1
B	1	-	1	1	1
C	0	1	-	0	0
D	0	1	0	-	1
E	1	1	0	1	-

---

Matrice b, k = 1

	A	B	C	D	E
A	2	0
B
C
D
E

Matrice b, k = 2

	A	B	C	D	E
A	2	0
B
C
D
E

Matrice b, k = 3

	A	B	C	D	E
A	2	0
B
C
D
E

Matrice b, k = 4

	A	B	C	D	E
A	2	0
B
C
D
E

Matrice b, k = 5

	A	B	C	D	E
A	2	1
B
C
D
E

---

In effetti, quanti vertici collegati ha A in comune con A stesso? Due, cioè B ed E. Procediamo.

• i = 1
• j = 3
• k = 1 ⇒ 5

Matrice a

Matrice a

	A	B	C	D	E
A	-	1	0	0	1
B	1	-	1	1	1
C	0	1	-	0	0
D	0	1	0	-	1
E	1	1	0	1	-

---

Matrice b, k = 1

	A	B	C	D	E
A	2	1	0
B
C
D
E

Matrice b, k = 2

	A	B	C	D	E
A	2	1	1
B
C
D
E

Matrice b, k = 3

	A	B	C	D	E
A	2	1	1
B
C
D
E

Matrice b, k = 4

	A	B	C	D	E
A	2	1	1
B
C
D
E

Matrice b, k = 5

	A	B	C	D	E
A	2	1	1
B
C
D
E

---

In effetti, quanti vertici collegati ha A in comune con A stesso? Due, cioè B ed E. Procediamo.

• i = 1
• j = 4
• k = 1 ⇒ 5

Matrice a

Matrice a

	A	B	C	D	E
A	-	1	0	0	1
B	1	-	1	1	1
C	0	1	-	0	0
D	0	1	0	-	1
E	1	1	0	1	-

---

Matrice b, k = 1

	A	B	C	D	E
A	2	1	1	0
B
C
D
E

Matrice b, k = 2

	A	B	C	D	E
A	2	1	1	1
B
C
D
E

Matrice b, k = 3

	A	B	C	D	E
A	2	1	1	1
B
C
D
E

Matrice b, k = 4

	A	B	C	D	E
A	2	1	1	1
B
C
D
E

Matrice b, k = 5

	A	B	C	D	E
A	2	1	1	2
B
C
D
E

---

In effetti, quanti vertici collegati ha A in comune con A stesso? Due, cioè B ed E. Procediamo.

• i = 1
• j = 5
• k = 1 ⇒ 5

Matrice a

 

Matrice a

	A	B	C	D	E
A	-	1	0	0	1
B	1	-	1	1	1
C	0	1	-	0	0
D	0	1	0	-	1
E	1	1	0	1	-

---

Matrice b, k = 1

	A	B	C	D	E
A	2	1	1	2	0
B
C
D
E

Matrice b, k = 2

	A	B	C	D	E
A	2	1	1	2	1
B
C
D
E

Matrice b, k = 3

	A	B	C	D	E
A	2	1	1	2	1
B
C
D
E

Matrice b, k = 4

	A	B	C	D	E
A	2	1	1	2	1
B
C
D
E

Matrice b, k = 5

	A	B	C	D	E
A	2	1	1	2	1
B
C
D
E

---

Qui termina l'elaborazione della prima delle cinque righe, per tutte le colonne e per tutte le adiacenze.
Cosa ci dice questo primo risultato?

Ci dice che il vertice A ha in comune:

• con se stesso i vertici B ed E, per un totale di due
• con B il vertice E, per un totale di uno
• con C il vertice B per un totale di uno
• con D i vertici B ed E, per un totale di due
• con E il vertice B, quindi uno

Al termine del ciclo annidato, la tabella b prende i seguenti valori:

Matrice b, risultato finale

	A	B	C	D	E
A	2	1	1	2	1
B	1	4	0	1	2
C	1	0	1	1	1
D	2	1	1	2	1
E	1	2	1	1	3

Possiamo osservare che anche se la matrice b contiene 25 valori, la diagonale principale rappresenta il numero di archi collegati al vertice in oggetto (es. il vertice A ha due archi, quindi il valore è 2).

Inoltre, essendo un grafo non orientato, anche la b gode della simmetria, quindi il "calcolo" vero e proprio consiste solo in 10 "celle" (n * (n-1) / 2).

Matrice b, significato di diagonale e simmetria

	A	B	C	D	E
A	2	1	1	2	1
B	1	4	0	1	2
C	1	0	1	1	1
D	2	1	1	2	1
E	1	2	1	1	3

Se ora sovrapponiamo a e b (moltiplicandone i valori tra loro), otteniamo una matrice contenente alcuni archi:

Matrice a * b

	A	B	C	D	E
A	-	1	0	0	1
B	1	-	0	1	2
C	0	0	-	0	0
D	0	1	0	-	1
E	1	2	0	1	-

Conclusioni

Questo algoritmo serve a individuare se in un grafo sono presenti cicli composti da tre vertici.

Dato un grafo orientato e pesato G=(V, E) con pesi positivi, cioè w(u, v) > 0 per ogni (u, v) ∈ E, si vuole determinare se esiste in G un ciclo c ≡ <x₀, x₁, ... x_q> (con x₀ = x_q) per cui sia soddisfatta la seguente condizione:

$\underset{i=1}{\overset{q}{\Pi }}2w{\left(x_{i=1},x_i\right)}^3>2^q$

Si sviluppi un algoritmo per risolvere questo problema, se ne discuta la correttezza e si determini la sua complessità computazionale. (Suggerimento: si cerchi di ricondurre il problema dato ad uno noto)

Dare la definizione di max-heap e dire se ‹23,17,14,6,13,10,1,5,7,12› è un max-heap giustificando la risposta.

Svolgimento

Un max-heap è un albero in cui gli elementi sono tutti non maggiori dell'elemento padre.

L'implementazione ad array di uno heap binario consiste nel posizionare come primo elemento la radice dell'albero (23, nell'esercizio) e poi per ogni livello l 2^l elementi, in posizione 2^l e 2^l+1.

L'albero corrispondente all'array è quindi

               23
      17              14
  6        13      10     1
5   7    12

Dal momento che 7 > 6, questo non è un max-heap.

In una tabella Hash di m = 17 posizioni, inizialmente vuota, devono essere inserite le seguenti chiavi numeriche nell’ordine indicato:

23, 40, 15, 58, 85

Indicare per ogni chiave la posizione finale dove viene allocata in questi due casi:

a. Funzione Hash:

h(k) = k mod m

Risoluzione delle collisioni mediante concatenamento

b. La tabella è a indirizzamento aperto e la scansione è eseguita per doppio Hashing:

h(k, i) = (k mod m + i * 2k mod 5) mod m

Si devono indicare tutte le posizioni scandite nella tabella.

Svolgimento

Caso A:

1. 23 mod 17 = 6 → 6[0] = 23
2. 40 mod 17 = 6 → 6[1] = 40
3. 15 mod 17 = 15 → 15[0] = 15
4. 58 mod 17 = 7 → 7[0] = 58
5. 85 mod 17 = 0 → 0[0] = 85

Risultato:

0: 85; 1:; 2:; 3:; 4:; 5:; 6: 23, 40; 7: 58; 8:; 9:; 10:; 11:; 12:; 13:; 14:; 15: 15; 16:;

Caso B

1. i = 0, k = 23: (23 mod 17 + 0 * 2*23 mod 5) mod 17 = 6
2. i = 1, k = 40: (40 mod 17 + 1 * 2*40 mod 5) mod 17 = 6: c'è una collisione, quindi si scorre fino al numero 7
3. i = 2, k = 15: (15 mod 17 + 2 * 2*15 mod 5) mod 17 = 15
4. i = 3, k = 58: (58 mod 17 + 3 * 2*58 mod 5) mod 17 = 10
5. i = 4, k = 85: (85 mod 17 + 4 * 2*85 mod 5) mod 17 = 0

Risultato:

0: 85; 1:; 2:; 3:; 4:; 5:; 6: 23; 7: 40; 8:; 9:; 10: 58; 11:; 12:; 13:; 14:; 15: 15; 16:;

In una tabella Hash di m = 17 posizioni, inizialmente vuota, devono essere inserite le seguenti chiavi numeriche nell’ordine indicato:
18, 36, 155, 19
La tabella è a indirizzamento aperto e la scansione è eseguita per doppio Hashing:
h(k, i) = (k mod m + i * 2^{k mod 5}) mod m
Indicare per ogni chiave le posizioni scandite nella tabella e la posizione finale dove viene allocata.

i = 0, k = 18 → (18 mod 17 + 1 * 2^{18 mod 5}) mod 17 = (1 + 0 * 8) mod 17 = 1

i = 1, k = 36 → (36 mod 17 + 1 * 2^{36 mod 5}) mod 17 = (2 + 1 * 2) mod 17 = 4

i = 2, k = 155 → (155 mod 17 + 2 * 2^{155 mod 5}) mod 17 = (2 + 2 * 1) mod 17 = 4: collisione

i = 3, k = 155 → (155 mod 17 + 3 * 2^{155 mod 5}) mod 17 = (2 + 3 * 1) mod 17 = 5

i = 4, k = 19 → (19 mod 17 + 4 * 2^{19 mod 5}) mod 17 = (2 + 4 * 16) mod 17 = 15

La hash finale è la seguente (l'indicizzazione è 0 - n-1):

[_] [18] [_] [_] [36] [155] [_] [_] [_] [_] [_] [_] [_] [_] [_] [19] [_]

Si vuole costruire una rete stradale che colleghi cinque città (A-E), minimizzando i costi complessivi di realizzazione. I costi per la costruzione di una strada tra due città sono sintetizzati nella seguente tabella (dove +∞ significa che la strada è irrealizzabile):

	A	B	C	D	E
A	0	3	5	11	9
B	3	0	3	9	8
C	5	3	0	+∞	10
D	11	9	+∞	0	7
E	9	8	10	7	0

Si formuli il problema dato in termini di un problema di ottimizzazione su grafi, e si descriva un algoritmo per la sua soluzione discutendone correttezza e complessità. Infine, si simuli accuratamente l’algoritmo presentato per determinare una soluzione del problema.

Svolgimento

Il grafo è non orientato, poiché la matrice di adiacenza è simmetrica.

Si può utilizzare l'algoritmo di Kruskal, che è corretto, poiché è composto da

1. un'inizializzazione con tempo O(n) che termina sicuramente, in quanto è un ciclo
2. un ordinamento degli archi con costo O(m log(m)), che termina sicuramente, utilizzando un algoritmo di ordinamento che termina (es. mergesort o quicksort)
3. un ciclo per ciascun arco O(m) per ciascuno dei quali è necessario verificare se i due vertici appartengono allo stesso insieme O(log(n)) ⇒ O(m log(n)), operazione che termina sicuramente
4. l'aggiunta dell'arco e l'unione (eventuale) dei due sottoinsiemi, con costo O(log(m)), che termina sicuramente.

e che ha un costo complessivo di esecuzione O(m log(m))

1. gli archi ordinati sono AB(3), BC(3), AC(5), DE(7), BE(8), AE(9), BD(9), CE(10), AD(11), CD(+∞)
2. AB costituisce il primo arco aggiunto all'albero U, e A, B i primi due vertici (nota: sarebbe stato indifferente iniziare con BC, con un esito diverso ma costi uguali). Ora U = {A, B, (AB)}
3. BC è aggiunto, in quanto C non appartiene a U. Ora U = {A, B, C, (AB), (BC)}
4. AC non è aggiunto, in quanto sia A sia C appartengono a U
5. DE è aggiunto - pur non essendo ancora connesso. Ora U = {A, B, C, D, E, (AB), (BC), (DE)}
6. BE è aggiunto, perché B ed E appartengono a due set diversi. Ora U = {A, B, C, D, E, (AB), (BC), (DE), (BE)}
7. Per brevità riportiamo in un solo passaggio AE, BD, CE, AD, CD, che non sono inclusi.

Le strade da realizzare sono quelle evidenziate in neretto:

	A	B	C	D	E
A	0	3	5	11	9
B	3	0	3	9	8
C	5	3	0	+∞	10
D	11	9	+∞	0	7
E	9	8	10	7	0

Si stabilisca quale problema risolve il seguente algoritmo, che accetta in ingresso un grafo non orientato G = (V, E):

MyAlgorithm(G)
1. A = ∅
2. ordina i vertici di G per grado crescente
3. for each u ∈ V[G] do /* vertici estratti secondo l’ordine stabilito nel passo 2 */
4.    if MyFunction(G,A,u) then
5.       A = A ∪ {u}
6. return A

MyFunction(G,A,u)
1. for each v ∈ A do
2.    if (u,v) ∈ E[G] then
3.       return FALSE
4. return TRUE

Si dimostri la correttezza dell’algoritmo, si determini la sua complessità e si simuli infine la sua esecuzione sul seguente grafo:

Svolgimento

1. l'algoritmo restituisce l'insieme con i gradi più bassi possibile di elementi non collegati tra loro
2. l'algoritmo è corretto, perché, essendo composto da due cicli for innestati, termina sicuramente
3. la complessità è data da
   1. ordinamento O(n log(n))
   2. un ciclo Θ(n), che richiama un altro ciclo Θ(n), quindi il costo complessivo è Θ(n²)
   3. la ricerca dell'arco, che a seconda dell'implementazione può essere O(n) o O(log(n))
   4. la complessità totale è quindi O(n log(n)) + Θ(n²) + O(n) ⇒ O(n²)
4. L'esecuzione:
   1. Si considera l'elemento 6: A è vuoto, quindi MyFunction restituisce true e l'elemento viene aggiunto ad A
   2. Si considera l'elemento 1: A contiene solo 6, che non è collegato a 1. L'elemento è quindi aggiunto.
   3. Si considera l'elemento 5: non è collegato ad alcun vertice in A, quindi l'elemento è aggiunto.
   4. Si considera l'elemento 2: è collegato a 1, che è presente in A, quindi l'elemento non è aggiunto.
   5. Si considera l'elemento 4: è collegato a 5 e 6, che sono presente in A, quindi l'elemento non è aggiunto.
   6. Si considera l'elemento 3: è collegato a 1 e a 5, che sono presente in A, quindi l'elemento non è aggiunto.
   7. Il risultato finale è che A contiene 1, 5, 6.

Il seguente algoritmo accetta in ingresso la matrice di adiacenza di un grafo non orientato e restituisce un valore Booleano (TRUE / FALSE)

MyAlgorithm( A )
1. n = rows(A) /* determina il numero di vertici del grafo */
2. let B an n x n matrix /* alloca memoria per una matrice B n x n */
3. for i = 1 to n
4.    for j = 1 to n
5.       b[i,j] = 0
6.       for k = 1 to n
7.          b[i,j] = b[i,j] + a[i,k]*a[k,j]
8. for i = 1 to n
10.   for j = i + 1 to n
11.      if a[i,j]*b[i,j] <> 0 then
12.          return FALSE
13.return TRUE

Si calcoli la complessità computazionale di MyAlgorithm e si determini la sua funzione (in quali casi restituisce TRUE? in quali casi FALSE?). (Nota: Nel determinare la complessità si ignori per comodità la complessità delle istruzioni 1 e 2).
Si simuli inoltre il suo comportamento sui seguenti due grafi, verificando che restituisca il risultato atteso:

Risposta

L'algoritmo è trattato nella lezione 10 di Pelillo, in cui si parla del risultato di un prodotto tra la matrice di adiacenza e se stessa, e dei successivi prodotti tra la matrice e il risultato precedente.

Una volta terminato la prima serie di cicli annidati, di costo O(n³), si verifica con un'altra serie di cicli annidati, di costo O(n²), se esistono archi in comune. Se esistono (confronto alla riga 11), il grafo ha almeno un ciclo di lunghezza 3 vertici.
Il costo complessivo è O(n³) + O(n²), quindi O(n³).

Il comportamento si basa su matrice di adiacenza e matrice di appoggio.

Le matrici di adiacenza sono:

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

e  per il secondo grafo

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

Una volta terminati le 64 esecuzioni (4 x 4 x 4) della riga 7, si ottengono le seguenti matrici:

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

Questa matrice è "complementare" a quella del primo grafo, che infatti non presenta cicli.

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

Questa seconda matrice ha in comune con la seconda matrice di adiacenza i tre archi ((1, 2), (2, 3), (3, 1)) che costituiscono il ciclo.