Algorithmique et programmation
Graphes
1 Parcours de graphe
- 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.
- 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.
- 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.
- 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.
-
Pourquoi M est-elle diagonalisable ?
- Montrer que λ1 = 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.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 ≤ |V(X)\ X|/|X|.
-
Montrer que δ(X) ≥ λ |X|(1-|X|/n).
- Montrer que si X et Y sont des parties disjointes de V
avec ρ>1 la distance entre X et Y, on a
|Y|/n(1+ρ2λ|X|/dn)
≤ 1-|X|/n.
- En déduire que tout graphe est d'expansion
(n,d,c) avec c = 2λ/d+2λ.
This document was translated from LATEX by
HEVEA.