\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}
\begin{center}
\LARGE
Algorithmique et programmation

Travaux dirigés, 21 décembre 2001

\textbf{Graphes ; Arborescences.}
\end{center}
\vspace*{1cm}

\begin{enumerate}

\item{Arborescences}
  \begin{intro}
  Une arborescence de racine $r$ est un graphe orienté (fini)
  dont $r$ est un sommet
  et tel que pour tout autre sommet $x$ il existe un unique chemin de
  $r$ à $x$.
  On représente souvent une arborescence en numérotant ses sommets et
  en indiquant pour chacun quel est son père.
  \end{intro}
  \begin{enumerate}
    \item Quelle est la différence entre un arbre et une arborescence ?
    \item Si les sommets sont numérotés de 1 à $n$,
          on dit qu'une arborescence est préfixe lorsque l'ensemble des
          descendants de tout sommet $i$ est un intervalle dont le minimum
          est $i$. Trouver un algorithme de renumérotation qui rend une
          arborescence préfixe.
  \end{enumerate}

\item{Arborescence recouvrante}
  \begin{intro}
  Étant donné un graphe orienté $G$, une arborescence recouvrante est un
  graphe partiel de $G$ qui est une arborescence et qui passe par
  tous les sommets.
  On dit qu'un graphe est enraciné en $r$ s'il existe une arborescence
  recouvrante de racine $r$.
  \end{intro}
  \begin{enumerate}
    \item Trouver un algorithme qui dit si un graphe est enraciné.
  \end{enumerate}

\item{Chemin de poids minimal}
  \begin{intro}
  On suppose que chaque arc est valué par un réel.
  Le poids d'un chemin est la somme des poids de ses arcs.
  \end{intro}
  \begin{enumerate}
    \item Proposer un algorithme pour calculer un chemin de poids minimal
          entre deux sommets, dans le cas où les poids des arcs ne sont
          jamais négatifs.
    \item Proposer un algorithme pour trouver s'il existe un cycle de poids
          négatif.
    \item Proposer un algorithme pour calculer un chemin de poids minimal
          dans le cas général.
  \end{enumerate}

\item{Arborescences recouvrantes de poids minimal}
  \begin{intro}
  On suppose que chaque arc est valué par un réel strictement positif.
  Le poids d'une arborescence est la somme des poids de ses arcs.
  \end{intro}
  \begin{enumerate}
    \item Proposer un algorithme pour trouver une arborescence
          recouvrante de poids minimal pour un graphe non-orienté.
    \item Regarder le cas des graphes orientés.
  \end{enumerate}

\item{Arborescence des dominants}
  \begin{intro}
  On suppose que le graphe (orienté) $G$ est acyclique et enraciné.
  On dit qu'un sommet en domine un autre s'il est dans tout chemin
  de la racine à cet autre sommet.
  \end{intro}
  \begin{enumerate}
    \item Montrer que la relation de domination décrit une arborescence.
    \item Trouver un algorithme qui calcule cette arborescence.
  \end{enumerate}

\item{Réduction transitive}
  \begin{intro}
  Rappel : la clôture transitive d'un graphe (orienté)
  est un graphe ayant les mêmes
  sommets et dont deux sommets sont reliés par une arête s'il
  y a un chemin les reliant dans le graphe de départ.
  \par
  Une réduction transitive est un graphe avec un nombre minimal
  d'arêtes et même clôture transitive.
  \end{intro}
  \begin{enumerate}
    \item Trouver une condition pour que la réduction transitive soit unique.
    \item Trouver un algorithme de calcul d'une réduction transitive.
  \end{enumerate}

\end{enumerate}

\end{document}
