Wednesday 26
Graphs, flows, combinatorial algorithms and approximation
Alexandre Salch
› 14:40 - 15:00 (20min)
› Bât B - TD 43
Noeuds mous d'un graphe
Arnaud Knippel  1@  , Jean-Guy Caputo  2@  , Elie Simo  3  
1 : Laboratoire de Mathématiques de l'INSA de Rouen  (LMI)  -  Website
Institut National des Sciences Appliquées [INSA] - Rouen : EA3226
2 : Laboratoire de Mathématiques de l'INSA de Rouen  (LMI)  -  Website
Institut National des Sciences Appliquées [INSA] - Rouen
3 : University of Yaounde

Nous nous plaçons dans le contexte de phénomènes physiques d'oscillation dans des réseaux (typiquement des réseaux électriques ou des systèmes mécaniques). Ces phénomènes sont modélisés par des systèmes d'équations différentielles associées à un graphe, et le comportement du système est lié à la matrice de Laplacien du graphe L=D-A (où D est une matrice diagonale des degrés et A est une matrice d'adjacence). Dans le cas de systèmes linéaires, on se ramène à étudier les valeurs propres et vecteurs propres de L. Lorsque les phénomènes étudiés ne sont pas linéaires, une approche consiste à projeter sur une base de vecteurs propres.

En fonction du graphe, il peut arriver qu'une composante d'un vecteur propre soit nulle : nous appelons noeud mou le sommet du graphe correspondant, car agir sur ce noeud n'a aucune influence sur le réseau pour le mode correspondant à la valeur propre en régime linéaire. Nous nous intéressons à la détection de tels noeuds. Calculer une valeur propre ne peut pas se faire de façon exacte dans tous les cas, et les résultats généraux existants sur les valeurs propres de graphes donnent généralement des bornes peu précises. Nous montrons qu'on peut déterminer certaines configurations précises de sous-graphes qui entraînent automatiquement la présence de noeuds mous pour des valeurs propres qui dépendent uniquement de ces sous-graphes.

 


Online user: 2