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

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

\else

%% 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}}
\fi

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

Travaux dirigés, 11 et 17 janvier 2000

Louis Granboulan
\end{center}

Le but de cette séance est d'étudier la signification
des valeurs propres de la matrice d'adjacence.
La première partie montre qu'elles sont toutes
de même signe et que le rang exprime le nombre de
composantes connexes.
La seconde partie montre que la plus proche de 0
mesure la capacité d'expansion du graphe.

\section{Matrice d'adjacence}
  \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}

\section{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,\frac{2\lambda}{d+2\lambda})$.
    \item Soit $y$ un vecteur propre associé à $\lambda$
          ayant moins de coordonnées positives que négatives.
          Notons $X$ l'ensemble des sommets correspondant
          aux coordonnées positives et $x$ le vecteur qui
          s'obtient à partir de $y$ en remplaçant les
          coordonnées négatives par des 0.
          Montrer que $\lambda \geq {\Sigma_{(i,j)\in E}(x_i-x_j)^2
          \over \Sigma_{i\in V}x_i^2}$.
    \item Construisons $G'$ à partir de $G$ en rajoutant deux
          sommets $s$ et $t$, des arêtes de $s$ vers les sommets
          de $X$ et des arêtes des sommets de $V$ vers $t$.
          Toutes les arêtes ont capacité 1 sauf les arêtes
          issues de $s$ qui ont capacité $1+c$.
          Le flot maximal de $s$ à $t$ sur $G'$
          est de capacité $(1+c)|X|$. On considère les coefficients
          $\alpha_{(i,j)}$ de ce flot, sur l'arête $(i,j)$.
          Montrer que $\lambda \geq {\big(\Sigma_{(i,j)\in E}
          \alpha_{(i,j)}|x_i^2-x_j^2|\big)^2
          \over \Sigma_{i\in V}x_i^2}
          \Sigma_{(i,j)\in E}\alpha_{(i,j)}^2(x_i+x_j)^2$.
    \\    En déduire que pour un graphe d'expansion $(n,d,c)$ on a
          $\lambda \geq \frac{c^2}{4+2c^2}$.
  \end{enumerate}

\end{document}
