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 l1 ³ l2 ³ ... ln les valeurs
propres de cette matrice.
-
Pourquoi M est-elle diagonalisable ?
- Montrer que l1 = 0.
- Montrer que le nombre de composantes connexes du graphe
est n moins le rang de cette matrice.
- Quelle est la complexité d'un algorithme qui utiliserait
cette propriété pour calculer le nombre de composantes connexes ?
Commenter...
- Que représentent tXMX et tXMY
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 l = - l2.
Pour XÌ V, on note d(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 £ |V(X)\ X|/|X|.
-
Montrer que d(X) ³ l |X|(1-|X|/n).
- Montrer que si X et Y sont des parties disjointes de V
avec r>1 la distance entre X et Y, on a
|Y|/n(1+r2l|X|/dn)
£ 1-|X|/n.
- En déduire que tout graphe est d'expansion
(n,d,2l/d+2l).
- Soit y un vecteur propre associé à l
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 l ³ S(i,j)Î E(xi-xj)2
/SiÎ Vxi2.
- 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
a(i,j) de ce flot, sur l'arête (i,j).
Montrer que l ³ (S(i,j)Î E
a(i,j)|xi2-xj2|)2
/SiÎ Vxi2
S(i,j)Î Ea(i,j)2(xi+xj)2.
En déduire que pour un graphe d'expansion (n,d,c) on a
l ³ c2/4+2c2.
This document was translated from LATEX by HEVEA.