Graphes et algèbres tropicales.

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 :

• Des algèbres tropicales pour les problèmes de graphes. 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 calcul 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).
• Des graphes pour les problèmes d'algèbres tropicales. 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. Le théorème dit de Perron-Frobenius est le suivant : 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 cycle (poids moyen = somme de poids / longueur du cycle) et il existe deux entiers K et c tels que ∀ k≥K, M^k+c= M^k+ cλ. L'entier c est parfois appelé cyclicité ou période, et admet une définition à partir de G(M). Considérer le graphe G_c(M) des cycles critiques de G(M) : c'est le graphe partiel de G(M) où seuls sont conservés les arcs appartenant à un cycle 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 cycles.
  Vous pouvez présenter une démonstration du théorème de Perron-Frobenius ou/et un algorithme polynomial pour calculer le poids moyen minimum λ (par exemple celui de Karp) et/ou un algorithme polynomial pour le pgcd des cycles d'un graphe fortement connexe (par exemple celui de Denardo ou celui de Balcer-Veinott).
• Applications. Donner éventuellement des exemples d'application du théorème de Perron-Frobenius, 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 cycle, 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 (algorithme de Balcer-Veinott). L'autre s'appuyant sur un DFS et attribué ici à Knuth, est plus souvent appelé algorithme de Denardo (il fonctionne à partir de n'importe quel arbre de parcours, cf TD MaxPlus Exercice 6).
• Introduction aux systèmes dynamiques à événements discrets, Notes de cours de S. Gaubert, ENSMP, Option Automatique et M2 ATSI, Université d'Orsay (1999). Excellent polycopié avec une démonstration du théorème de Perron-Frobenius en page 72 (Théorème 4.2.2.2), de nombreuses résultats annexes dans le chapitre 4 et de nombreux exemples d'applications.
• L'algèbre des sandwichs, article de G. Cohen, S. Gaubert et 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.