Matrices et graphes

Choisir un ordre pour les sommets permet de coder toutes les liaisons dans une matrice d’adjacence. Pour un graphe simple non orienté de sommets A, B et C, rangés dans cet ordre, le coefficient de ligne i et de colonne j vaut 1 si les sommets correspondants sont adjacents et 0 sinon. La matrice est carrée, d’ordre égal au nombre de sommets. L’ordre choisi doit rester le même pendant tous les calculs.

La matrice d’un graphe non orienté est symétrique : la liaison de i vers j existe exactement lorsque celle de j vers i existe. Pour un graphe simple sans boucle, sa diagonale est nulle. La somme des coefficients d’une ligne est le degré du sommet associé. Changer l’ordre des sommets change le tableau des coefficients ; cela ne change pas le réseau décrit, mais interdit de comparer les coefficients sans retrouver leurs sommets.

Pour un graphe orienté, le coefficient de ligne i et de colonne j indique l’existence d’un arc allant de i vers j. La matrice n’est donc pas forcément symétrique. La somme d’une ligne donne le nombre d’arcs sortants et celle d’une colonne le nombre d’arcs entrants. Dans les exemples sans arcs multiples, les coefficients valent 0 ou 1. Une boucle, si le modèle l’autorise, correspond à un coefficient diagonal non nul.

Soit M une matrice d’adjacence. Le coefficient (i ; j) de M² est la somme des produits mᵢₖmₖⱼ lorsque k parcourt tous les sommets. Un produit vaut 1 exactement lorsqu’il existe une liaison de i à k, puis une liaison de k à j. Chaque choix de k donne une manière de relier i à j en deux étapes. La somme compte donc les chemins de longueur 2, en respectant le sens des arcs lorsque le graphe est orienté.

Ici, les chemins comptés peuvent repasser par un sommet ou une liaison. On compte des successions d’arêtes ou d’arcs, parfois appelées marches, sans imposer la simplicité du trajet. Si un problème interdit toute répétition, les puissances de la matrice d’adjacence ne donnent pas directement le nombre recherché. Il faut alors ajouter une analyse des contraintes. La longueur est toujours le nombre de liaisons parcourues, pas une distance géographique.

Pour tout entier naturel n, le coefficient (i ; j) de Mⁿ compte les chemins de longueur n allant de i à j. Au rang zéro, on pose M⁰ = I : il existe un chemin sans déplacement d’un sommet vers lui-même, et aucun vers un autre sommet. Au rang 1, la propriété est exactement la définition de la matrice d’adjacence.

Supposons le résultat vrai au rang n. Un chemin de longueur n + 1 allant de i à j possède un unique avant-dernier sommet k. Sa première portion est un chemin de longueur n de i à k ; sa dernière liaison va de k à j. Pour un k donné, le nombre de possibilités est (Mⁿ)ᵢₖmₖⱼ. Additionner sur tous les k donne le coefficient (i ; j) de MⁿM. La récurrence établit la propriété pour toutes les longueurs.

Le comptage ne double pas les chemins : leurs avant-derniers sommets sont différents lorsque les classes diffèrent. Il ne les oublie pas non plus : tout chemin possède un avant-dernier sommet. Ces deux remarques justifient la somme. Elles sont plus importantes que la simple récitation de la formule, car elles expliquent pourquoi un produit matriciel est adapté à un problème de successions.

Le calcul matriciel ne sert pas seulement à compter des chemins. Une suite de colonnes Uₙ peut décrire plusieurs quantités évoluant ensemble. Une relation Uₙ₊₁ = AUₙ donne Uₙ = AⁿU₀, par récurrence. Si une contribution fixe C s’ajoute à chaque étape, la relation devient Uₙ₊₁ = AUₙ + C. Il faut alors conserver ce terme ; utiliser seulement AⁿU₀ donnerait une évolution différente.

Pour une récurrence affine, on peut rechercher une colonne fixe L telle que L = AL + C. Si elle existe, poser Vₙ = Uₙ − L donne Vₙ₊₁ = AVₙ, donc Uₙ = L + Aⁿ(U₀ − L). L’existence de L doit être vérifiée ; elle n’est pas automatique. Une autre possibilité consiste à ajouter une coordonnée constante égale à 1 pour transformer l’évolution affine en produit d’une matrice de plus grande taille.

Dans cet exemple, ajouter la coordonnée 1 conduit à Wₙ₊₁ = BWₙ, avec Wₙ la colonne (uₙ ; vₙ ; 1) et B = (1, 1, 1 ; 0, 1, 2 ; 0, 0, 1). La dernière ligne conserve la coordonnée constante. On peut donc utiliser BⁿW₀ pour calculer les termes. Cette matrice n’est pas une matrice d’adjacence ni une matrice de probabilités : son interprétation vient des relations qu’elle code.

Erreurs fréquentes : lire un coefficient de M au lieu de Mⁿ ; croire que Mⁿ interdit les retours ; confondre exactement n et au plus n ; mélanger matrice d’adjacence et matrice d’évolution. Les coefficients d’une matrice n’ont pas un sens universel : ils prennent leur signification dans le modèle choisi. Ouvre S’entraîner dans /exercices pour travailler cette traduction entre situation, tableau et calcul.