Matrices et graphes

9.1 Matrice d'adjacence

Pour un graphe oriente a n sommets, la matrice d'adjacence M est une matrice n x n ou mᵢⱼ = 1 s'il existe un arc du sommet i vers le sommet j, et mᵢⱼ = 0 sinon.

Exemple :

Graphe a 3 sommets {A, B, C} avec les arcs : A vers B, A vers C, B vers C, C vers A.

     A  B  C
M = [ 0  1  1 ]   A
    [ 0  0  1 ]   B
    [ 1  0  0 ]   C

Lecture : m₁₂ = 1 signifie qu'il y a un arc de A vers B. m₂₁ = 0 signifie qu'il n'y a pas d'arc de B vers A.

Pour un graphe non oriente, la matrice est symetrique (mᵢⱼ = mⱼᵢ).

9.2 Nombre de chemins de longueur k

Propriete fondamentale : le coefficient (i, j) de la matrice Mᵏ donne le nombre de chemins de longueur k allant du sommet i au sommet j.

Exemple : nombre de chemins de longueur 2.

Avec la matrice M precedente, calculons M² = M x M :

c₁₁ = 0x0 + 1x0 + 1x1 = 0 + 0 + 1 = 1
c₁₂ = 0x1 + 1x0 + 1x0 = 0 + 0 + 0 = 0
c₁₃ = 0x1 + 1x1 + 1x0 = 0 + 1 + 0 = 1
c₂₁ = 0x0 + 0x0 + 1x1 = 0 + 0 + 1 = 1
c₂₂ = 0x1 + 0x0 + 1x0 = 0 + 0 + 0 = 0
c₂₃ = 0x1 + 0x1 + 1x0 = 0 + 0 + 0 = 0
c₃₁ = 1x0 + 0x0 + 0x1 = 0 + 0 + 0 = 0
c₃₂ = 1x1 + 0x0 + 0x0 = 1 + 0 + 0 = 1
c₃₃ = 1x1 + 0x1 + 0x0 = 1 + 0 + 0 = 1

M² = [ 1  0  1 ]
     [ 1  0  0 ]
     [ 0  1  1 ]

Interpretation :

• m²₁₁ = 1 : il existe 1 chemin de longueur 2 de A vers A (A -> C -> A).
• m²₁₃ = 1 : il existe 1 chemin de longueur 2 de A vers C (A -> B -> C).
• m²₃₂ = 1 : il existe 1 chemin de longueur 2 de C vers B (C -> A -> B).

Chemins de longueur 3 : calculons M³ = M² x M :

c₁₁ = 1x0 + 0x0 + 1x1 = 0 + 0 + 1 = 1
c₁₂ = 1x1 + 0x0 + 1x0 = 1 + 0 + 0 = 1
c₁₃ = 1x1 + 0x1 + 1x0 = 1 + 0 + 0 = 1
c₂₁ = 1x0 + 0x0 + 0x1 = 0 + 0 + 0 = 0
c₂₂ = 1x1 + 0x0 + 0x0 = 1 + 0 + 0 = 1
c₂₃ = 1x1 + 0x1 + 0x0 = 1 + 0 + 0 = 1
c₃₁ = 0x0 + 1x0 + 1x1 = 0 + 0 + 1 = 1
c₃₂ = 0x1 + 1x0 + 1x0 = 0 + 0 + 0 = 0
c₃₃ = 0x1 + 1x1 + 1x0 = 0 + 1 + 0 = 1

M³ = [ 1  1  1 ]
     [ 0  1  1 ]
     [ 1  0  1 ]

Interpretation : m³₁₂ = 1 signifie qu'il existe 1 chemin de longueur 3 de A vers B (par exemple A -> C -> A -> B).

9.3 Matrice de transition (chaines de Markov)

Dans une chaine de Markov, on associe a chaque graphe pondere une matrice de transition T ou tᵢⱼ est la probabilite de passer du sommet i au sommet j.

Propriete : la somme de chaque ligne vaut 1.

Exemple :

T = [ 0.3  0.7 ]
    [ 0.4  0.6 ]

Lecture : depuis l'etat 1, probabilite 0.3 de rester en 1 et 0.7 d'aller en 2.

Verification : 0.3 + 0.7 = 1 et 0.4 + 0.6 = 1.

Si la distribution initiale est P₀ = [1 0] (on est dans l'etat 1), la distribution apres 1 etape est :

P₁ = P₀ x T = [1  0] x [ 0.3  0.7 ] = [ 1 x 0.3 + 0 x 0.4,  1 x 0.7 + 0 x 0.6 ] = [ 0.3  0.7 ]
                        [ 0.4  0.6 ]

Apres 2 etapes : P₂ = P₁ x T.

P₂ = [0.3  0.7] x [ 0.3  0.7 ]
                   [ 0.4  0.6 ]

composante 1 : 0.3 x 0.3 + 0.7 x 0.4 = 0.09 + 0.28 = 0.37
composante 2 : 0.3 x 0.7 + 0.7 x 0.6 = 0.21 + 0.42 = 0.63

P₂ = [ 0.37  0.63 ]