13.5: Un ejemplo concreto
- Page ID
- 118268
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Apliquemos el Algoritmo de Etiquetado al flujo de red que se muestra en la Figura 13.2. Entonces comenzamos con la fuente:
\(S:(∗,+,∞)\)
Dado que la fuente\(S\) es el primer vértice etiquetado, también es el primero escaneado. Entonces miramos a los vecinos de\(S\) usar el orden pseudo-alfabético en los vértices. Así, el primero en ser considerado es el vértice\(B\) y como el borde no\((S,B)\) está lleno, etiquetamos\(B\) como
\(B:(S,+,8)\).
Luego consideramos el vértice\(E\) y lo etiquetamos como
\(E:(S,+,28)\).
El siguiente es el vértice\(F\), que está etiquetado como
\(F:(S,+,15)\).
En este punto, el escaneo de\(S\) está completo.
El primer vértice después de\(S\) ser etiquetado fue\(B\), así que ahora escaneamos desde\(B\). Los vecinos (sin etiquetar) de\(B\) a ser considerados, en orden, son\(A, C\), y\(D\). Esto da como resultado las siguientes etiquetas:
\(A:(B,+,8)\)
\(C:(B,+,8)\)
\(D:(B,−,6)\)
El siguiente vértice a escanear es\(E\), pero no\(E\) tiene vecinos sin etiquetar, así que luego pasamos a\(F\), que nuevamente no tiene vecinos sin etiquetar. Finalmente, escaneamos desde\(A\), y usando el orden pseudo-alfabético, primero consideramos el sumidero\(T\) (que en este caso es el único vértice sin etiquetar que queda). Esto da como resultado la siguiente etiqueta para\(T\).
\(T:(A,+,8)\)
Ahora que el fregadero está etiquetado, sabemos que hay un camino de aumento. Descubrimos este camino retrocediendo. El fregadero\(T\) obtuvo su etiqueta de\(A, A\) obtuvo su etiqueta de\(B\), y\(B\) obtuvo su etiqueta de\(S\). Por lo tanto, el camino de aumento es\(P=(S,B,A,T)\) con\(δ=8\). Todos los bordes en este camino son hacia adelante. Luego, el flujo se actualiza aumentando el flujo en los bordes\(P\) de en 8. Esto da como resultado el flujo mostrado en la Figura 13.12. El valor de este flujo es 38.
Aquí está la secuencia (leyendo las columnas) de etiquetas que se encontrarán cuando se aplique el algoritmo de etiquetado a este flujo actualizado. (Tenga en cuenta que en el escaneo desde\(S\), no\(B\) se etiquetará el vértice, ya que ahora el borde\((S,B)\) está lleno).
\(S:(∗,+,∞)\)\(D:(E,+,12)\)
\(E:(S,+,28)\)\(A:(F,+,12)\)
\(F:(S,+,15)\)\(C:(B,+,10)\)
\(B:(E,+,19)\)\(T:(A,+,12)\)
Este etiquetado da como resultado la ruta de aumento\(P=(S,F,A,T)\) con\(δ=12\).
Después de esta actualización, el valor del flujo se ha incrementado y ahora es 50=38+12. Comenzamos de nuevo el proceso de etiquetado y repetimos hasta llegar a una etapa en la que algunos vértices (incluido el origen) están etiquetados y algunos vértices (incluido el sumidero) no están etiquetados.
13.5.1 Cómo se detiene el algoritmo de etiquetado
Considere el flujo de red en la Figura 13.13.
El valor del flujo de corriente es 172. La aplicación del algoritmo de etiquetado usando el orden pseudo-alfabético da como resultado las siguientes etiquetas (leyendo las columnas):
\(S:(∗,+,∞)\)\(E:(I,−,3)\)
\(C:(S,+,8)\)\(G:(E,−,3)\)
\(F:(S,+,23)\)\(L:(E,+,3)\)
\(H:(C,+,7)\)\(B:(G,+,3)\)
\(I:(H,+,7)\)\(T:(L,+,3)\)
Estas etiquetas dan como resultado la ruta de aumento\(P=(S,C,H,I,E,L,T)\) con\(δ=3\). Después de actualizar el flujo y aumentar su valor a 175, el algoritmo de etiquetado se detiene con las siguientes etiquetas:
\(S:(∗,+,∞)\)\(H:(C,+,4)\)
\(C:(S,+,5)\)\(I:(H,+,4)\)
\(F:(S,+,23)\)
Ahora observamos que los vértices etiquetados y no etiquetados son\(L=\{S,C,F,H,I\}\) y\(U=\{T,A,B,D,E,G,J,K\}\). Además, la capacidad del corte\(V=L \cup U\) es
41+8+23+8+13+29+28+25=175.
Esto demuestra que hemos encontrado un corte cuya capacidad es exactamente igual al valor del flujo de corriente. A su vez, esto demuestra que el flujo es óptimo.