\documentclass[12pt]{article}
\usepackage{isolatin1}
\pagestyle{empty}
\begin{document}
\begin{center}\large \bf
MIAGE Master 1\\
Recherche Op\'erationnelle 1\\
TD7: le 16/11/2006\\
Algorithmes de flot maximum
\end{center}

Trouver un flot maximum pour le r\'eseau
donn\'e:
\begin{enumerate}
\item Soit par l'algorithme de Ford et Fulkerson; vous allez
dessiner le flot dans le r\'eseau apr\`es chaque recherche d'une cha\^{\i}ne
augmentante.
\item Soit par l'algorithme des hauteurs\\
rappel: tant que possible on ajoute un flot d'un sommet à un voisin moins haut;
si ceci est impossible on incrémente la hauteur d'un sommet au minimum qui le
rend possible\\
correction: au début la hauteur de la source est $n$ le nombre de sommets et
celle de chaque autre sommet est $0$; on ne change pas la hauteur de la
source ou du puits.
\end{enumerate}
Essayez de ne pas utiliser le même algorithme que vos voisins; quand vous
aurez terminé vérifier que la quantité transférée est la même pour les deux
algorithmes; avez-vous exactement le même flot que vos voisins?\\[1cm]
Quelle est la coupe minimum?\\[1cm]
{\bf Sommets:} ${A(source),~B,~C,~D,~E,~F,~G,~H,~I(destination)}$\\[5mm]
{\bf Ar\^etes:} (avec capacit\'es dans chaque sens):\\
$AB(2),~AC(5),~AD(7),~BF(6),~BG(5),~CD(3),~CF(3),~CG(4),$\\
$CH(3),~DE(4),~EG(4),~EH(1),~FI(6),~GI(5),~HI(3)$
\end{document}
