commit 9109316231dec3e94acb0408de90928ac4eb7855
parent f8e978db6c4a99a4caeabe8060c2a95f276e0cb4
Author: Georges Dupéron <jahvascriptmaniac+github@free.fr>
Date: Sat, 11 Dec 2010 15:00:29 +0100
Début de correction de la preuve de ma partie fait vandredi matin, je continuerai ce soir.
Diffstat:
1 file changed, 9 insertions(+), 2 deletions(-)
diff --git a/rapport.tex b/rapport.tex
@@ -205,10 +205,17 @@ Considérons les arcs entre les $v_{ai,t}$~:
\item Arcs de précédences~: ces arcs sont entre des sommets $v_{ai,t}$ et $v_{aj,t'}$ avec $ai < aj$, car grâce au tri topologique, il n'existe pas d'arcs entre des sommets $J_{ai}$ et $J_{aj}$ avec $aj < ai$, et de plus il n'y a pas de boucle (donc pas d'arc $(J_{ai},J_{ai})$ dans $G$, donc pas d'arc $(v_{ai,t}, v_{ai,t'})$ dans $G*$).
\item Arcs auxiliaires~: ces arcs ne sont pas entre des sommets $v_{ai,t}$.
\end{itemize}
-On va créer une $(s-t)-\mathrm{coupe}$ minimale. Etant donné que cette coupe est minimale, aucun arc de capacité infinie n'a son origine dans $S$ et son extremité dans $\overline{S}$.
+Soit un $(s-t)-\mathrm{coupe}$ minimale, entre les ensembles de noeuds $S$ et $T$. Etant donné que cette coupe est minimale, aucun arc de capacité infinie n'a son origine dans $S$ et son extremité dans $\overline{S}$. Autrement dit, en fonction des noeuds présents dans S, on est donc \og obligé\fg d'inclure dans $S$ toutes les extrémités des arcs de capacité infinie et dont l'origine est dans $S$. On va donc construire $S$ itérativement en suivant cette règle.
+
+\begin{itemize}
+\item $s \in S$, et tous les arcs sortant de $s$ sont les arcs auxiliaires, de capacité infinie, qui pointent
+sur tous les $v_{ai,0}$. On les inclut donc dans $S$.
+\item Pour chaque $v_{ai,t}$ dans $S$, on n'a pas besoin de suivre les arcs d'affectation, car ils sont de capacité finie. Comme ces arcs d'affectation \og restent sur la même ligne\fg, à partir du moment où un $v_{ai,t}$ est présent dans $S$, les arcs d'affectation ne nous obligent pas à inclure les $v_{ai,t'}$ avec $t' > t$.
+\item Par contre les arcs de précédence nous obligent, lorsqu'on inclut un $v_{ai,t}$, d'inclure tous les $v_{aj,t'}$ qui sont à l'extrémité d'un arc de précédence partant de
+\end{itemize}
TODO~: Montrons que s'il s'agit d'une coupe minimale, il ne sort qu'un et qu'un
-seul arc d'affectation par job. Il faut aussi montrer qu'il (il = ?) existe.
+seul arc d'affectation par job. Il faut aussi montrer qu'il (il = l'arc d'affectation) existe.
\begin{enonce}
Montrer que l'on peut associer un ordonnancement réalisable (qui respectent toutes les contraintes à toute
