L’algorithme de Kosaraju décrit ci-dessous permet de rechercher les composantes fortement connexes (CFC) d’un graphe orienté.
Exécutez cet algorithme sur le graphe ci-dessous en détaillant les étapes de la résolution.
Pour nous convaincre de la correction de cet algorithme, nous introduisons le graphe des composantes fortement connexes $g^{cfc}=(S^{cfc}, A^{cfc})$ tel que $S^{cfc}$ est une partition de $S$ telle que :
$$A^{cfc} = \{ (cfc_i, cfc_j) \in S^{cfc} \times S^{cfc} \mid \exists{\lang s_1, …, s_k \rang} \text{ tel que } s_1 \in cfc_i, s_k \in cfc_j \}$$
Ce graphe peut-il avoir des circuits ? Dessinez $g^{cfc}$ pour le graphe précédent. Montrez qu’après l’exécution de la ligne 3 de l’algorithme, pour tout $arc(cfc_i,cfc_j) \in A^{cfc}$, la plus grande valeur de $num$ de l’ensemble des sommets de $cfc_i$ est supérieure à la plus grande valeur de $num$ de l’ensemble des sommets de $cfc_j$. Autrement dit, $$max\{num[s_i]|s_i \in cfc_i\} > max\{num[s_j]|s_j \in cfc_j\}$$
En déduire des propriétés sur les couleurs des sommets au moment de l’appel à $DFS_{rec}(g^t, s_i)$(ligne 9 de l’algorithme) :
En déduire que l’algorithme est correct.
// Loading
$$ Blancs = \{A, B, C, D, E, F, G, H, I\} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ A, B, C, D, E, G, H, I \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ A, B, C, D, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ A, B, C, D, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ A, B, C, D, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ A, B, C, D, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ A, B, C, D, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ B, C, D, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ C, D, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ C, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ C, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ C, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ C, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ C, E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ E, G, H \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ E, G \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ E \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ E \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ E \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ E \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ E \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
// Loading
$$ Blancs = \{ \} $$
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| Ordre $DFS_{num}$ | 7 | 1 | 5 | 6 | 2 | 9 | 3 | 4 | 8 |
Le graphe $G^{cfc}$ peut-il avoir des circuits ?
Ce graphe des SCC est un DAG. En effet, s’il existait un circuit alors, tous les sommets des SCC du circuit devraient appartenir à une même SCC. Sur notre exemple, le DAG des SCC comporte 4 sommets et 4 arcs :
$$ S^{SCC} = \{ scc_1 = \{ a, b, c, d \}, scc_2 = \{ g, h \}, scc_3 = \{ f, i \}, scc_4 = \{ e \} \} $$ $$ A^{SCC} = \{ (scc_1, scc_2), (scc_2, scc_4), (scc_3, scc_2), (scc_3, scc4) \} $$
Montrez qu’après l’exécution de la ligne 3 de l’algorithme, pour tout $arc(cfc_i,cfc_j) \in A^{cfc}$, la plus grande valeur de $num$ de l’ensemble des sommets de $cfc_i$ est supérieure à la plus grande valeur de $num$ de l’ensemble des sommets de $cfc_j$. Autrement dit, $$max\{num[s_i]|s_i \in cfc_i\} > max\{num[s_j]|s_j \in cfc_j\}$$
Montrez qu’après l’exécution de la ligne 3 de l’algorithme, pour tout $arc(cfc_i,cfc_j) \in A^{cfc}$, la plus grande valeur de $num$ de l’ensemble des sommets de $cfc_i$ est supérieure à la plus grande valeur de $num$ de l’ensemble des sommets de $cfc_j$. Autrement dit, $$max\{num[s_i]|s_i \in cfc_i\} > max\{num[s_j]|s_j \in cfc_j\}$$
Soit $s_0$ le premier sommet de $scc_i \cup scc_j$ qui est colorié en gris.
Montrez qu’après l’exécution de la ligne 3 de l’algorithme, pour tout $arc(cfc_i,cfc_j) \in A^{cfc}$, la plus grande valeur de $num$ de l’ensemble des sommets de $cfc_i$ est supérieure à la plus grande valeur de $num$ de l’ensemble des sommets de $cfc_j$. Autrement dit, $$max\{num[s_i]|s_i \in cfc_i\} > max\{num[s_j]|s_j \in cfc_j\}$$
Soit $s_0$ le premier sommet de $scc_i \cup scc_j$ qui est colorié en gris.
C’est le cas par exemple pour l’arc $(scc_1,scc_2)$: le premier sommet à être découvert est $a$, qui a bien la plus grande valeur de num parmi tous les sommets de $scc_1 \cup scc_2$.
Montrez qu’après l’exécution de la ligne 3 de l’algorithme, pour tout $arc(cfc_i,cfc_j) \in A^{cfc}$, la plus grande valeur de $num$ de l’ensemble des sommets de $cfc_i$ est supérieure à la plus grande valeur de $num$ de l’ensemble des sommets de $cfc_j$. Autrement dit, $$max\{num[s_i]|s_i \in cfc_i\} > max\{num[s_j]|s_j \in cfc_j\}$$
Soit $s_0$ le premier sommet de $scc_i \cup scc_j$ qui est colorié en gris.
C’est le cas par exemple pour l’arc $(scc_1,scc_2)$: le premier sommet à être découvert est $a$, qui a bien la plus grande valeur de num parmi tous les sommets de $scc_1 \cup scc_2$.
C’est le cas par exemple pour l’arc $(scc_3,scc_4)$ : le premier sommet à être découvert est $e$, qui a une valeur de num égale à 2, et tous les sommets de $scc_3$ ont une valeur de num supérieure à 2.
Notons finalement que le graphe transposé $g^t$ a les mêmes SCC que $g$. Par conséquent, nous pouvons rechercher les SCC dans $g^t$. En triant les sommets par ordre de num décroissant, nous sommes sûrs que pour tout arc $(scc_i,scc_j) \in A^{scc}$, un sommet de $scc_i$ sera rencontré avant un sommet de $scc_j$. Le parcours en profondeur à partir de ce premier sommet $s_i$ de $scc_i$ (ligne 9 de l’algorithme 8) permettra de découvrir tous les sommets de $scc_i$ et uniquement les sommets de $scc_i$. En effet, à l’appel de $DFS_{rec}(g^t,s_i)$ :
— tous les sommets appartenant à une SCC $scc_j$ telle qu’il existe dans $g^t$ un chemin de $s_i$ vers un sommet de $scc_j$ seront noirs (car au moins un sommet de $scc_j$ aura été rencontré avant $s_i$ dans la boucle lignes 6 à 9) ;
— tous les sommets appartenant à $scc_i$ seront blancs car tous les appels précédents à $DFS_{rec}$ seront partis de sommets pour lesquels il n’existe pas de chemin jusque $s_i$.