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 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.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,c) avec c = 2l/d+2l.
This document was translated from LATEX by HEVEA.