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

Posté par clicli clicli

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 1emeu 1emeu

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 clicli clicli

Bonjour,

Merci pour cette belle démonstration.

On pouvait utiliser la même technique en remarquant toutefois que où E est l'ensemble des arcs de notre graphe!

Mais ça revient un peu au même!