Geek or not

Accueil du site > MOCA > Représentation matricielle d’un graphe

Aller à ...

OMFG

Informations

Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 18 mars 2006.
2560 personnes ont affiché cette page et sa popularité est de 11.

Pebkac

Mots clefs

I see dead pixels.

Outils

SYN

Représentation matricielle d’un graphe

Fermeture transitive d’un graphe

La fermeture transitive d’un graphe $G = <X, U>$ génère un graphe $G' = <X, U'>$ auquel on à rajouté des arcs reliant le sommet i au sommet j s’il existe un chemin reliant le sommet i au sommet j ou si $i = j$ .

Exemple

Soit le graphe orienté $G = <X, U>$ suivant :


Exemple de graphe orienté pour réaliser la fermeture transitive

Et $M$ sa matrice booléenne :

	1	2	3	4	5	6
1	0	1	0	0	1	0
2	0	0	1	0	0	0
3	0	0	0	1	0	0
4	0	0	0	0	0	1
5	0	1	1	0	0	1
6	0	0	0	0	0	0

La matrice booléenne $M'$ correspondant à la fermeture transitive du graphe G est :

	1	2	3	4	5	6
1	1	1	1	1	1	1
2	0	1	1	1	0	1
3	0	0	1	1	0	1
4	0	0	0	1	0	1
5	0	1	1	1	1	1
6	0	0	0	0	0	1

Cela signifie qu’à partir du sommet 1 on peut accéder aux sommets 2, 3, 4, 5 et 6 du graphe et qu’à partir du sommet 6 on ne peut accéder à aucun sommet du graphe.

Conclusion : La fermeture transitive d’un graphe permet de répondre à la question : "existe t’il un chemin de x à y pour tout couple de sommet $\left(x, y\right)$ du graphe ?"

Algorithme de Warshall

Warshall est parti de l’observation suivante :
S’il existe un moyen d’aller du sommet x vers le sommet y ET un moyen d’aller du sommet y vers le sommet z alors il existe un moyen d’aller du sommet x vers le sommet z.\\

Algorithme :

$M$ est la matrice booléenne du graphe $G$
$M'$ est la matrice booléenne du graphe $G'$
$N$ est le nombre de sommets



M' = M

Pour i allant de 1 à N faire

        M'[i][i] = 1

Fin Pour

Pour k allant de 1 à N faire

        Pour i allant de 1 à N faire

                Pour j allant de 1 à N faire

                        M'[i][j] = M'[i][j] OU (M'[i][k] ET M'[k][j])

                Fin Pour

        Fin Pour

Fin Pour

L’idée de l’algorithme est de déterminer les chemins passant par le sommet 1, le sommet 2, le sommet 3,... le sommet N. Ce qui se fait en calculant M pour $k=1$ , $k=2$ , ..., $k=N$ [1]br>

Méthode matricielle

Soit le graphe orienté $G = <X, U>$ suivant :

Voir la figure Exemple de graphe orienté pour réaliser la fermeture transitive

Et M sa matrice booléenne :

	1	2	3	4	5	6
1	0	1	0	0	1	0
2	0	0	1	0	0	0
3	0	0	0	1	0	0
4	0	0	0	0	0	1
5	0	1	1	0	0	1
6	0	0	0	0	0	0

On a vu précédemment qu’on pouvait élever la matrice M au carré, au cube, ..., à la puissance k pour déterminer le nombre de chemis de longueur 2, 3, ..., k.

On se propose ici d’élever la matrice M au carré, au cube, ..., à la puissance k en adoptant des lois de composition logique pour la multiplication et l’addition.

loi de multiplication logique ( ET ) : $\left( 1 \dot\times 1 = 1\right)$
loi d’addition logique ( OU ) : $\left( 1 \dot+ 1 = 1\right)$ ou encore $\left( 1 \dot+ 0 = 1\right)$

On note les matrices obtenues à partir des lois de composition $M^{[2]}$ , $M^{[3]}$ , $M^{[4]}$ pour les différencier des matrices booléennes calculées à partir des lois de composition usuelles. Ces matrices nous permettent de savoir s’il existe au moins un chemin de longueur 2, 3, ..., k dans le graphe.

Calcul de $M^{[2]}$

$M^{[2]}= M^{[1]} \dot\times M^{[1]} = M \dot\times M$

	1	2	3	4	5	6
1	0	1	1	0	0	1
2	0	0	0	1	0	0
3	0	0	0	0	0	1
4	0	0	0	0	0	0
5	0	0	1	0	0	0
6	0	0	0	0	0	0

La présence d’un 1 à l’intersection de la ligne i et de la colonne j de $M^{[k]}$ indique qu’il existe au moins un chemin de longueur k entre les sommets i et j

De la même façon on peut calculer les matrices $M^{[3]}$ , $M^{[4]}$ , $M^{[5]}$ et si l’on procède à la somme booléenne $P = M \dot+ M^{[2]} \dot+ M^{[3]} \dot+ M^{[4]} \dot+ M^{[5]}$ on obtient une matrice P dans laquelle la présence d’un 1 à l’intersection de la ligne i et de la colonne j indique qu’il existe au moins un chemin de longueur inférieure ou égale à 5 entre les sommets i et j.

	1	2	3	4	5	6
1	0	1	1	1	1	1
2	0	0	1	1	0	1
3	0	0	0	1	0	1
4	0	0	0	0	0	1
5	0	1	1	1	0	1
6	0	0	0	0	0	0

On s’aperçoit que la matrice P ne donne pas la fermeture transitive du graphe car elle n’est pas composée de 1 sur la diagonale, il faut donc rajouter à l’expression $P = M \dot+ M^{[2]} \dot+ M^{[3]} \dot+ M^{[4]} \dot+ M^{[5]}$ la matrice identité I composée de 1 sur la diagonale et de 0 partout ailleurs. On obtient donc l’expression suivante donnant la fermeture transitive :

$P = I \dot+ M \dot+ M^{[2]} \dot+ M^{[3]} \dot+ M^{[4]} \dot+ M^{[5]}$

	1	2	3	4	5	6
1	1	1	1	1	1	1
2	0	1	1	1	0	1
3	0	0	1	1	0	1
4	0	0	0	1	0	1
5	0	1	1	1	1	1
6	0	0	0	0	0	1

Plus généralement, dans un graphe de N sommets, la somme booléenne suivante donne la fermeture transitive du graphe :

$I \dot+ M \dot+ M^{[2]} \dot+ M^{[3]} \dot+ ... \dot+ M^{[N-1]} = \left(I \dot+ M\right)^{[N-1]}$

Faire l’exercice 7 Exercice 7

pages : << 1 2 3

[1] La matrice obtenue pour $k = N$ donne la fermeture transitive du graphe

Poster un message