You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

374 lines
11KB

  1. \section{Chapitre 7: Problème du flot maximum}
  2. \label{sec:ch7}
  3. Référence: \cite{papadimitriou2013combinatorial}
  4. \subsection{Les graphes orientés}
  5. \label{sec:graphesorientes}
  6. \begin{itemize}
  7. \item Un graphe est un tuple $(V,E)$ formé de \textbf{sommets} $V$ et d'\textbf{arêtes} $E \subseteq V \times V$.
  8. \item Une arête est représentée par une paire de sommets. Ces sommets sont \textbf{adjacents}.
  9. \item Un graphe peut avoir des \textbf{poids} sur ses arêtes.
  10. \item Un \textbf{chemin} est une suite de sommets distincts. Il a une \textbf{origine} et une \textbf{destination}.
  11. \item Un \textbf{cycle} est une suite de sommets distincts dont le dernier sommet est adjacent au premier.
  12. \item Liste de proximité: Tableau $Adj$ dont chaque élément $Adj[i]$ pointe sur une liste qui contient les sommets adjacents. Cette liste peut être doublement chaînée
  13. \end{itemize}
  14. \subsection{Fouille en profondeur}
  15. \label{sec:fouilleprofondeur}
  16. \begin{itemize}
  17. \item Code de couleurs: Blanc=non visité, Gris=visite non complétée, Noir=visite complétée
  18. \item Vecteur parent: Encode une forêt. $u$ est le parent de $v$ = $Parent[v]=u$
  19. \item Complexité:
  20. \begin{table}[!ht]
  21. \centering
  22. \begin{tabular}{l|l}
  23. Étape & Complexité \\
  24. \hline
  25. Initialisation & $\mathcal{O}(|V|)$ \\
  26. Visite & $|V|$ \\
  27. Arête & $|E|$ \\
  28. \hline
  29. \textbf{Total} & $\mathcal{O}(|V|+|E|)$
  30. \end{tabular}
  31. \caption{Complexité de la fouille en profondeur}
  32. \label{tab:compfouilleprof}
  33. \end{table}
  34. \end{itemize}
  35. \begin{algorithm}[!ht]
  36. \Deb{
  37. \PourTous{$u \in V$}{
  38. $Couleur[u] \leftarrow Blanc$ \;
  39. $Parent[u] \leftarrow Nul$ \;
  40. }
  41. \PourTous{$u \in V$}{
  42. \Si{$Couleur[u]=Blanc$}{
  43. Visite$(u,V,E)$ \;
  44. }
  45. }
  46. }
  47. \caption{FouilleProfondeur$(V,E)$}
  48. \end{algorithm}
  49. \begin{algorithm}[!ht]
  50. \Deb{
  51. $Couleur[u]=Gris$ \;
  52. \Pour{$v \in Adj[u]$}{
  53. \Si{$Couleur[u]=Blanc$}{
  54. $Parent[v] \leftarrow u$ \;
  55. Visite$(v,V,E)$ \;
  56. }
  57. }
  58. $Couleur[u]=Noir$
  59. }
  60. \caption{Visite$(u,V,E)$}
  61. \end{algorithm}
  62. Pour trouver un chemin entre $s$ et $t$, on exécute seulement la fouille en profondeur sur l'origine $s$. Si $t$ est nul, il n'y a pas de chemin de $s$ vers $t$.
  63. \subsection{Problème du flot maximum}
  64. \label{sec:flotmaximum}
  65. Définition du problème:
  66. \begin{itemize}
  67. \item $s$: Source
  68. \item $t$: Puits
  69. \item $c(a,b)$: Capacité
  70. \item $f(a,b)=-f(b,a)$: Flot
  71. \item Instance: $FlotMaximum(G=(V,E),s,t,c)$
  72. \end{itemize}
  73. Contraintes: un flot valide satisfait ces contraintes
  74. \begin{itemize}
  75. \item Conservation du flot:
  76. \begin{align}
  77. \sum_{b \mid (b,a) \in E} f(b,a) &= \sum_{b \mid (a,b) \in E} f(a,b) & \forall a \in V \setminus \lbrace s,t \rbrace
  78. \end{align}
  79. \item Ce qui équivaut à:
  80. \begin{align}
  81. \sum_{b \in V} f(a,b) &= 0 & \forall a \in V \setminus \lbrace s,t \rbrace
  82. \end{align}
  83. \item Contrainte de capacité:
  84. \begin{align}
  85. f(a,b) &\leq c(a,b) & \forall (a,b) \in E \\
  86. f(a,b) &\leq 0 & \forall (a,b) \notin E
  87. \end{align}
  88. \end{itemize}
  89. Le problème du flot maximum consiste à trouver un flot valide dont la valeur est maximale
  90. \begin{align}
  91. v(f) &= \sum_{a \in V}f(s,a)\\
  92. &= \sum_{a \in V} f(a,t)
  93. \end{align}
  94. Représentation graphique
  95. \begin{figure}[!ht]
  96. \centering
  97. \includegraphics[width=12cm]{exemple_flot}
  98. \caption{Représentation graphique d'un flot}
  99. \label{fig:grapheflot}
  100. \end{figure}
  101. \subsection{Chemins augmentant}
  102. \label{sec:cheminsaugmentant}
  103. Objectif: Identifier les chemins augmentants dans le graphe résiduel
  104. \paragraph{Graphe résiduel}
  105. \begin{itemize}
  106. \item Utilisé pour identifier les chemins reliant la source au puits
  107. \item Mêmes noeuds que le graphe original, mais les arêtes peuvent avoir un poids et une orientation différente
  108. \item Notation: $G_f = (V, E_f)$
  109. \item Existence d'une arête dans le graphe résiduel
  110. \begin{align}
  111. (a,b) \in E_{f} \iff f(a,b) < c(a,b)
  112. c_f(a.b) = c(a,b) - f(a.b)
  113. \end{align}
  114. \item Chemin augmentant: relie la source au puits dans le graphe résiduel. Non nul
  115. \end{itemize}
  116. Exemple de graphe résiduel (Figure \ref{fig:grapheresiduel})
  117. \begin{figure}[h]
  118. \centering
  119. \includegraphics[width=7cm]{exemple_flot_residuel}
  120. \caption{Graphe résiduel}
  121. \label{fig:grapheresiduel}
  122. \end{figure}
  123. \clearpage
  124. \subsection{Algorithme de Ford-Fulkerson}
  125. \label{sec:fordfulkerson}
  126. \begin{algorithm}[h]
  127. \Deb{
  128. \Pour{$i \in \binom{|V|}{2}$}{
  129. $f[i] \leftarrow 0$
  130. }
  131. \Repeter{aucun chemin entre $s$ et $t$ dans $G_f$}{
  132. Construire $G_f$ \;
  133. Trouver le chemin $C$ de $s$ à $t$ avec une fouille en profondeur \;
  134. \Si{$\exists C$}{
  135. $q=min(c_f(a,b)) | (a,b) \in C$ \;
  136. \PourTous{$(a,b) \in C$}{
  137. $f(a,b) \leftarrow f(a,b)+q$ \;
  138. $f(b,a) \leftarrow f(b,a)-q$ \;
  139. }
  140. }
  141. }
  142. \Retour{f} \;
  143. }
  144. \caption{Algorithme de Ford-Fulkerson}
  145. \end{algorithm}
  146. Complexité:
  147. \begin{table}[h]
  148. \centering
  149. \begin{tabular}{l|l}
  150. Étape & Complexité \\
  151. \hline
  152. Chemin dans le graphe résiduel & $\mathcal{O}(|V|+|E|), |V|-1 \leq |E| \rightarrow \mathcal{O}(|E|)$ \\
  153. Mise à jour du graphe résiduel & $\mathcal{O}(|V|)$ \\
  154. \hline
  155. \textbf{Total} & $\mathcal{O}(v(f)|E|)$
  156. \end{tabular}
  157. \caption{Complexité de l'algorithme de Ford-Fulkerson}
  158. \label{tab:compfouilleprofordfulkerson}
  159. \end{table}
  160. \subsection{Coupe minimale}
  161. \label{sec:coupeminimale}
  162. \begin{itemize}
  163. \item Une coupe est une bipartition des noeuds tel que la source est dans $S$ et le puits dans $T$
  164. \item Capacité d'une coupe
  165. \begin{align}
  166. c(S,T) &= \sum_{a \in S} \sum_{b \in T} c(a,b)
  167. \end{align}
  168. \item Flot net d'une coupe: quantité de flot passant d'un noeud dans $S$ à un noeud dans $T$:
  169. \begin{align}
  170. f(S,T) &= \sum_{a\in S, b\in T} f(a,b)
  171. \end{align}
  172. \item Théorème: Pour toute coupe $(S,T)$ et tout flot valide $f$: $v(f)=f(S,T)$
  173. \end{itemize}
  174. Trois affirmations équivalentes:
  175. \begin{enumerate}
  176. \item $f$ est un flot maximum dans $G$
  177. \item Le graphe résiduel $G_f$ n'a pas de chemin augmentant
  178. \item Il existe une coupe $(S,T)$ dont la capacité $c(S,T)$ est égale a $v(f)$
  179. \end{enumerate}
  180. \subsection{Types de problèmes}
  181. \label{sec:flotproblemes}
  182. \paragraph{Ordonnancement}
  183. Source reliée aux personnes avec des arêtes de capacité 1.
  184. Personnes reliées aux plages de disponibilité avec une capacité de 1
  185. Plages de disponibilité reliées au puits avec capacité de 1.
  186. La partie du graphe se nomme couplage: sous-ensemble d'arêtes non adjacentes.
  187. On recherche un couplage maximum.
  188. \paragraph{All-Different}
  189. \begin{itemize}
  190. \item Se résout aussi avec un couplage maximum.
  191. \item On peut trouver un autre support de domaine en poussant une unité de flot sur un cycle.
  192. \item La différence entre les deux flots valides est un ensemble de cycles disjoints.
  193. \item La valeur $v$ a un support de domaine dans $dom(X_i)$ ssi. $(v,X_i)$ appartient au graphe résiduel ou $(v,X_i)$ appartient à un cycle du graphe résiduel.
  194. \end{itemize}
  195. \begin{figure}[!ht]
  196. \centering
  197. \includegraphics[width=6cm]{composantsfortementconnexes}
  198. \caption{Composants fortement connexes}
  199. \label{fig:composantfortement}
  200. \end{figure}
  201. \subsection{Algorithmes de Kosaraju et de Régin}
  202. \label{sec:kosarajuregin}
  203. \paragraph{Algorithme de Kosaraju}
  204. Sert à identifier les composantes fortement connexes: ensembles de noeuds où chaque noeud peut rejoindre tous les autres noeuds. Cet ensemble est maximal.
  205. \begin{enumerate}
  206. \item Effectuer une fouille en profondeur
  207. \item Ajouter les noeuds coloriés en noir à une pile
  208. \item Construire le graphe transposé
  209. \item Effectuer une fouille en profondeur sur le graphe transposé en dépilant les noeuds
  210. \item Définir le vecteur parent de cette fouille. Chaque arbre est une composante fortement connexe
  211. \end{enumerate}
  212. \paragraph{Algorithme de Régin}
  213. Filtrage pour All-Different
  214. \begin{enumerate}
  215. \item Calculer un couplage avec Ford-Fulkerson
  216. \item Marquer toutes les arêtes faisant partie d'un cycle
  217. \item Retirer $v$ du domaine de $X_i$ si le flot est nul sur $(X_i,v)$ ou si cette arête n'est pas marquée.
  218. \end{enumerate}
  219. \begin{algorithm}
  220. \Deb{
  221. Construire un graphe $G$ avec $V= \lbrace X_1,\ldots,X_n \rbrace \cup \bigcup_{i=1}^{n} dom(X_i) \cup \lbrace s,t \rbrace$ \;
  222. \Pour{$i \in \left[ 1,\ldots,n \right]$}{
  223. \Pour{$v \in dom(X_i)$}{
  224. Ajouter $(C_i,v)$ de capacité 1 à $G$ \;
  225. }
  226. Ajouter l'arête $(s,X_i)$ de capacité 1 à $G$ \;
  227. }
  228. \Pour{$v \in \bigcup_{i=1}^{n} dom(X_i)$}{
  229. Ajouter l'arête $(v,t)$ de capacité 1 à $G$ \;
  230. }
  231. $f \leftarrow$ Ford-Fulkerson($G$) \;
  232. \Si{$v(f) \neq n$}{
  233. $sat=Faux$ \;
  234. }
  235. composantes $\leftarrow$ Kosaraju(GrapheResiduel) \;
  236. \Pour{$i \in \left[ 1,\ldots,n \right]$}{
  237. \Pour{$v \in dom(X_i)$}{
  238. \Si{$f(X_i,v)=0 \wedge$ composante($X_i$) $\neq$ composante($v$)}{
  239. $dom(X_i) \leftarrow dom(X_i) \ \lbrace v \rbrace$
  240. }
  241. }
  242. }
  243. }
  244. \caption{Algorithme de Régin}
  245. \end{algorithm}
  246. Complexité: (D=somme des cardinalité des domaines). Possible de ramener à $\mathcal{O}(\delta D)$ en pratique, où $\delta$ est le nombre de valeurs supprimées des domaines.
  247. \begin{table}[h]
  248. \centering
  249. \begin{tabular}{l|l}
  250. Étape & Complexité \\
  251. \hline
  252. Calcul du flot&$\mathcal{O}(nD)$ \\
  253. Calcul des composantes fortement connexes&$\mathcal{O}(D)$ \\
  254. Boucles de l'algorithme&$\mathcal{O}(D)$ \\
  255. \hline
  256. \textbf{Total} & $\mathcal{O}(nD)$
  257. \end{tabular}
  258. \caption{Complexité de l'algorithme de Régin}
  259. \label{tab:compregin}
  260. \end{table}
  261. \subsection{Production et consommation de flot}
  262. \label{sec:prodconsflot}
  263. On associe $b_i$ pour chaque noeud $i$ du graphe.
  264. \begin{itemize}
  265. \item Si $b_i>0$, le noeud produit $b_i$ unités de flot et les injecte dans le graphe
  266. \item Si $b_i<0$, le noeud absorbe $b_i$ unités de flot
  267. \end{itemize}
  268. La contrainte de conservation du flot devient:
  269. \begin{align}
  270. \sum_{b \mid (a,b) \in E} f(a,b) - \sum_{b \mid (b,a) \in E} f(b,a) &= b_a &\forall a \in V
  271. \end{align}
  272. Exemple:
  273. \begin{itemize}
  274. \item Problème: Chaque noeud est soit un producteur ou un consommateur de marchandise, les arêtes représentent le réseau de transport.
  275. \item Solution: Créer un noeud source et le relier à chaque producteur. Créer un noeud puits et l'ajouter à chaque consommateur.
  276. \item Résoudre le flot maximum avec Ford-Fulkerson
  277. \end{itemize}
  278. \subsection{Capacités minimales}
  279. \label{sec:capaciteminimale}
  280. On ajoute une capacité minimale $l(a,b)$ sur chaque arête. On a maintenant cette contrainte:
  281. \begin{align}
  282. l(a,b) &\leq f(a,b) \leq c(a,b)\\
  283. l(a,b) &= -c(b,a)
  284. \end{align}
  285. \begin{itemize}
  286. \item Le graphe résiduel est inchangé. Si f(a,b)=l(a,b), l'arête n'apparaitra pas
  287. \item On peut utiliser l'algorithme de Ford-Fulkerson sur ce graphe résiduel.
  288. \item On doit identifier un flot valide initial
  289. \end{itemize}
  290. Résolution:
  291. \begin{enumerate}
  292. \item Ajouter (s,t) tel que $l(s,t)=0$ et $c(s,t)=\infty$
  293. \item On effectue le changement de variable $f^{\prime}(a,b) = f(a,b) - l(a,b)$
  294. \item On retrouve le problème de production et consommation de flot
  295. \item On ajoute une source et un puits, puis on exécute l'algorithme de Ford-Fulkerson
  296. \item Le flot maximum obtenu est un flot initial valide pour le problème des capacités minimales
  297. \item On exécute l'algorithme de Ford-Fulkerson pour le problème initial
  298. \end{enumerate}
  299. %%% Local Variables:
  300. %%% mode: latex
  301. %%% TeX-master: "notes_de_cours"
  302. %%% End: