Graphes et matrices

Exemples de matrices associées aux graphes

On trouve les matrices dans des applications particulièrement variées. Dame Nature a doté ces bestioles-là d’une telle faculté d’adaptation qu’elles prolifèrent dans les algorithmes de toute sorte.

À travers trois exemples, nous allons voir le lien qui existe entre graphes et matrices.

Il s'agit de matrices d'adjacence aux graphes, c'est-à-dire de matrices carrées dont chaque terme indique si tel sommet (en ligne) est relié à tel autre (en colonne). S'ils ne le sont pas, le coefficient situé à la croisée des deux sommets est nul. Sinon, ce coefficient est de 1 si le graphe est non pondéré et s'il l'est, le coefficient est la pondération. La matrice d'adjacence d'un graphe non orienté est symétrique. Lorsque le graphe est orienté, les origines des arcs sont en ligne tandis que leurs extrémités sont en colonnes (voir l'exemple 2).

Exemple 1 : graphe non orienté

non orienté

Il existe quatre sommets. On représente donc ce graphe par une matrice 4 × 4.

Comme le graphe n’est pas orienté, la matrice est symétrique, c'est-à-dire que la diagonale agit comme un miroir entre le nord-est et le sud-ouest. Ainsi, le point A (1re ligne) est lié à C et à D (3ème et 4èmecolonne) mais la réciproque est vraie aussi. Une liaison vaut 1 et une absence de liaison vaut 0. Une matrice qui n’est pas assez riche pour posséder autre chose que des 1 et des 0 est dite « booléenne »…

Pour être plus clair, écrivons la matrice associée :

matrice

Les lettres ne sont là que pour expliciter les liens. Nous nous en passerons désormais.

Puissance n d’une matrice

Vous vous en doutiez, il s’agit de la multiplication d’une matrice par elle-même n fois. Nous allons voir que les chaînes de longueur n nous sont données par la matrice élevée à la puissance n.

Exemple 2 : graphe orienté non pondéré

Dans la mesure où un graphe est orienté, la matrice qui lui est associée est rarement symétrique.

Le graphe suivant représente les chemins qu’il est possible d’emprunter entre quatre maisons A, B, C et D. Les voies qui les relient sont pour la plupart à sens unique. Déterminons le nombre de parcours possibles entre deux maisons, puis trois, puis quatre.

orienté

En lignes figurent les points de départ et en colonne les points d’arrivée.

matrice 1

Entre trois maisons : il suffit d’élever la matrice au carré.

matrice 2

Que signifie ceci ? Sur la première ligne, on ne relève qu’un 1 et c’est celui de la maison D. Il y a donc une chaîne de longueur 2 qui part de A et qui arrive à D (on voit que c’est A-B-D). Un 2 fait son apparition sur cette matrice. Il existe deux chaînes de longueur 2 qui partent de C et qui parviennent à B (C-A-B et C-D-B). Et ainsi de suite. Passons à la puissance 3 (chaînes entre quatre maisons). La matrice est encore différente…

matrice 3

Ces matrices ont été calculées avec une TI-82 (version anglaise) : touche MATRX, puis déplacement du curseur sur EDIT. ENTER. Saisie de la dimension de la matrice d’origine puis de ses valeurs. Touche MATRX pour revenir au menu. Le curseur étant positionné sur le nom de la bonne matrice, ENTER pour que seul le nom de la matrice figure sur l’écran (probablement [A]). Ensuite, x² pour une élévation au carré ou utilisation de la touche ^ (puissance).

Exemple 3 : graphe orienté pondéré

Dans certaines problématiques, les arcs n'ont pas tous le même poids. Un graphe orienté et pondéré par des probabilités est dit « probabiliste ». Il permet de visualiser un processus stochastique. Un exemple figure en page graphes probabilistes (rappel des principes et extrait d'une épreuve de bac). Mais tout graphe pondéré n'est pas probabiliste (voir la page algorithme de Dijkstra).

Pourquoi un graphe probabiliste ? L'intérêt pratique est celui d'étudier le passage d'un état à un autre dans un contexte d'incertitude. À partir d'un état initial, on simule ainsi des états successifs, éventuellement en se projetant sur l'infini. Par exemple, on extrapole les proportions de citadins et de ruraux en Europe sachant qu'il existe aussi bien un exode rural qu'un retour à la campagne. Si aucun facteur exogène ne vient gripper cette belle mécanique, les états vont évoluer de façon prévisible pour peut-être atteindre, à long terme des proportions stables. Ce type d'exercice est une initiation aux chaînes de Markov.

Pour effectuer les calculs, on recourt aux matrices ou aux suites. Après avoir reporté les probabilités dans une matrice carrée, on peut connaître l'état après n périodes. Il suffit pour cela d’élever la matrice de transition à la puissance n. Sous certaines conditions, après une certaine valeur de n, la matrice ne bouge plus.

Illustration : un panel de consommateurs est partagé en trois catégories en fonction d’une appétence pour un produit. On trouve de gros consommateurs (G), des occasionnels (O) et des réfractaires (R). Un an plus tard, on mesure leur probabilité d’appartenir à telle catégorie en fonction de leur profil en début de période. On obtient ce graphe, avec sa matrice de transition :

graphe probabiliste

Élevons cette matrice à la puissance 5, ce qui permet d’estimer les modifications d’appétence des consommateurs cinq ans après l’état initial si l'on fait l'hypothèse que les probabilités restent les mêmes.

matrice de l'état stable

On peut s’amuser à « augmenter la puissance ». On remarque alors que cet état est stable puisque la matrice ne bouge plus. Il est ainsi possible d’établir des prévisions à moyen terme mais aussi de modifier légèrement l’état initial afin de savoir quel type de consommateur il est d'ores et déjà préférable de cibler par des campagnes publicitaires.

Voir aussi la page d'exercice sur graphe non orienté.

 

matrices et graphes