Calcul matriciel

Rappels sur le calcul matriciel et booléen

Addition de matrices

[0150]+ [1203] = [1353]
[1210] [0024] [1234]

Multiplication de matrices

Calcul booléen
le + correspond au "OU"
0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 1

pour les produits : le * correspond au "ET"
0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
1 * 1 = 1
le 0 = Faux
le 1 = Vrai

Théorie des graphes : matrice d’un graphe

Matrice d’incidence ou matrice d’incidence sommet-arc ou sommet-arête
Si on a un graphe orienté G=(X, U) comportant n sommets et m arcs, on appelle matrice d’incidence sommet-arc la matrice M de dimension n x m avec :
Mij = 1 si xi est l’extrémité initiale de l’arc j
Mij = -1 si xi est l’extrémité terminale de l’arc j
Mij = 0 si xi n’est pas une extrémité de l’arc j
Pour un graphe non orienté, il n’y a pas de –1, juste des 1.

On numérote les arcs comme on veut. La matrice fait 8 sur 5 avec en abscisse les arcs et en ordonnée les sommets. C’est aussi une matrice binaire.

Connexité
Un graphe G=(X,U) est connexe si pour tout couple de sommets (x,y) il existe une chaîne joignant x à y. Trivialement, ça signifie qu’il tient en un seul morceau. Si G est divisé en trois morceaux, ces morceaux sont des sous-graphes connexes de G, qu’on appelle les composantes connexes du graphe. Le nombre de connexités est noté p.

Chemin de longueur k
On appelle longueur d’un chemin, entre deux sommets, i et j, sur un graphe G=(X,U), le nombre d’arcs existant entre ces deux sommets. Un chemin est de longueur, k, s’il comprend k arcs et (k+1) sommets. Un sommet seul, détermine un chemin de longueur 0.

Soit un graphe G=(X,U),
M la matrice d’incidence sommets-sommets,
Mk : le produit matriciel booléen de M par elle même k fois.

La présence d’un 1 sur Mk représente au moins un chemin entre i et j. Sur la matrice à la puissance p, un 1 sur xij indique l’existence d’un chemin de longueur p entre i et j. Si on calculait de façon non booléenne, on aurait aussi le nombre de chemins.
Ex : sur M2 booléenne, un 1 entre A et B indique l’existence d’un ou plusieurs chemins de longueur 2 entre A et B, comme par exemple le chemin AD DB.

On s’arrête à la matrice à la puissance trois car on a quatre sommets. On a alors la présence de chemins entre deux sommets, quels que soient leur longueur.

Fermeture transitive d’un graphe
Un graphe est transitif si, quels que soient deux arcs adjacents, a1 (x, y) et a2 (y, z) appartenant à A, alors l’arc a3 (x, z) appartient également à A.
On appelle fermeture transitive d’un graphe la liste des chemins établis à partir de la propriété de transitivité.

La fermeture transitive s’obtient en faisant la somme booléenne de la matrice unité ou identité ou I ou [1] (matrice carrée avec des 1 sur la diagonale et des 0 partout ailleurs) et des puissances successives de la matrice d’adjacence sommets-sommets, M. On s’arrête à la matrice de puissance k-1, nombre de sommets –1.
Pour faire la fermeture transitive du graphe, on va ajouter tous les arcs qui n’existent pas selon la règle de transitivité.

Exemple : on a ajouté les arcs en rouge

La matrice représente tous les chemins existant entre toute paire de sommets xi,xj, plus les boucles réflexives et les chemins rajoutés pour la fermeture transitive.

Algorithme de Roy-Warshall
Etant donné un graphe, G=(X,U) de n sommets, déterminez la fermeture transitive de G.
Appelons M la matrice binaire associée à G.
On rend G réflexif par ajout d’une boucle en chaque sommet n’en comportant pas.
On vérifie d’abord que pour tous arcs (i,r) et (r,j), on a bien un arc (i,j). Sinon, on l’ajoute.

On fait de même avec les ensembles de trois arcs, quatre arcs et ainsi de suite.