Algorithmique et programmation Travaux dirigés, 23 et 24 novembre 1998

Louis Granboulan

1 Parcours de graphes

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

(a) À quelle condition un graphe admet-il un circuit eulérien ?

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

2. 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.

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

(b) Proposer un algorithme pour calculer les composantes biconnexes à l’aide d’un parcous en profondeur.

3. 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. On appelle couplage une partie M ⊂ E telle que chaque sommet du graphe appartient à au plus une arête de M. Un couplage est dit maximal si son cardinal l’est. Un couplage est parfait si tous les sommets en font partie. Pour toute partie X ⊂ V, on note V (X) l’ensemble des sommets adjacents à au moins un sommet de X.

(a) Proposer un algorithme pour décider si un graphe est bipartite.

(b) Proposer un algorithme pour trouver un couplage maximal.

(c) Montrer le théorème de Hall : un graphe admet un couplage parfait si, et seulement si ∀X ⊂ V, |X| ⩾ |V (X)|.

2 Graphes d’expansion

Un graphe simple non orienté (V, E) peut être représenté par une matrice d’adjacence M où les éléments diagonaux sont choisis de telle sorte que la somme de chaque ligne soit nulle. On note λ_{1} ⩾ λ_{2} ⩾ ... les valeurs propres de cette matrice. Pour X ⊂ V, on note δ(X) le nombre d’arêtes adjacentes à un sommet de X et à un sommet de V \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. Matrice d’adjacence (a) Montrer que λ_{1} = 0.

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

(c) Que représente ^{t}XMY ?

2. Graphes d’expansion

(a) Supposons le graphe connexe. Montrer que δ(X) ⩾ −λ_{2}|X|(1 − \frac{|X|}{n}).

(b) 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 − \frac{λ_{2}|X|}{dn}ρ^{2}) ⩽ 1 − \frac{|X|}{n}.

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