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.
  1. Pourquoi M est-elle diagonalisable ?
  2. Montrer que l1 = 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 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|.
  1. Montrer que d(X) ³ l |X|(1-|X|/n).
  2. 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.
  3. En déduire que tout graphe est d'expansion (n,d,2l/d+2l).
  4. 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.
  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 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.