Algorithmique et programmation Travaux dirigés, 12 et 13 décembre 2002 Graphes

1 Parcours de graphe

1. Graphes bipartites Un graphe non-orienté est dit bipartite si V se découpe en deux parties telles que toute arête relie un sommet dans chaque partie.

• Proposer un algorithme pour décider si un graphe est bipartite.

2. Circuits eulériens Un chemin d’un graphe orienté (V, E) est une suite d’arcs se succédant. Un circuit est un chemin fermé. Un circuit eulérien est un circuit qui parcourt chaque arc exactement une fois.

• À quelle condition un graphe admet-il un circuit eulérien ?

• Proposer un algorithme de complexité O(E) pour trouver un tel circuit s’il existe.

3. Composantes biconnexes Dans un graphe connexe non-orienté, on dit qu’un cycle est simple s’il ne passe pas deux fois par un même sommet. On définit une relation ∼ sur l’ensemble des arêtes, où deux arêtes sont en relation si elles peuvent être impliquées dans un même cycle simple.

• Montrer que c’est une relation d’équivalence. On appelle composantes biconnexes les classes d’équivalence.

• Proposer un algorithme pour calculer les composantes biconnexes à l’aide d’un parcours en profondeur. On détectera par exemple les points d’articulation, qui séparent les composantes biconnexes.

4. Diamètre Le diamêtre d’un graphe (connexe non-orienté) est la plus longue distance entre deux de ses sommets.

• Proposer un algorithme pour calculer le diamètre d’un graphe.

2 Matrice d’adjacence

Le but de cette section est de commencer une étude de la signification des valeurs propres de la matrice d’adjacence.

2.1 Rang de la matrice

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.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, c) avec c = \frac{2λ}{d+2λ}.