MATRICE D'ADJACENCE



THÉORIE DES GRAPHES

1. Matrice d'adjacence

2. Catégories

Au plan formel, un graphe est aussi un ensemble sur lequel nous avons défini une relation binaire, antiréflexive (aucun élément n'est en relation avec lui-même) et symétrique (si x est en relation avec y, alors y est en relation avec x). La structure de graphe peut alors sembler particulièrement pauvre.

Mais nous pouvons aussi associer à un graphe G de sommets equation une matrice carrée M de dimensions equation appelée "matrice d'adjacence" du graphe et dont les éléments valent 0 ou 1. En notant equation le terme située au croisement de la ligne i (représentant le sommet equation) et de la colonne j (représentant le sommet equation), M est défini par :

equation si et seulement si equation sont adjacents

De par cette définition et celle du graphe lui-même, il vient que dans une matrice d'adjacence d'un graphe formel que les éléments diagonaux pour lesquels equation valent tous 0 et que equation.

Rappelons qu'une telle matrice est dite "symétrique" (cf. chapitre d'Algèbre linéaire).

Remarque: Nous savons aussi que les graphes sont représentés par des matrices dans le cadre de l'étude des chaînes de Markov dans le domaine des probabilités (cf. chapitre de Probabilités)

Voyons un exemple à la fois abstrait mais facilement applicable à n'importe à de nombreux domaines de l'industrie, de la sociologie et de la biologie. Considérons le graphe orienté suivant et observons qu'il n'est pas antiréflexif ni symétrique:

equation
  (27.27)

Nous pouvons représenter ce diagramme sous forme d'un tableau dans lequel nous noterons "1" quand une transition est possible de l'état mentionné en haut de cette case vers celui mentionné au début de la ligne et "0" sinon:

equation

E1

E4

E2

E3

E5

E7

E6

E1

0

0

0

0

0

0

0

E4

0

0

1

0

0

0

0

E2

1

1

1

1

0

0

0

E3

0

0

1

0

0

0

0

E5

0

0

0

1

0

0

0

E7

0

1

1

1

0

0

0

E6

0

1

1

1

0

0

0

Tableau: 27.2  - Matrice d'adjacence

Il est indispensable de comprendre parfaitement la signification des valeurs se trouvant dans ce tableau! Mais à ce niveau du site cela ne devrait pas poser de difficulté majeure.

Maintenant évaluons le nombre de manières permettant d'aller:

1. De E2 vers E2 en deux étapes

2. De E3 vers E4 en deux étapes

3. De E2 vers E7 en deux étapes.

Il est facile dans le cas particulier ci-dessus de dénombrer ces possibilités. Mais dans le cas d'un graphe plus complexe cela devient difficile voir impossible pour un être humain dans un temps raisonnable.

Nous devons faire appel alors au théorème suivant:

Soit un graphe orienté avec equation sommet de matrice d'adjacence :

equation   (27.28)

Pour tout entier naturel k, alors le nombre de chemins de longueur k du sommet equation au sommet equation est donné par:

equation   (27.29)

où l'exposant sur M dénote la puissance de k de la matrice d'adjacence.

Démonstration:

Effectuons une récurrence sur k:

equation   (27.30)

désigne bien le nombre de chemins allant de equation à equation (où i et j peuvent être égaux). Supposons le résultat vrai pour l'entier k-1, avec equation comme:

equation   (27.31)

nous avons alors (par construction de la multiplication matricielle):

equation   (27.32)

Par hypothèse de récurrence, equation est le nombre de chemins de longueur k-1 allant de equation à equation et equation est nous le savons (par construction) le nombre de chemins de longueur 1 allant de equation à equation et en particulier il est égal à 1 si equation est une arête du Graphe et 0 sinon!

Donc le produit:

equation   (27.33)

donne pour une valeur de l donnée le nombre de chemins de longueur k allant de equation à equation dont la dernière arête est equation.

La somme:

equation   (27.34)

donne donc toutes les possibilités (chemins) de longueur k allant de equation à equation quelque soit le point de début de la dernière arête!

equationC.Q.F.D.

Ainsi, dans notre exemple, la matrice d'adjacence M est donnée par:

equation   (27.35)

