Techniques et concepts de l'entreprise, de la finance et de l'économie 
(et fondements mathématiques)

Graphes et matrices

logo

 

 

 

 

 

 

 

 

 

 

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.

Exemple 1 : graphe non orienté

non orienté

Il existe quatre sommets. On utilise donc une matrice carrée 4 × 4 pour avoir une vision algébrique des choses. Si 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 4e colonne) 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ù le graphe est orienté, la matrice qui lui est associée n’est pas forcément symétrique. Voyons ceci.

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. Il s’agit de déterminer 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é

Un graphe orienté et pondéré par des probabilités est dit « probabiliste ». Il permet de visualiser un processus stochastique.

La matrice associée à ce graphe est dite de transition. La somme de chacune de ses lignes est égale à 1 puisque, là encore, les états de départ figurent en ligne et ceux d'arrivée sont présentés en colonnes.

Pourquoi un graphe probabiliste ? Rendez-vous en page chaînes de Markov. À partir d'un état initial, on voit comment les probabilités de passage d'un état à un autre évoluent. 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 probabilités vont évoluer (la probabilité qu'un individu tiré au hasard soit citadin ou rural n'est pas tout fait la même d'une année sur l'autre).

Il est possible de modéliser l’évolution de 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 un certain nombre d’itérations, la matrice ne bouge plus. Elle représente alors l’état stable du graphe. La réalité peut être décrite par un processus stationnaire.

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.

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 quelle population il est d'ores et déjà préférable de cibler par des campagnes publicitaires.

 

matrices et graphes

 

© JY Baudot - Droits d'auteur protégés