Niveau autre

Théorie des Graphes - Analyse spectrale de la matrice de Laplace

Posté par
clicli 23-11-09 à 13:15

Bonjour à tous

Je cherche à démontrer que si la matrice laplacienne d'un graphe admet la valeur propre 0 à une multiplicité supérieure ou égale à 2, alors le graphe ne peut pas être connexe.

J'ai déjà réussi la réciproque, mais là je sèche un peu,

Merci de vos coups de main!

Posté par re : Théorie des Graphes - Analyse spectrale de la matrice de La 23-11-09 à 19:39

Bonjour,

je pense qu'une manière de faire est de dire que
(x1,...,xn) est un vecteur du noyau de la matrice laplacienne si et seulement si lorqu'on associe le poids xi au sommet i, le poids de chaque sommet du graphe est la moyenne des poids des sommets adjacents.

Ensuite on montre que dans un graphe connexe où les sommets ont des poids tels le poids d'un sommet est la moyenne des poids adjacents, les poids de chaque sommet sont nécessairement les memes (ceci correspond au vecteur (1,...1) du noyau de la laplacienne).
Pour cela suppose que deux sommets adjacents aient des poids différents a<b. Alors un voisin du sommet qui a pour poids a a néessairement un poids c<a. Puis par récurrence ce sommet a aussi un voisin qui a un poids d<c, etc... d'où une contradiction.

On a donc montré que pour un graphe connexe, le noyau de la laplacienne est exactement engendré par le vecteur (1,...,1). Ce même raisonnement permet également de montrer que le nombre de composantes connexes du graphe est exactement la dimension du noyau de la matrice laplacienne (et une base du noyau va meme donner explicitement les composantes connexes).

Il y a sûrement d'autres manières de faire...

à plus,
1emeu

Posté par re : Théorie des Graphes - Analyse spectrale 26-11-09 à 18:09

Bonjour,

Merci pour cette belle démonstration.

On pouvait utiliser la même technique en remarquant toutefois que $\displaystyle X^T AX=\sum_{i,j\in E~}(x_i -x_j)^2$ où E est l'ensemble des arcs de notre graphe!

Mais ça revient un peu au même!