\documentclass[a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
%\usepackage{french}
\usepackage[francais]{babel}
\usepackage{version}
\includeversion{flots}

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

\def\ceil#1{\left\lceil #1\right\rceil}
\def\floor#1{\left\lfloor #1\right\rfloor}
\usepackage{amssymb}
\let\geq\geqslant
\let\leq\leqslant
\def\intro{\begin{center}\begin{minipage}{.9\linewidth}\small}
\def\endintro{\end{minipage}\end{center}}

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

Travaux dirigés, 23 et 24 novembre 1998

Louis Granboulan
\end{center}

\section{Parcours de graphes}
\begin{enumerate}
\item{Circuits eulériens}
  \begin{intro}
  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.
  \end{intro}
  \begin{enumerate}
    \item À quelle condition un graphe admet-il un circuit eulérien ?
    \item Proposer un algorithme de complexité ${\cal O}(E)$
          pour trouver un tel circuit s'il existe.
  \end{enumerate}
\item{Composantes biconnexes}
  \begin{intro}
  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.
  \end{intro}
  \begin{enumerate}
    \item Montrer que c'est une relation d'équivalence.
          On appelle {\em composantes biconnexes} les
          classes d'équivalence.
    \item Proposer un algorithme pour calculer les composantes biconnexes
          à l'aide d'un parcous en profondeur.
  \end{enumerate}
\begin{flots}
\item{Graphes bipartites}
  \begin{intro}
  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 {\em couplage} une partie $M\subset 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\subset V$, on note $V(X)$ l'ensemble des sommets
  adjacents à au moins un sommet de $X$.
  \end{intro}
  \begin{enumerate}
    \item Proposer un algorithme pour décider si un graphe est bipartite.
    \item Proposer un algorithme pour trouver un couplage maximal.
    \item Montrer le théorème de Hall : un graphe admet un couplage
          parfait si, et seulement si
          $\forall X\subset V, \quad |X| \geq |V(X)|$.
  \end{enumerate}
\end{flots}
\end{enumerate}

\section{Graphes d'expansion}
  \begin{intro}
  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 $\lambda_1 \geq \lambda_2 \geq ...$ les valeurs
  propres de cette matrice.
  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$.
  \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{Matrice d'adjacence}
  \begin{enumerate}
%   \item Montrer que $M$ est 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 Que représente ${}^tXMY$ ?
  \end{enumerate}
\item{Graphes d'expansion}
  \begin{enumerate}
    \item Supposons le graphe connexe.
          Montrer que $\delta(X) \geq -\lambda_2 |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-\frac{\lambda_2|X|}{dn}\rho^2\big)
           \leq 1-\frac{|X|}n$.
    \item En déduire que tout graphe est d'expansion
          $(n,d,\frac{-2\lambda_2}{d-2\lambda_2})$.
  \end{enumerate}
\end{enumerate}

\end{document}
