Graphes et algèbre (max,+).

Certains problèmes de graphes ont des liens forts avec les algèbre (min,+) ou (max,+), parfois appelées algèbres exotiques ou tropicales. Pour ces algèbres qui sont en fait des semi-anneaux où min (ou bien max) et + remplacent respectivement + et ×, une algèbre linéaire spécifique a été développée, avec notamment des applications aux réseaux de Petri, en évaluation de performances des réseaux et en automatique.

L'objectif de ce sujet est d'illustrer les liens entre ces algèbres et des problèmes de graphes. Les points suivants proposent des pistes :

• Illustrer le fait que certains problèmes de graphes se traduisent bien en termes d'algèbre linéaire (min,+) ou (max,+). Donner par exemple le lien entre le calculs des plus courts chemins entre tous les sommets et les puissances de matrices en (min,+) (dans la multiplication de matrices en (min,+), on remplace dans la formule classique de multiplication les + et × par respectivement min et +, on conserve l'associativité de la multiplication de matrices).
• Illustrer le fait que l'étude de l'algèbre (min,+) ou (max,+) utilise la théorie et l'algorithmique des graphes. Par exemple, un théorème fondamental donne le comportement asymptotique des puissances d'une matrice dans l'algèbre (min,+). Dans l'algèbre classique (+,×), quand k tend vers +∞, les puissances M^k font ressortir les valeurs propres de M, notamment la plus grande en module. Dans l'algèbre (min,+), à toute matrice M de taille n × n à valeurs dans R ∪ {+∞}, on associe un graphe orienté et pondéré G(M) sur V={1,...,n} avec un arc de poids M[i,j] entre i et j, uniquement si M[i,j] ≠ +∞. La matrice est dite irréductible si G(M) est fortement connexe. On a le résultat suivant :
• Théorème fondamental des matrices itérées : dans l'algèbre (min,+), soit M une matrice irréductible, alors elle admet une unique valeur propre λ qui est le poids moyen minimum d'un circuit (poids moyen = somme de poids / longueur du circuit). De plus il existe deux entiers K et c tels que ∀ k≥K, M^k+c = M^k + cλ.
• Pour utiliser ce théorème en pratique, présenter au moins un algorithme polynomial de calcul de λ à partir de G(M), par exemple celui de Karp.
• L'entier c est parfois appelé cyclicité ou période. Considérer le graphe G_c(M) des circuits critiques de G(M) : c'est le graphe partiel de G(M) où seuls sont conservés les arcs appartenant à un circuit de poids moyen λ. La cyclicité de G_c(M) est le ppcm des cyclicités de ses composantes fortement connexes. La cyclicité d'une composante fortement connexe de G_c(M) est le pgcd des longueurs de tous ses circuits. On est donc ramener à un problème de graphe orienté : calculer le pgcd des longueurs de tous les circuits d'un graphe fortement connexe. Proposer au moins un algorithme polynomial pour résoudre ce problème (vous pouvez en imaginer un en vous basant sur un DFS, ou présenter celui suggéré dans le livre Digraphs de Bang-Jensen et Gutin).
• Donner éventuellement des exemples d'application de ce théorème fondamental des matrices itérées, ou d'autres applications en lien avec les algèbres (min,+) ou (max,+) et les graphes.
  

Quelques références (pas exhaustif).

• Introduction to Algorithms, livre de T. Cormen, C. Leiserson, R. Rivest (et C. Stein dans la dernière édition), MIT Press (2001) (traduit en français: Introduction à l'algorithmique, chez Dunod). Une section traite du problème des plus courts chemins et l'algorithme de Karp de calcul de λ, poids moyen minimum d'un circuit, est donné en exercice (voir l'index).
• Digraphs: theory, algorithms and applications, livre de J. Bang-Jensen et G. Gutin, Springer (2002). La cyclicité c est appelée période et deux algorithmes de calcul sont mentionnés page 567. Le premier se réfère au théorème 10.5.1 et à l'exercice 10.25. L'autre s'appuyant sur un DFS correspond à la question posée dans les points au-dessus. Il est ici attribué à Knuth, à d'autres endroits il est parfois associé à Denardo.
  
• Synchronization and Linearity, un livre online de F. Baccelli, G; Cohen, G. Olsder et J.-P. Quadrat, Wiley (1992). Pour ceux qui souhaitent une preuve du théorème fondamental des matrices itérées, allez en section 3.7.4, page 148.
• L'algèbre des sandwichs, article de  G. Cohen, S. Gaubert, and J.P. Quadrat dans Pour la Science, pages 56--63, Février 2005. Présentation des algèbres (max,+) et (min,+) avec des exemples d'utilisation.
  

 

Retour à la page des sujets.