\documentclass[a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage[francais]{babel}

\usepackage{hevea}
\ifhevea
\def\linewidth{}
\def\mathbb#1{\textbf{#1}}
\newenvironment{introduction}{\quotation\footnotesize}{\endquotation}
\newenvironment{intro}{\\\footnotesize}{}

\else

%% Parametres de mise en page
\topmargin -1.04cm
\headheight 0pt
\headsep 0pt
\marginparwidth 0mm
\oddsidemargin  -1.04cm
\evensidemargin -1.04cm
\textwidth 18cm
\textheight 25.7cm
\advance\textheight by \topskip
\parindent 0pt

\usepackage{amssymb}
\let\geq\geqslant
\let\leq\leqslant
\def\intro{\begin{center}\begin{minipage}{.9\linewidth}\small}
\def\endintro{\end{minipage}\end{center}}
\fi

\begin{document}
\twocolumn[
\begin{center}
\LARGE
Algorithmique et programmation

Travaux dirigés, 7 décembre 2001

\textbf{Graphes}
\end{center}\vspace*{1cm}]
\ifhevea
\begin{center}
\LARGE
Algorithmique et programmation

Travaux dirigés, 7 décembre 2001

\textbf{Graphes}
\end{center}
\fi

\section{Matrice d'adjacence}

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

\subsection{Rang de la matrice}
  \begin{intro}
  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 $\lambda_1 \geq \lambda_2 \geq ... \lambda_n$ les valeurs
  propres de cette matrice.
  \end{intro}
  \begin{enumerate}
    \item Pourquoi $M$ est-elle diagonalisable ?
    \item Montrer que $\lambda_1 = 0$.
    \item Montrer que le nombre de composantes connexes du graphe
          est $n$ moins le rang de cette matrice.
    \item Quelle est la complexité d'un algorithme qui utiliserait
          cette propriété pour calculer le nombre de composantes connexes ?
          Commenter...
    \item Que représentent ${}^tXMX$ et ${}^tXMY$
          lorsque $X$ et $Y$ sont les vecteurs
          caractéristiques de deux parties disjointes de $V$ ?
  \end{enumerate}

\subsection{Graphes d'expansion}
  \begin{intro}
  On suppose le graphe connexe et on note $\lambda = - \lambda_2$.
  Pour $X\subset V$, on note $\delta(X)$ le nombre d'arêtes adjacentes
  à un sommet de $X$ et à un sommet de $V\backslash X$.
  On note $V(X)$ l'ensemble des sommets adjacents à au moins un sommet de $X$.
  \par
  Un graphe d'expansion $(n,d,c)$ est un graphe non orienté
  à $n$ sommets de degré maximal $d$ tel que pour tout $X\subset V$
  avec $|X|\leq n/2$, on a $c \leq \frac{|V(X)\backslash X|}{|X|}$.
  \end{intro}
  \begin{enumerate}
    \item Montrer que $\delta(X) \geq \lambda |X|\big(1-\frac{|X|}n\big)$.
    \item Montrer que si $X$ et $Y$ sont des parties disjointes de $V$
          avec $\rho>1$ la distance entre $X$ et $Y$, on a
          $\frac{|Y|}n\big(1+\rho^2\frac{\lambda|X|}{dn}\big)
           \leq 1-\frac{|X|}n$.
    \item En déduire que tout graphe est d'expansion
          $(n,d,c)$ avec $c = \frac{2\lambda}{d+2\lambda}$.
  \end{enumerate}

\newpage

\section{Parcours de graphe}

\begin{enumerate}

\item{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.

  $\bullet$ Proposer un algorithme pour décider si un graphe est bipartite.

\item{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.

  $\bullet$ À quelle condition un graphe admet-il un circuit eulérien ?

  $\bullet$ Proposer un algorithme de complexité ${\cal O}(E)$
  pour trouver un tel circuit s'il existe.

\item{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 $\sim$ 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.

  $\bullet$ Montrer que c'est une relation d'équivalence.

  On appelle {\em composantes biconnexes} les
  classes d'équivalence.

  $\bullet$ Proposer un algorithme pour calculer les composantes biconnexes
  à l'aide d'un parcours en profondeur.
  On détectera par exemple les {\em points d'articulation},
  qui séparent les composantes biconnexes.

\item{Diamètre}

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

  $\bullet$ Proposer un algorithme pour calculer le diamètre d'un graphe.

\end{enumerate}

\end{document}