est n'est ni symétrique, ni antiréflexive comme nous en avions déjà fait mention.

Donc si nous la mettons à la puissance k, chaque composant equationdonnera toutes les possibilités (chemins) de longueur k allant de equation à equation. Et nous avons:

equation   (27.36)

en utilisant par exemple la fonction PRODUITMAT( ).

Nous avons alors la réponse à nos trois questions en lisant la matrice ci-dessus:

1. De E2 vers E2 en deux étapes nous avons donc 3 possibilités.

2. De E3 vers E4 en deux étapes nous avons donc 1 possibilité.

3. De E2 vers E7 en deux étapes nous avons donc 3 possibilités.

Il est possible de gagner un peu de temps dans ce genre de calculs. Si nous notons equation, la i-ème colonne de la matrice M, alors:

equation   (27.37)

donnera la i-ème colonne de la matrice M au carré. Et ainsi de suite:

equation   (27.38)

Donc nous obtenons systématiquement le nombre de chemins de longueur k d'un point de départ donné correspondant à la colonne i.

Cet exemple à une autre approche très intéressante dans certains domaines étudiant le comportement d'individus dans diverses situations (achats, tourismes, accidents,...).

Si au lieu de noter dans la matrice M le nombre de chemins possibles d'un sommet à l'autre nous notons la probabilité (la partie) du nombre total d'individus qui partent de ce même sommet pour en arriver à un autre alors nous avons par exemple (valeurs imposées par l'expérience!) la matrice:

equation   (27.39)

qui est déjà la matrice stochastique transposée du graphe visible ci-dessous (conformément à la théorie des chaînes de Markov, nous avons vu qu'il fallait prendre la transposée de la matrice stochastique pour calculer les probabilités d'états).

En considérant que ces probabilités ne changent pas au cours du temps, nous avons alors une chaîne de Markov homogène (sans cycles). Nous voyons alors que:

1. La somme des probabilités de transitions au départ de chaque sommet (état) doit toujours logiquement être égale à 1 (ce que nous avions déjà mentionné dans le chapitre de Probabilités)

2. Tout le monde part de la première étape E1

3. Certains stagnent (s'arrêtent) à une certaine étape

4. Ceux qui arrivent à une étape de fin E5, E6 ou E7 y restent et ne reviennent pas sur leurs pas (états abosorbants).

Le graphe équivalent devient alors:

equation
  (27.40)

En appelant N (au lieu de M pour ne pas confondre) la matrice construite à partir du graphe ci-dessus nous voyons que si equation est une des colonnes de la matrice M alors par exemple:

equation   (27.41)

donne la somme des probabilités de transition que ce qui part de E1 arrive en 2 étapes en respectivement E1(0), E2(0.662), E3(0.218)... (la distribution du vecteur initial peut être quelconque tant que la sommes des valeurs de la colonne est égale à 1)!

Si nous multiplions ensuite encore une fois:

equation   (27.42)

donne la somme des probabilités de transition que ce qui part de E1 arrive en 3 étapes en respectivement E1(0), E2(0.691), ... et ainsi de suite. Nous pouvons ainsi savoir qu'elle est la probabilité qu'un individu arrivant à E2 puisse arriver à un des sommets terminaux (E5, E6 ou E7) en un nombre d'étapes donné.

Remarque: Se rappeler que la somme des probabilités des colonnes T obtenues est toujours égale à 1 pour la transposée de la matrice stochastique.

En continuant encore longtemps ainsi... nous trouvons que la mesure d'équilibre equation qui satisfait (cf. chapitre de Probabilités):

equation

est:

equation   (27.43)

quelque soit la distribution du vecteur de départ. Propriété que l'on appelle "ergodique" dans le domaine des chaînes de Markov.

Ce qui signifie 45% de probabilité de se trouver en E5, 32% de probabilité de se trouver en E7 et 23% de probabilité de se trouver en E6. Une autre manière de voir les choses est de dire que si une cohorte de 100 individus part de l'étape E1 avec les probabilités constantes dans le temps entres les transitions d'étapes, à l'équilibre nous aurons 45 personnes en E5, 32 personnes en E7 et 23 personnes en E6.


page suivante : 2. Catégories