Graphes et matrices

Un graphe est un ensemble de sommets reliés par des arêtes. Il modélise des relations du quotidien : amis sur un réseau social, villes reliées par des routes, pages web liées par des hyperliens. L'ordre d'un graphe est son nombre de sommets ; le degré d'un sommet est le nombre d'arêtes qui en partent. Une chaîne est une suite d'arêtes consécutives reliant des sommets.

Pour un graphe d'ordre n, on numérote les sommets de 1 à n. La matrice d'adjacence M est une matrice carrée n×n où le coefficient m_{ij} vaut 1 si les sommets i et j sont reliés par une arête, et 0 sinon. Pour un graphe non orienté, cette matrice est symétrique car la relation est réciproque. La somme des coefficients d'une ligne donne le degré du sommet correspondant.

En multipliant la matrice d'adjacence par elle-même, on obtient des informations sur les chaînes de longueur donnée. Le coefficient (i,j) de M^k est égal au nombre de chaînes de longueur k reliant le sommet i au sommet j. Par exemple, M^2 compte les chaînes de longueur 2, c'est-à-dire les chemins passant par exactement deux arêtes. Cette propriété permet de répondre à des questions concrètes : combien de trajets en deux étapes relient deux villes ?

Un graphe orienté possède des arcs avec un sens, comme des rues à sens unique ou des liens hypertextes. Sa matrice de transition T est carrée : le coefficient t_{ij} est la probabilité de passer du sommet j au sommet i en une étape. Si P_n est l'état probabiliste à l'étape n, alors P_{n+1} = T P_n. On peut ainsi modéliser l'évolution d'un système : météo, parts de marché, navigation sur un site.