Algorithmique et programmation Travaux dirigés, 11 et 17 janvier 2000 Louis Granboulan

Le but de cette séance est d’étudier la signification des valeurs propres de la matrice d’adjacence. La première partie montre qu’elles sont toutes de même signe et que le rang exprime le nombre de composantes connexes. La seconde partie montre que la plus proche de 0 mesure la capacité d’expansion du graphe.

1 Matrice d’adjacence

Un graphe simple non orienté (V, E) à n sommets peut être représenté par une matrice d’adjacence M. C’est une matrice carrée de dimension n, les éléments non diagonaux valent 1 ou 0 selon l’existence on non d’une arête. Les éléments diagonaux sont choisis de telle sorte que la somme de chaque ligne soit nulle. On note λ_{1} ⩾ λ_{2} ⩾ ...λ_{n} les valeurs propres de cette matrice.

1. Pourquoi M est-elle diagonalisable ?

2. Montrer que λ_{1} = 0.

3. Montrer que le nombre de composantes connexes du graphe est n moins le rang de cette matrice.

4. Quelle est la complexité d’un algorithme qui utiliserait cette propriété pour calculer le nombre de composantes connexes ? Commenter...

5. Que représentent ^{t}XMX et ^{t}XMY lorsque X et Y sont les vecteurs caractéristiques de deux parties disjointes de V ?

2 Graphes d’expansion

On suppose le graphe connexe et on note λ = −λ_{2}. Pour X ⊂ V, on note δ(X) le nombre d’arêtes adjacentes à un sommet de X et à un sommet de V \X. On note V (X) l’ensemble des sommets adjacents à au moins un sommet de X. Un graphe d’expansion (n, d, c) est un graphe non orienté à n sommets de degré maximal d tel que pour tout X ⊂ V avec |X| ⩽ n/2, on a c ⩽ \frac{|V (X)\X|}{|X|}.

1. Montrer que δ(X) ⩾ λ|X|(1 − \frac{|X|}{n}).

2. Montrer que si X et Y sont des parties disjointes de V avec ρ > 1 la distance entre X et Y, on a \frac{|Y |}{n}(1 + ρ^{2} \frac{λ|X|}{dn}) ⩽ 1 − \frac{|X|}{n}.

3. En déduire que tout graphe est d’expansion (n, d, \frac{2λ}{d+2λ}).

4. Soit y un vecteur propre associé à λ ayant moins de coordonnées positives que négatives. Notons X l’ensemble des sommets correspondant aux coordonnées positives et x le vecteur qui s’obtient à partir de y en remplaçant les coordonnées négatives par des 0. Montrer que λ ⩾ \frac{Σ_{(i,j)∈E}(x_{i}−x_{j})^{2}}{Σ_{i∈V} x_{i}^{2}} .

5. Construisons G′ à partir de G en rajoutant deux sommets s et t, des arêtes de s vers les sommets de X et des arêtes des sommets de V vers t. Toutes les arêtes ont capacité 1 sauf les arêtes issues de s qui ont capacité 1 + c. Le flot maximal de s à t sur G′ est de capacité (1 + c)|X|. On considère les coefficients α_{(i,j)} de ce flot, sur l’arête (i, j).

Montrer que λ ⩾ ^{\frac{(Σ_{(i,j)∈E}α_{(i,j)}|x_{i}^{2}−x_{j}^{2}|)^{2}}{Σ_{i∈V} x_{i}^{2}}} Σ_{(i,j)∈E}α_{(i,j)}^{2}(x_{i} + x_{j})^{2}.

En déduire que pour un graphe d’expansion (n, d, c) on a λ ⩾ \frac{c^{2}}{4+2c^{2}} .