Součásti dokumentu 01ZTGA
Zdrojový kód
%\wikiskriptum{01ZTGA}
\section{Toky v sítích}
\begin{defn}
Nechť $V$ je konečná množina, $A\subset V\times V$. Uspořádanou
dvojici $D=(V,A)$ nazýváme \textbf{orientovaným grafem} (angl. \emph{directed
graph}, \emph{,,digraph{}``}). Prvky množiny $A$ se nazývají orientované
hrany (angl. \emph{arcs}).
\end{defn}
\begin{defn}
Nechť $D=(V,A)$ je orientovaný graf, $X\subset V$, $Y\subset V$,
$X,Y\neq\emptyset$ a nechť je dáno zobrazení $c:A\mapsto\N$. Potom
uspořádaná čtveřice $(D,X,Y,c)$ se nazývá \textbf{síť} (angl. \emph{network}).
Vrcholy z $X$ se nazývají \textbf{zdroje} (angl. \emph{sources}),
vrcholy z $Y$ \textbf{spotřebiče} (angl. \emph{sinks}), vrcholy z
$I:=V\backslash X\backslash Y$ se nazývají \textbf{uzlové body} (angl.
\emph{intermediate vertices}). Pro $a\in A$ představuje $c(a)$ \textbf{kapacitu
hrany} $a$.
\end{defn}
\begin{defn}
\label{def:definice-toku} Nechť $N=(D,X,Y,c)$ je síť. Zobrazení
$f:A\mapsto\R_{0}^{+}$ nazveme \textbf{tokem} v síti $N$, jestliže
platí
\begin{enumerate}
\item $\left(\forall a\in A\right)\left(f(a)\leq c(a)\right)$, tj. tok
po hraně je omezen její kapacitou,
\item $\left(\forall v\in I\right)\left(\sum\limits _{(u,v)\in A}f\left((u,v)\right)=\sum\limits _{(v,u)\in A}f\left((v,u)\right)\right)$,
tj. v uzlových bodech platí, že ,,co do vrcholu vtéká, to z něj také
vytéká{}``.
\end{enumerate}
\end{defn}
\begin{defn}
Nechť $f$ je tok v síti $N=(D,X,Y,c)$. Nechť $S\subset V$ je taková,
že $X\subset S$, $S\cap Y=\emptyset$. Označme $\bar{S}=V\backslash S$.
Potom dvojici $(S,\bar{S})$ nazýváme \textbf{řezem} (angl. \emph{cut})
v síti $N$. \textbf{Kapacitou řezu} $(S,\bar{S})$ rozumíme číslo\[
c\left((S,\bar{S})\right)=\sum_{\begin{matrix}{\scriptstyle (u,v)\in A}\\
{\scriptstyle u\in S,v\in\bar{S}}\end{matrix}}c\left((u,v)\right)\]
Dále označme\[
f^{+}(S)=\sum_{\begin{matrix}{\scriptstyle (u,v)\in A}\\
{\scriptstyle u\in S,v\in\bar{S}}\end{matrix}}f(u,v)-\sum_{\begin{matrix}{\scriptstyle (u,v)\in A}\\
{\scriptstyle u\in\bar{S},v\in S}\end{matrix}}f(u,v).\]
Číslo $\val f:=f^{+}(X)$ nazýváme \textbf{hodnotou toku} $f$ (angl.
\emph{value of} $f$) v síti $N$.
\end{defn}
\begin{rem*}
Je snadné ukázat, že pro každý řez $(S,\bar{S})$ v síti $N$ platí
$f^{+}(S)=f^{+}(X)$. Formálně by to bylo možné provést postupnou
konstrukcí množiny $S$ z množiny $X$ přidáváním vrcholů jednoho
po druhém. Z definice toku $f$ pak plyne, že přidání jediného vrcholu
do $S$ nezmění hodnotu $f^{+}(S)$.
\end{rem*}
\begin{defn}
Tok $f$ v síti $N$ nazveme \textbf{maximální}, jestliže pro každý
jiný tok $\tilde{f}$ v $N$ platí $\val f\geq\val\tilde{f}$.
\end{defn}
\begin{obs}
Pro každý tok $f$ a řez $(S,\bar{S})$ v síti $N$ platí\[
\val f\leq c\left((S,\bar{S})\right).\]
\end{obs}
\begin{rem}
\label{rem:max-rez-min-tok}Speciálně platí, že hodnota maximálního
toku je $\leq$ než hodnota minimálního řezu, tj. řezu s nejmenší
kapacitou. Najdeme-li tok $f$ a řez $(S,\bar{S})$ tak, že\[
\val f=c\left((S,\bar{S})\right),\]
pak tok $f$ je maximální a řez $(S,\bar{S})$ je minimální.
\end{rem}
\begin{example*}
Na obrázku \ref{cap:Tok-v-siti} jsou římskými číslicemi vyznačeny
kapacity hran a arabskými číslicemi tok $f$ po jednotlivých hranách.
Dále jsou tam vyznačeny řezy $(S_{1},\bar{S}_{1}),(S_{2},\bar{S}_{2}),(S_{3},\bar{S}_{3})$
a jejich kapacity. Protože $\val f=5=c\left((S_{2},\bar{S}_{2})\right)$,
je řez $(S_{2},\bar{S}_{2})$ minimální a tok $f$ je maximální.%
\begin{figure}
\begin{center}
%Title: toky_priklad.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 21:40:08 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.096 25.718
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 5.715 24.289
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 3.334 24.289
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 3.334 26.194
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 0.953 25.241
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,1}\plot 7.499 26.670 7.497 26.668 /
\plot 7.497 26.668 7.491 26.666 /
\plot 7.491 26.666 7.480 26.659 /
\plot 7.480 26.659 7.463 26.651 /
\plot 7.463 26.651 7.440 26.640 /
\plot 7.440 26.640 7.408 26.623 /
\plot 7.408 26.623 7.370 26.602 /
\plot 7.370 26.602 7.326 26.579 /
\plot 7.326 26.579 7.275 26.551 /
\plot 7.275 26.551 7.220 26.518 /
\plot 7.220 26.518 7.159 26.484 /
\plot 7.159 26.484 7.095 26.444 /
\plot 7.095 26.444 7.027 26.401 /
\plot 7.027 26.401 6.960 26.357 /
\plot 6.960 26.357 6.892 26.310 /
\plot 6.892 26.310 6.824 26.259 /
\plot 6.824 26.259 6.756 26.206 /
\plot 6.756 26.206 6.691 26.151 /
\plot 6.691 26.151 6.627 26.092 /
\plot 6.627 26.092 6.566 26.031 /
\plot 6.566 26.031 6.507 25.965 /
\plot 6.507 25.965 6.452 25.893 /
\plot 6.452 25.893 6.399 25.819 /
\plot 6.399 25.819 6.350 25.737 /
\plot 6.350 25.737 6.306 25.650 /
\plot 6.306 25.650 6.265 25.557 /
\plot 6.265 25.557 6.234 25.457 /
\plot 6.234 25.457 6.208 25.351 /
\plot 6.208 25.351 6.191 25.241 /
\plot 6.191 25.241 6.185 25.129 /
\plot 6.185 25.129 6.187 25.019 /
\plot 6.187 25.019 6.198 24.909 /
\plot 6.198 24.909 6.215 24.803 /
\plot 6.215 24.803 6.240 24.701 /
\plot 6.240 24.701 6.270 24.604 /
\plot 6.270 24.604 6.303 24.511 /
\plot 6.303 24.511 6.342 24.420 /
\plot 6.342 24.420 6.384 24.331 /
\plot 6.384 24.331 6.430 24.246 /
\plot 6.430 24.246 6.479 24.164 /
\plot 6.479 24.164 6.530 24.083 /
\plot 6.530 24.083 6.583 24.007 /
\plot 6.583 24.007 6.638 23.931 /
\plot 6.638 23.931 6.693 23.857 /
\plot 6.693 23.857 6.750 23.787 /
\plot 6.750 23.787 6.803 23.719 /
\plot 6.803 23.719 6.856 23.656 /
\plot 6.856 23.656 6.907 23.597 /
\plot 6.907 23.597 6.955 23.544 /
\plot 6.955 23.544 6.998 23.495 /
\plot 6.998 23.495 7.034 23.453 /
\plot 7.034 23.453 7.068 23.419 /
\plot 7.068 23.419 7.093 23.391 /
\plot 7.093 23.391 7.112 23.368 /
\plot 7.112 23.368 7.127 23.353 /
\plot 7.127 23.353 7.137 23.345 /
\plot 7.137 23.345 7.142 23.338 /
\plot 7.142 23.338 7.144 23.336 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,1}\putrule from 1.190 26.789 to 1.192 26.789
\putrule from 1.192 26.789 to 1.198 26.789
\putrule from 1.198 26.789 to 1.211 26.789
\plot 1.211 26.789 1.230 26.786 /
\plot 1.230 26.786 1.255 26.784 /
\plot 1.255 26.784 1.287 26.782 /
\plot 1.287 26.782 1.327 26.778 /
\plot 1.327 26.778 1.374 26.774 /
\plot 1.374 26.774 1.425 26.767 /
\plot 1.425 26.767 1.480 26.761 /
\plot 1.480 26.761 1.539 26.753 /
\plot 1.539 26.753 1.600 26.740 /
\plot 1.600 26.740 1.662 26.727 /
\plot 1.662 26.727 1.725 26.710 /
\plot 1.725 26.710 1.789 26.691 /
\plot 1.789 26.691 1.852 26.668 /
\plot 1.852 26.668 1.916 26.640 /
\plot 1.916 26.640 1.977 26.609 /
\plot 1.977 26.609 2.040 26.573 /
\plot 2.040 26.573 2.102 26.528 /
\plot 2.102 26.528 2.161 26.477 /
\plot 2.161 26.477 2.220 26.420 /
\plot 2.220 26.420 2.278 26.352 /
\plot 2.278 26.352 2.333 26.276 /
\plot 2.333 26.276 2.381 26.194 /
\plot 2.381 26.194 2.419 26.118 /
\plot 2.419 26.118 2.451 26.037 /
\plot 2.451 26.037 2.477 25.961 /
\plot 2.477 25.961 2.500 25.887 /
\plot 2.500 25.887 2.519 25.817 /
\plot 2.519 25.817 2.536 25.753 /
\plot 2.536 25.753 2.548 25.694 /
\plot 2.548 25.694 2.559 25.641 /
\plot 2.559 25.641 2.565 25.595 /
\plot 2.565 25.595 2.574 25.552 /
\plot 2.574 25.552 2.578 25.514 /
\plot 2.578 25.514 2.582 25.480 /
\plot 2.582 25.480 2.587 25.449 /
\plot 2.587 25.449 2.589 25.419 /
\plot 2.589 25.419 2.591 25.392 /
\putrule from 2.591 25.392 to 2.591 25.362
\putrule from 2.591 25.362 to 2.591 25.332
\plot 2.591 25.332 2.589 25.298 /
\plot 2.589 25.298 2.587 25.265 /
\plot 2.587 25.265 2.582 25.224 /
\plot 2.582 25.224 2.578 25.182 /
\plot 2.578 25.182 2.570 25.131 /
\plot 2.570 25.131 2.561 25.076 /
\plot 2.561 25.076 2.548 25.015 /
\plot 2.548 25.015 2.532 24.945 /
\plot 2.532 24.945 2.510 24.871 /
\plot 2.510 24.871 2.487 24.790 /
\plot 2.487 24.790 2.457 24.704 /
\plot 2.457 24.704 2.421 24.617 /
\plot 2.421 24.617 2.381 24.528 /
\plot 2.381 24.528 2.328 24.431 /
\plot 2.328 24.431 2.269 24.337 /
\plot 2.269 24.337 2.206 24.255 /
\plot 2.206 24.255 2.140 24.179 /
\plot 2.140 24.179 2.074 24.109 /
\plot 2.074 24.109 2.007 24.047 /
\plot 2.007 24.047 1.939 23.990 /
\plot 1.939 23.990 1.869 23.942 /
\plot 1.869 23.942 1.799 23.895 /
\plot 1.799 23.895 1.729 23.853 /
\plot 1.729 23.853 1.659 23.815 /
\plot 1.659 23.815 1.590 23.779 /
\plot 1.590 23.779 1.522 23.747 /
\plot 1.522 23.747 1.454 23.717 /
\plot 1.454 23.717 1.391 23.690 /
\plot 1.391 23.690 1.329 23.666 /
\plot 1.329 23.666 1.272 23.645 /
\plot 1.272 23.645 1.221 23.626 /
\plot 1.221 23.626 1.179 23.611 /
\plot 1.179 23.611 1.143 23.599 /
\plot 1.143 23.599 1.115 23.590 /
\plot 1.115 23.590 1.094 23.584 /
\plot 1.094 23.584 1.082 23.580 /
\plot 1.082 23.580 1.075 23.575 /
\putrule from 1.075 23.575 to 1.071 23.575
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,1}\plot 5.000 26.789 5.002 26.786 /
\plot 5.002 26.786 5.004 26.782 /
\plot 5.004 26.782 5.008 26.772 /
\plot 5.008 26.772 5.014 26.759 /
\plot 5.014 26.759 5.025 26.740 /
\plot 5.025 26.740 5.036 26.712 /
\plot 5.036 26.712 5.052 26.681 /
\plot 5.052 26.681 5.069 26.642 /
\plot 5.069 26.642 5.088 26.600 /
\plot 5.088 26.600 5.110 26.549 /
\plot 5.110 26.549 5.131 26.496 /
\plot 5.131 26.496 5.154 26.439 /
\plot 5.154 26.439 5.177 26.376 /
\plot 5.177 26.376 5.201 26.310 /
\plot 5.201 26.310 5.224 26.240 /
\plot 5.224 26.240 5.247 26.168 /
\plot 5.247 26.168 5.268 26.092 /
\plot 5.268 26.092 5.287 26.012 /
\plot 5.287 26.012 5.304 25.925 /
\plot 5.304 25.925 5.321 25.834 /
\plot 5.321 25.834 5.336 25.737 /
\plot 5.336 25.737 5.347 25.633 /
\plot 5.347 25.633 5.357 25.523 /
\plot 5.357 25.523 5.362 25.404 /
\plot 5.362 25.404 5.366 25.277 /
\plot 5.366 25.277 5.364 25.144 /
\plot 5.364 25.144 5.357 25.004 /
\plot 5.357 25.004 5.349 24.881 /
\plot 5.349 24.881 5.336 24.759 /
\plot 5.336 24.759 5.321 24.640 /
\plot 5.321 24.640 5.302 24.526 /
\plot 5.302 24.526 5.283 24.414 /
\plot 5.283 24.414 5.262 24.308 /
\plot 5.262 24.308 5.241 24.206 /
\plot 5.241 24.206 5.218 24.107 /
\plot 5.218 24.107 5.192 24.014 /
\plot 5.192 24.014 5.167 23.923 /
\plot 5.167 23.923 5.141 23.834 /
\plot 5.141 23.834 5.114 23.747 /
\plot 5.114 23.747 5.086 23.664 /
\plot 5.086 23.664 5.057 23.584 /
\plot 5.057 23.584 5.029 23.506 /
\plot 5.029 23.506 5.000 23.429 /
\plot 5.000 23.429 4.972 23.357 /
\plot 4.972 23.357 4.945 23.288 /
\plot 4.945 23.288 4.917 23.222 /
\plot 4.917 23.222 4.892 23.161 /
\plot 4.892 23.161 4.868 23.103 /
\plot 4.868 23.103 4.847 23.053 /
\plot 4.847 23.053 4.828 23.006 /
\plot 4.828 23.006 4.811 22.968 /
\plot 4.811 22.968 4.796 22.934 /
\plot 4.796 22.934 4.784 22.909 /
\plot 4.784 22.909 4.775 22.890 /
\plot 4.775 22.890 4.769 22.875 /
\plot 4.769 22.875 4.765 22.866 /
\plot 4.765 22.866 4.763 22.862 /
\putrule from 4.763 22.862 to 4.763 22.860
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 5.715 24.289 8.096 25.718 /
%
% arrow head
%
\plot 7.739 25.325 8.096 25.718 7.582 25.587 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 3.334 26.194 8.096 25.718 /
%
% arrow head
%
\plot 7.576 25.616 8.096 25.718 7.606 25.920 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 5.715 24.289 3.334 26.194 /
%
% arrow head
%
\plot 3.826 25.995 3.334 26.194 3.635 25.757 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 3.334 24.289 to 5.715 24.289
%
% arrow head
%
\plot 5.207 24.136 5.715 24.289 5.207 24.441 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 3.334 24.289 to 3.334 26.194
%
% arrow head
%
\plot 3.486 25.686 3.334 26.194 3.181 25.686 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 0.953 25.241 3.334 24.289 /
%
% arrow head
%
\plot 2.805 24.336 3.334 24.289 2.919 24.619 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 0.953 25.241 3.334 26.194 /
%
% arrow head
%
\plot 2.919 25.864 3.334 26.194 2.805 26.147 /
%
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,1}$c((S_{3},\bar{S}_{3}))=8$}%
} [lB] at 6.905 22.384
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,1}$c((S_{1},\bar{S}_{1}))=6$}%
} [lB] at 0.237 22.384
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,1}$c((S_{2},\bar{S}_{2}))=5$}%
} [lB] at 3.571 21.670
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}2}%
} [lB] at 4.047 23.813
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}V}%
} [lB] at 7.023 24.528
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}I}%
} [lB] at 4.881 25.121
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}III}%
} [lB] at 5.952 26.075
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}II}%
} [lB] at 4.405 23.813
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}IV}%
} [lB] at 1.903 24.289
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}III}%
} [lB] at 3.452 25.004
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}II}%
} [lB] at 1.905 25.838
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}2}%
} [lB] at 6.668 24.409
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}3}%
} [lB] at 5.596 26.075
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}0}%
} [lB] at 4.286 24.765
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}1}%
} [lB] at 2.976 25.004
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}3}%
} [lB] at 1.547 24.289
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}2}%
} [lB] at 1.547 25.838
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}y}%
} [lB] at 8.572 25.599
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}c}%
} [lB] at 5.715 23.457
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}b}%
} [lB] at 3.213 23.457
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}a}%
} [lB] at 3.334 26.670
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}x}%
} [lB] at 0.356 25.123
\linethickness=0pt
\putrectangle corners at 0.205 27.265 and 8.604 21.429
\endpicture}
\end{center}
\caption{\label{cap:Tok-v-siti}Tok v síti a minimální řez}
\end{figure}
\end{example*}
\begin{rem*}
Každou síť lze snadno převést na síť s jediným zdrojem a jediným spotřebičem.
Přidáme zdroj $x_{0}$, spotřebič $y_{0}$ a všechny původní zdroje
spojíme s vrcholem $x_{0}$ hranami o dostatečně velké kapacitě (např.
rovné součtu všech kapacit v síti). To samé provedeme pro spotřebiče.
Díky tomu můžeme dále bez újmy na obecnosti uvažovat pouze sítě s
jediným zdrojem a jediným spotřebičem, které budeme místo $(D,\{ x_{0}\},\{ y_{0}\},c)$
značit jen jako $(D,x_{0},y_{0},c)$.
\end{rem*}
\subsection{Hledání maximálního toku pomocí $f$-nenasycených cest}
\begin{defn}
Nechť $f$ je tok v síti $N=(D,x_{0},y_{0},c)$ a nechť $P$ je neorientovaná%
\footnote{Cestu $P$ uvažujeme tak, jako kdyby graf $D$ nebyl orientovaný,
tj. každé hraně $a=(u,v)$ odpovídá neorientovaná hrana $\{ u,v\}$.
Formálně můžeme zapsat, že orientovanému grafu $D=(V,A)$ přísluší
neorientovaný graf $G_{D}=\left(V,\left\{ \left.\{ u,v\}\right|(u,v)\in A\right\} \right)$.%
} (!!) cesta s počátečním vrcholem $x_{0}$. Pro každou hranu $a\in P$
%
\footnote{Pokud uvažujeme $P$ jako podgraf $G_{D}$, pak bychom měli psát spíše
,,$a\in A$ taková, že $a=(u,v)$ a $\{ u,v\}\in E(P)${}``.%
} položme\[
\iota(a)=\begin{cases}
c(a)-f(a) & \textrm{je-li }a\textrm{ (na cest\v{e} }P\textrm{) orientována ve sm\v{e}ru z }x_{0}\\
f(a) & \textrm{je-li }a\textrm{ (na cest\v{e} }P\textrm{) orientována ve sm\v{e}ru do }x_{0}\end{cases}\]
Jestliže $\iota(P):=\min_{a\in P}\iota(a)>0$, pak řekneme, že cesta
$P$ je $f$-\textbf{nenasycená}.
\end{defn}
\begin{example*}
Na obrázku \ref{cap:nenasycena-cesta} je tlustou čarou znázorněna
$f$-nenasycená cesta $P$. Význam číslic je vysvětlen v minulém příkladě.
Podle definice zjistíme, že $\iota(P)=2$. Nyní upravíme tok v síti
následovně. Na hranách, které vedou po cestě $P$ ve směru od $x$,
zvýšíme tok o $\iota(P)$ a na hranách vedoucích po $P$ ve směru
do $x$ snížíme tok o $\iota(P)$. Potom nové zobrazení $\tilde{f}$,
které vznikne z $f$ uvedenými úpravami, je opět $\tilde{f}:A\mapsto\R_{0}^{+}$
a též první podmínka na tok v definici \ref{def:definice-toku} je
zřejmě splněna. Co se týká druhé podmínky, lze situace, které nastanou
na cestě $P$, shrnout na následujících schématech:
\hfill{}
\begin{center}
%Title: nenasyc_zpusoby.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:48:48 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at -4.763 30.956
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at -4.763 29.407
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at -0.953 30.956
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at -0.953 29.407
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from -6.191 30.956 to -4.763 30.956
%
% arrow head
%
\plot -5.271 30.804 -4.763 30.956 -5.271 31.109 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from -4.763 30.956 to -3.334 30.956
%
% arrow head
%
\plot -3.842 30.804 -3.334 30.956 -3.842 31.109 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from -6.191 29.407 to -4.763 29.407
%
% arrow head
%
\plot -5.271 29.254 -4.763 29.407 -5.271 29.559 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}%
% arrow head
%
\plot -4.255 29.559 -4.763 29.407 -4.255 29.254 /
%
\putrule from -4.763 29.407 to -3.334 29.407
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from -0.953 29.407 to 0.476 29.407
%
% arrow head
%
\plot -0.032 29.254 0.476 29.407 -0.032 29.559 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}%
% arrow head
%
\plot -1.873 29.559 -2.381 29.407 -1.873 29.254 /
%
\putrule from -2.381 29.407 to -0.953 29.407
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}%
% arrow head
%
\plot -1.873 31.109 -2.381 30.956 -1.873 30.804 /
%
\putrule from -2.381 30.956 to -0.953 30.956
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}%
% arrow head
%
\plot -0.444 31.109 -0.953 30.956 -0.444 30.804 /
%
\putrule from -0.953 30.956 to 0.476 30.956
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+\iota(P)$}%
} [lB] at -6.191 30.241
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+\iota(P)$}%
} [lB] at -4.644 30.241
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+\iota(P)$}%
} [lB] at -6.191 28.694
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+\iota(P)$}%
} [lB] at -0.834 28.694
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$-\iota(P)$}%
} [lB] at -2.381 30.241
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$-\iota(P)$}%
} [lB] at -0.834 30.241
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$-\iota(P)$}%
} [lB] at -4.644 28.694
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$-\iota(P)$}%
} [lB] at -2.381 28.694
\linethickness=0pt
\putrectangle corners at -6.238 31.153 and 0.523 28.535
\endpicture}
\end{center}
\hfill{}
\noindent Je vidět, že ať jsou hrany na vrcholech cesty $P$ orientovány
jakkoliv, bude v každém uzlovém bodě stále zachována bilance ,,vtoku{}``
a ,,výtoku{}``. Proto $\tilde{f}$ je tok, který má hodnotu $\val\tilde{f}=\val f+\iota(P)$.%
\begin{figure}
\begin{center}
%Title: nenasycena_cesta.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 23:49:44 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 17.145
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 12.383 17.145
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 15.716
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.474}}} at 7.620 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.474}}} at 13.335 19.526
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 10.478 20.955 to 10.478 19.526
%
% arrow head
%
\plot 10.325 20.034 10.478 19.526 10.630 20.034 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 10.478 19.526 to 10.478 19.524
\plot 10.478 19.524 10.475 19.518 /
\putrule from 10.475 19.518 to 10.475 19.505
\plot 10.475 19.505 10.471 19.488 /
\plot 10.471 19.488 10.467 19.465 /
\plot 10.467 19.465 10.463 19.433 /
\plot 10.463 19.433 10.454 19.395 /
\plot 10.454 19.395 10.446 19.351 /
\plot 10.446 19.351 10.435 19.300 /
\plot 10.435 19.300 10.425 19.245 /
\plot 10.425 19.245 10.410 19.188 /
\plot 10.410 19.188 10.395 19.124 /
\plot 10.395 19.124 10.378 19.058 /
\plot 10.378 19.058 10.357 18.993 /
\plot 10.357 18.993 10.336 18.923 /
\plot 10.336 18.923 10.310 18.853 /
\plot 10.310 18.853 10.283 18.779 /
\plot 10.283 18.779 10.251 18.703 /
\plot 10.251 18.703 10.215 18.625 /
\plot 10.215 18.625 10.175 18.544 /
\plot 10.175 18.544 10.128 18.459 /
\plot 10.128 18.459 10.075 18.373 /
\plot 10.075 18.373 10.016 18.282 /
\plot 10.016 18.282 9.950 18.191 /
\plot 9.950 18.191 9.881 18.098 /
\plot 9.881 18.098 9.807 18.009 /
\plot 9.807 18.009 9.728 17.924 /
\plot 9.728 17.924 9.652 17.844 /
\plot 9.652 17.844 9.578 17.772 /
\plot 9.578 17.772 9.504 17.706 /
\plot 9.504 17.706 9.432 17.647 /
\plot 9.432 17.647 9.362 17.592 /
\plot 9.362 17.592 9.292 17.541 /
\plot 9.292 17.541 9.224 17.494 /
\plot 9.224 17.494 9.159 17.452 /
\plot 9.159 17.452 9.093 17.412 /
\plot 9.093 17.412 9.028 17.374 /
\plot 9.028 17.374 8.966 17.338 /
\plot 8.966 17.338 8.907 17.306 /
\plot 8.907 17.306 8.848 17.276 /
\plot 8.848 17.276 8.795 17.249 /
\plot 8.795 17.249 8.746 17.225 /
\plot 8.746 17.225 8.702 17.204 /
\plot 8.702 17.204 8.666 17.187 /
\plot 8.666 17.187 8.634 17.173 /
\plot 8.634 17.173 8.611 17.162 /
\plot 8.611 17.162 8.572 17.145 /
%
% arrow head
%
\plot 8.975 17.491 8.572 17.145 9.099 17.212 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 10.478 19.526 to 10.478 19.524
\plot 10.478 19.524 10.480 19.518 /
\putrule from 10.480 19.518 to 10.480 19.505
\plot 10.480 19.505 10.484 19.488 /
\plot 10.484 19.488 10.488 19.465 /
\plot 10.488 19.465 10.492 19.433 /
\plot 10.492 19.433 10.501 19.395 /
\plot 10.501 19.395 10.509 19.351 /
\plot 10.509 19.351 10.518 19.300 /
\plot 10.518 19.300 10.530 19.245 /
\plot 10.530 19.245 10.543 19.188 /
\plot 10.543 19.188 10.560 19.124 /
\plot 10.560 19.124 10.577 19.058 /
\plot 10.577 19.058 10.596 18.993 /
\plot 10.596 18.993 10.617 18.923 /
\plot 10.617 18.923 10.643 18.853 /
\plot 10.643 18.853 10.670 18.779 /
\plot 10.670 18.779 10.702 18.703 /
\plot 10.702 18.703 10.738 18.625 /
\plot 10.738 18.625 10.778 18.544 /
\plot 10.778 18.544 10.825 18.459 /
\plot 10.825 18.459 10.878 18.373 /
\plot 10.878 18.373 10.937 18.282 /
\plot 10.937 18.282 11.002 18.191 /
\plot 11.002 18.191 11.072 18.098 /
\plot 11.072 18.098 11.146 18.009 /
\plot 11.146 18.009 11.225 17.924 /
\plot 11.225 17.924 11.301 17.844 /
\plot 11.301 17.844 11.375 17.772 /
\plot 11.375 17.772 11.449 17.706 /
\plot 11.449 17.706 11.521 17.647 /
\plot 11.521 17.647 11.593 17.592 /
\plot 11.593 17.592 11.661 17.541 /
\plot 11.661 17.541 11.728 17.494 /
\plot 11.728 17.494 11.796 17.452 /
\plot 11.796 17.452 11.862 17.412 /
\plot 11.862 17.412 11.925 17.374 /
\plot 11.925 17.374 11.989 17.338 /
\plot 11.989 17.338 12.048 17.306 /
\plot 12.048 17.306 12.105 17.276 /
\plot 12.105 17.276 12.160 17.249 /
\plot 12.160 17.249 12.209 17.225 /
\plot 12.209 17.225 12.253 17.204 /
\plot 12.253 17.204 12.289 17.187 /
\plot 12.289 17.187 12.321 17.173 /
\plot 12.321 17.173 12.344 17.162 /
\plot 12.344 17.162 12.383 17.145 /
%
% arrow head
%
\plot 11.856 17.212 12.383 17.145 11.980 17.491 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 8.572 17.145 to 8.572 17.147
\putrule from 8.572 17.147 to 8.572 17.151
\putrule from 8.572 17.151 to 8.572 17.160
\putrule from 8.572 17.160 to 8.572 17.175
\putrule from 8.572 17.175 to 8.572 17.194
\plot 8.572 17.194 8.575 17.219 /
\putrule from 8.575 17.219 to 8.575 17.251
\plot 8.575 17.251 8.577 17.289 /
\plot 8.577 17.289 8.579 17.331 /
\plot 8.579 17.331 8.581 17.380 /
\plot 8.581 17.380 8.585 17.435 /
\plot 8.585 17.435 8.589 17.492 /
\plot 8.589 17.492 8.596 17.556 /
\plot 8.596 17.556 8.602 17.621 /
\plot 8.602 17.621 8.611 17.691 /
\plot 8.611 17.691 8.621 17.763 /
\plot 8.621 17.763 8.634 17.837 /
\plot 8.634 17.837 8.647 17.913 /
\plot 8.647 17.913 8.664 17.996 /
\plot 8.664 17.996 8.683 18.078 /
\plot 8.683 18.078 8.706 18.167 /
\plot 8.706 18.167 8.731 18.258 /
\plot 8.731 18.258 8.761 18.356 /
\plot 8.761 18.356 8.797 18.459 /
\plot 8.797 18.459 8.835 18.567 /
\plot 8.835 18.567 8.882 18.680 /
\plot 8.882 18.680 8.932 18.800 /
\plot 8.932 18.800 8.987 18.923 /
\plot 8.987 18.923 9.049 19.050 /
\plot 9.049 19.050 9.110 19.169 /
\plot 9.110 19.169 9.174 19.285 /
\plot 9.174 19.285 9.237 19.397 /
\plot 9.237 19.397 9.303 19.505 /
\plot 9.303 19.505 9.366 19.609 /
\plot 9.366 19.609 9.430 19.706 /
\plot 9.430 19.706 9.493 19.799 /
\plot 9.493 19.799 9.555 19.888 /
\plot 9.555 19.888 9.618 19.973 /
\plot 9.618 19.973 9.677 20.053 /
\plot 9.677 20.053 9.739 20.130 /
\plot 9.739 20.130 9.798 20.206 /
\plot 9.798 20.206 9.857 20.278 /
\plot 9.857 20.278 9.917 20.348 /
\plot 9.917 20.348 9.974 20.413 /
\plot 9.974 20.413 10.031 20.479 /
\plot 10.031 20.479 10.086 20.540 /
\plot 10.086 20.540 10.139 20.599 /
\plot 10.139 20.599 10.190 20.654 /
\plot 10.190 20.654 10.238 20.707 /
\plot 10.238 20.707 10.283 20.754 /
\plot 10.283 20.754 10.323 20.796 /
\plot 10.323 20.796 10.359 20.834 /
\plot 10.359 20.834 10.391 20.866 /
\plot 10.391 20.866 10.416 20.894 /
\plot 10.416 20.894 10.437 20.915 /
\plot 10.437 20.915 10.454 20.932 /
\plot 10.454 20.932 10.478 20.955 /
%
% arrow head
%
\plot 10.226 20.488 10.478 20.955 10.011 20.704 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 10.478 20.955 10.480 20.957 /
\plot 10.480 20.957 10.486 20.959 /
\plot 10.486 20.959 10.494 20.963 /
\plot 10.494 20.963 10.509 20.970 /
\plot 10.509 20.970 10.530 20.980 /
\plot 10.530 20.980 10.558 20.991 /
\plot 10.558 20.991 10.592 21.006 /
\plot 10.592 21.006 10.632 21.021 /
\plot 10.632 21.021 10.676 21.038 /
\plot 10.676 21.038 10.725 21.054 /
\plot 10.725 21.054 10.778 21.074 /
\plot 10.778 21.074 10.835 21.088 /
\plot 10.835 21.088 10.894 21.103 /
\plot 10.894 21.103 10.958 21.118 /
\plot 10.958 21.118 11.024 21.129 /
\plot 11.024 21.129 11.091 21.135 /
\plot 11.091 21.135 11.163 21.139 /
\putrule from 11.163 21.139 to 11.240 21.139
\plot 11.240 21.139 11.318 21.133 /
\plot 11.318 21.133 11.402 21.122 /
\plot 11.402 21.122 11.494 21.105 /
\plot 11.494 21.105 11.589 21.080 /
\plot 11.589 21.080 11.690 21.048 /
\plot 11.690 21.048 11.796 21.006 /
\plot 11.796 21.006 11.906 20.955 /
\plot 11.906 20.955 12.002 20.904 /
\plot 12.002 20.904 12.095 20.849 /
\plot 12.095 20.849 12.184 20.792 /
\plot 12.184 20.792 12.268 20.731 /
\plot 12.268 20.731 12.351 20.669 /
\plot 12.351 20.669 12.427 20.606 /
\plot 12.427 20.606 12.499 20.540 /
\plot 12.499 20.540 12.569 20.477 /
\plot 12.569 20.477 12.634 20.411 /
\plot 12.634 20.411 12.698 20.345 /
\plot 12.698 20.345 12.757 20.280 /
\plot 12.757 20.280 12.816 20.214 /
\plot 12.816 20.214 12.871 20.149 /
\plot 12.871 20.149 12.926 20.083 /
\plot 12.926 20.083 12.977 20.017 /
\plot 12.977 20.017 13.028 19.954 /
\plot 13.028 19.954 13.075 19.892 /
\plot 13.075 19.892 13.117 19.833 /
\plot 13.117 19.833 13.159 19.778 /
\plot 13.159 19.778 13.195 19.727 /
\plot 13.195 19.727 13.227 19.681 /
\plot 13.227 19.681 13.257 19.641 /
\plot 13.257 19.641 13.280 19.607 /
\plot 13.280 19.607 13.299 19.579 /
\plot 13.299 19.579 13.314 19.558 /
\plot 13.314 19.558 13.335 19.526 /
%
% arrow head
%
\plot 12.926 19.864 13.335 19.526 13.180 20.033 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 7.620 19.526 7.622 19.528 /
\plot 7.622 19.528 7.624 19.535 /
\plot 7.624 19.535 7.631 19.543 /
\plot 7.631 19.543 7.641 19.558 /
\plot 7.641 19.558 7.656 19.579 /
\plot 7.656 19.579 7.675 19.607 /
\plot 7.675 19.607 7.698 19.641 /
\plot 7.698 19.641 7.728 19.681 /
\plot 7.728 19.681 7.760 19.727 /
\plot 7.760 19.727 7.796 19.778 /
\plot 7.796 19.778 7.838 19.833 /
\plot 7.838 19.833 7.880 19.892 /
\plot 7.880 19.892 7.927 19.954 /
\plot 7.927 19.954 7.978 20.017 /
\plot 7.978 20.017 8.029 20.083 /
\plot 8.029 20.083 8.084 20.149 /
\plot 8.084 20.149 8.139 20.214 /
\plot 8.139 20.214 8.198 20.280 /
\plot 8.198 20.280 8.257 20.345 /
\plot 8.257 20.345 8.321 20.411 /
\plot 8.321 20.411 8.386 20.477 /
\plot 8.386 20.477 8.456 20.540 /
\plot 8.456 20.540 8.528 20.606 /
\plot 8.528 20.606 8.604 20.669 /
\plot 8.604 20.669 8.687 20.731 /
\plot 8.687 20.731 8.771 20.792 /
\plot 8.771 20.792 8.860 20.849 /
\plot 8.860 20.849 8.954 20.904 /
\plot 8.954 20.904 9.049 20.955 /
\plot 9.049 20.955 9.159 21.006 /
\plot 9.159 21.006 9.265 21.048 /
\plot 9.265 21.048 9.366 21.080 /
\plot 9.366 21.080 9.462 21.105 /
\plot 9.462 21.105 9.553 21.122 /
\plot 9.553 21.122 9.637 21.133 /
\plot 9.637 21.133 9.716 21.139 /
\putrule from 9.716 21.139 to 9.792 21.139
\plot 9.792 21.139 9.864 21.135 /
\plot 9.864 21.135 9.931 21.129 /
\plot 9.931 21.129 9.997 21.118 /
\plot 9.997 21.118 10.061 21.103 /
\plot 10.061 21.103 10.120 21.088 /
\plot 10.120 21.088 10.177 21.074 /
\plot 10.177 21.074 10.230 21.054 /
\plot 10.230 21.054 10.279 21.038 /
\plot 10.279 21.038 10.323 21.021 /
\plot 10.323 21.021 10.363 21.006 /
\plot 10.363 21.006 10.397 20.991 /
\plot 10.397 20.991 10.425 20.980 /
\plot 10.425 20.980 10.446 20.970 /
\plot 10.446 20.970 10.478 20.955 /
%
% arrow head
%
\plot 9.953 21.032 10.478 20.955 10.082 21.308 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}%
% arrow head
%
\plot 12.230 17.534 12.383 17.026 12.535 17.534 /
%
\putrule from 12.383 17.026 to 12.383 17.058
\putrule from 12.383 17.058 to 12.383 17.079
\plot 12.383 17.079 12.380 17.107 /
\putrule from 12.380 17.107 to 12.380 17.141
\plot 12.380 17.141 12.378 17.183 /
\plot 12.378 17.183 12.376 17.230 /
\plot 12.376 17.230 12.374 17.283 /
\plot 12.374 17.283 12.370 17.342 /
\plot 12.370 17.342 12.366 17.405 /
\plot 12.366 17.405 12.359 17.473 /
\plot 12.359 17.473 12.353 17.543 /
\plot 12.353 17.543 12.344 17.617 /
\plot 12.344 17.617 12.334 17.695 /
\plot 12.334 17.695 12.321 17.776 /
\plot 12.321 17.776 12.308 17.858 /
\plot 12.308 17.858 12.291 17.945 /
\plot 12.291 17.945 12.272 18.034 /
\plot 12.272 18.034 12.249 18.127 /
\plot 12.249 18.127 12.224 18.224 /
\plot 12.224 18.224 12.194 18.328 /
\plot 12.194 18.328 12.158 18.434 /
\plot 12.158 18.434 12.120 18.548 /
\plot 12.120 18.548 12.073 18.667 /
\plot 12.073 18.667 12.023 18.792 /
\plot 12.023 18.792 11.968 18.919 /
\plot 11.968 18.919 11.906 19.050 /
\plot 11.906 19.050 11.845 19.173 /
\plot 11.845 19.173 11.781 19.291 /
\plot 11.781 19.291 11.718 19.406 /
\plot 11.718 19.406 11.652 19.516 /
\plot 11.652 19.516 11.589 19.622 /
\plot 11.589 19.622 11.525 19.719 /
\plot 11.525 19.719 11.462 19.814 /
\plot 11.462 19.814 11.400 19.903 /
\plot 11.400 19.903 11.337 19.988 /
\plot 11.337 19.988 11.278 20.068 /
\plot 11.278 20.068 11.216 20.146 /
\plot 11.216 20.146 11.157 20.221 /
\plot 11.157 20.221 11.098 20.290 /
\plot 11.098 20.290 11.038 20.360 /
\plot 11.038 20.360 10.981 20.426 /
\plot 10.981 20.426 10.924 20.489 /
\plot 10.924 20.489 10.869 20.551 /
\plot 10.869 20.551 10.816 20.608 /
\plot 10.816 20.608 10.765 20.663 /
\plot 10.765 20.663 10.717 20.714 /
\plot 10.717 20.714 10.672 20.758 /
\plot 10.672 20.758 10.632 20.800 /
\plot 10.632 20.800 10.596 20.836 /
\plot 10.596 20.836 10.564 20.868 /
\plot 10.564 20.868 10.539 20.896 /
\plot 10.539 20.896 10.518 20.915 /
\plot 10.518 20.915 10.501 20.932 /
\plot 10.501 20.932 10.490 20.942 /
\plot 10.490 20.942 10.484 20.949 /
\plot 10.484 20.949 10.480 20.953 /
\plot 10.480 20.953 10.478 20.955 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 12.383 17.145 12.385 17.143 /
\plot 12.385 17.143 12.389 17.141 /
\plot 12.389 17.141 12.397 17.134 /
\plot 12.397 17.134 12.408 17.124 /
\plot 12.408 17.124 12.425 17.111 /
\plot 12.425 17.111 12.448 17.094 /
\plot 12.448 17.094 12.474 17.075 /
\plot 12.474 17.075 12.505 17.052 /
\plot 12.505 17.052 12.541 17.026 /
\plot 12.541 17.026 12.579 17.001 /
\plot 12.579 17.001 12.622 16.974 /
\plot 12.622 16.974 12.664 16.948 /
\plot 12.664 16.948 12.711 16.923 /
\plot 12.711 16.923 12.757 16.897 /
\plot 12.757 16.897 12.804 16.878 /
\plot 12.804 16.878 12.850 16.861 /
\plot 12.850 16.861 12.897 16.847 /
\plot 12.897 16.847 12.946 16.840 /
\plot 12.946 16.840 12.992 16.838 /
\plot 12.992 16.838 13.037 16.842 /
\plot 13.037 16.842 13.083 16.853 /
\plot 13.083 16.853 13.130 16.874 /
\plot 13.130 16.874 13.174 16.906 /
\plot 13.174 16.906 13.216 16.946 /
\plot 13.216 16.946 13.259 17.001 /
\plot 13.259 17.001 13.299 17.067 /
\plot 13.299 17.067 13.335 17.145 /
\plot 13.335 17.145 13.363 17.223 /
\plot 13.363 17.223 13.386 17.310 /
\plot 13.386 17.310 13.407 17.399 /
\plot 13.407 17.399 13.424 17.494 /
\plot 13.424 17.494 13.437 17.590 /
\plot 13.437 17.590 13.445 17.689 /
\plot 13.445 17.689 13.451 17.788 /
\plot 13.451 17.788 13.456 17.888 /
\plot 13.456 17.888 13.458 17.990 /
\putrule from 13.458 17.990 to 13.458 18.091
\plot 13.458 18.091 13.456 18.195 /
\plot 13.456 18.195 13.451 18.296 /
\plot 13.451 18.296 13.447 18.400 /
\plot 13.447 18.400 13.441 18.504 /
\plot 13.441 18.504 13.432 18.605 /
\plot 13.432 18.605 13.424 18.707 /
\plot 13.424 18.707 13.415 18.807 /
\plot 13.415 18.807 13.407 18.904 /
\plot 13.407 18.904 13.396 18.997 /
\plot 13.396 18.997 13.388 19.084 /
\plot 13.388 19.084 13.379 19.166 /
\plot 13.379 19.166 13.371 19.241 /
\plot 13.371 19.241 13.363 19.308 /
\plot 13.363 19.308 13.356 19.365 /
\plot 13.356 19.365 13.350 19.414 /
\plot 13.350 19.414 13.343 19.452 /
\plot 13.343 19.452 13.341 19.482 /
\plot 13.341 19.482 13.335 19.526 /
%
% arrow head
%
\plot 13.558 19.045 13.335 19.526 13.256 19.002 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 7.620 19.526 to 7.620 19.522
\plot 7.620 19.522 7.618 19.516 /
\putrule from 7.618 19.516 to 7.618 19.503
\plot 7.618 19.503 7.614 19.482 /
\plot 7.614 19.482 7.612 19.452 /
\plot 7.612 19.452 7.605 19.414 /
\plot 7.605 19.414 7.599 19.365 /
\plot 7.599 19.365 7.592 19.308 /
\plot 7.592 19.308 7.584 19.241 /
\plot 7.584 19.241 7.576 19.166 /
\plot 7.576 19.166 7.567 19.084 /
\plot 7.567 19.084 7.559 18.997 /
\plot 7.559 18.997 7.548 18.904 /
\plot 7.548 18.904 7.540 18.807 /
\plot 7.540 18.807 7.531 18.707 /
\plot 7.531 18.707 7.523 18.605 /
\plot 7.523 18.605 7.514 18.504 /
\plot 7.514 18.504 7.508 18.400 /
\plot 7.508 18.400 7.504 18.296 /
\plot 7.504 18.296 7.499 18.195 /
\plot 7.499 18.195 7.497 18.091 /
\putrule from 7.497 18.091 to 7.497 17.990
\plot 7.497 17.990 7.499 17.888 /
\plot 7.499 17.888 7.504 17.788 /
\plot 7.504 17.788 7.510 17.689 /
\plot 7.510 17.689 7.518 17.590 /
\plot 7.518 17.590 7.531 17.494 /
\plot 7.531 17.494 7.548 17.399 /
\plot 7.548 17.399 7.569 17.310 /
\plot 7.569 17.310 7.592 17.223 /
\plot 7.592 17.223 7.620 17.145 /
\plot 7.620 17.145 7.656 17.067 /
\plot 7.656 17.067 7.696 17.001 /
\plot 7.696 17.001 7.739 16.946 /
\plot 7.739 16.946 7.781 16.906 /
\plot 7.781 16.906 7.825 16.874 /
\plot 7.825 16.874 7.872 16.853 /
\plot 7.872 16.853 7.918 16.842 /
\plot 7.918 16.842 7.963 16.838 /
\plot 7.963 16.838 8.009 16.840 /
\plot 8.009 16.840 8.058 16.847 /
\plot 8.058 16.847 8.105 16.861 /
\plot 8.105 16.861 8.151 16.878 /
\plot 8.151 16.878 8.198 16.897 /
\plot 8.198 16.897 8.244 16.923 /
\plot 8.244 16.923 8.291 16.948 /
\plot 8.291 16.948 8.333 16.974 /
\plot 8.333 16.974 8.376 17.001 /
\plot 8.376 17.001 8.414 17.026 /
\plot 8.414 17.026 8.450 17.052 /
\plot 8.450 17.052 8.481 17.075 /
\plot 8.481 17.075 8.507 17.094 /
\plot 8.507 17.094 8.530 17.111 /
\plot 8.530 17.111 8.547 17.124 /
\plot 8.547 17.124 8.572 17.145 /
%
% arrow head
%
\plot 8.280 16.703 8.572 17.145 8.085 16.937 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 8.572 17.145 10.478 15.716 /
%
% arrow head
%
\plot 9.980 15.899 10.478 15.716 10.163 16.143 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 10.478 15.716 12.383 17.145 /
%
% arrow head
%
\plot 12.068 16.718 12.383 17.145 11.885 16.962 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=3pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'162}}})
{\color[rgb]{0,0,1}\putrule from 7.620 19.526 to 7.620 19.522
\plot 7.620 19.522 7.618 19.516 /
\putrule from 7.618 19.516 to 7.618 19.503
\plot 7.618 19.503 7.614 19.482 /
\plot 7.614 19.482 7.612 19.452 /
\plot 7.612 19.452 7.605 19.414 /
\plot 7.605 19.414 7.599 19.365 /
\plot 7.599 19.365 7.592 19.308 /
\plot 7.592 19.308 7.584 19.241 /
\plot 7.584 19.241 7.576 19.166 /
\plot 7.576 19.166 7.567 19.084 /
\plot 7.567 19.084 7.559 18.997 /
\plot 7.559 18.997 7.548 18.904 /
\plot 7.548 18.904 7.540 18.807 /
\plot 7.540 18.807 7.531 18.707 /
\plot 7.531 18.707 7.523 18.605 /
\plot 7.523 18.605 7.514 18.504 /
\plot 7.514 18.504 7.508 18.400 /
\plot 7.508 18.400 7.504 18.296 /
\plot 7.504 18.296 7.499 18.195 /
\plot 7.499 18.195 7.497 18.091 /
\putrule from 7.497 18.091 to 7.497 17.990
\plot 7.497 17.990 7.499 17.888 /
\plot 7.499 17.888 7.504 17.788 /
\plot 7.504 17.788 7.510 17.689 /
\plot 7.510 17.689 7.518 17.590 /
\plot 7.518 17.590 7.531 17.494 /
\plot 7.531 17.494 7.548 17.399 /
\plot 7.548 17.399 7.569 17.310 /
\plot 7.569 17.310 7.592 17.223 /
\plot 7.592 17.223 7.620 17.145 /
\plot 7.620 17.145 7.656 17.067 /
\plot 7.656 17.067 7.696 17.001 /
\plot 7.696 17.001 7.739 16.946 /
\plot 7.739 16.946 7.781 16.906 /
\plot 7.781 16.906 7.825 16.874 /
\plot 7.825 16.874 7.872 16.853 /
\plot 7.872 16.853 7.918 16.842 /
\plot 7.918 16.842 7.963 16.838 /
\plot 7.963 16.838 8.009 16.840 /
\plot 8.009 16.840 8.058 16.847 /
\plot 8.058 16.847 8.105 16.861 /
\plot 8.105 16.861 8.151 16.878 /
\plot 8.151 16.878 8.198 16.897 /
\plot 8.198 16.897 8.244 16.923 /
\plot 8.244 16.923 8.291 16.948 /
\plot 8.291 16.948 8.333 16.974 /
\plot 8.333 16.974 8.376 17.001 /
\plot 8.376 17.001 8.414 17.026 /
\plot 8.414 17.026 8.450 17.052 /
\plot 8.450 17.052 8.481 17.075 /
\plot 8.481 17.075 8.507 17.094 /
\plot 8.507 17.094 8.530 17.111 /
\plot 8.530 17.111 8.547 17.124 /
\plot 8.547 17.124 8.558 17.134 /
\plot 8.558 17.134 8.566 17.141 /
\plot 8.566 17.141 8.570 17.143 /
\plot 8.570 17.143 8.572 17.145 /
}%
%
% Fig POLYLINE object
%
\linethickness=3pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'162}}})
{\color[rgb]{0,0,1}\plot 8.572 17.145 8.575 17.147 /
\plot 8.575 17.147 8.581 17.149 /
\plot 8.581 17.149 8.594 17.153 /
\plot 8.594 17.153 8.611 17.162 /
\plot 8.611 17.162 8.634 17.173 /
\plot 8.634 17.173 8.666 17.187 /
\plot 8.666 17.187 8.702 17.204 /
\plot 8.702 17.204 8.746 17.225 /
\plot 8.746 17.225 8.795 17.249 /
\plot 8.795 17.249 8.848 17.276 /
\plot 8.848 17.276 8.907 17.306 /
\plot 8.907 17.306 8.966 17.338 /
\plot 8.966 17.338 9.028 17.374 /
\plot 9.028 17.374 9.093 17.412 /
\plot 9.093 17.412 9.159 17.452 /
\plot 9.159 17.452 9.224 17.494 /
\plot 9.224 17.494 9.292 17.541 /
\plot 9.292 17.541 9.362 17.592 /
\plot 9.362 17.592 9.432 17.647 /
\plot 9.432 17.647 9.504 17.706 /
\plot 9.504 17.706 9.578 17.772 /
\plot 9.578 17.772 9.652 17.844 /
\plot 9.652 17.844 9.728 17.924 /
\plot 9.728 17.924 9.807 18.009 /
\plot 9.807 18.009 9.881 18.098 /
\plot 9.881 18.098 9.950 18.191 /
\plot 9.950 18.191 10.016 18.282 /
\plot 10.016 18.282 10.075 18.373 /
\plot 10.075 18.373 10.128 18.459 /
\plot 10.128 18.459 10.175 18.544 /
\plot 10.175 18.544 10.215 18.625 /
\plot 10.215 18.625 10.251 18.703 /
\plot 10.251 18.703 10.283 18.779 /
\plot 10.283 18.779 10.310 18.853 /
\plot 10.310 18.853 10.336 18.923 /
\plot 10.336 18.923 10.357 18.993 /
\plot 10.357 18.993 10.378 19.058 /
\plot 10.378 19.058 10.395 19.124 /
\plot 10.395 19.124 10.410 19.188 /
\plot 10.410 19.188 10.425 19.245 /
\plot 10.425 19.245 10.435 19.300 /
\plot 10.435 19.300 10.446 19.351 /
\plot 10.446 19.351 10.454 19.395 /
\plot 10.454 19.395 10.463 19.433 /
\plot 10.463 19.433 10.467 19.465 /
\plot 10.467 19.465 10.471 19.488 /
\plot 10.471 19.488 10.475 19.505 /
\putrule from 10.475 19.505 to 10.475 19.518
\plot 10.475 19.518 10.478 19.524 /
\putrule from 10.478 19.524 to 10.478 19.526
}%
%
% Fig POLYLINE object
%
\linethickness=3pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'162}}})
{\color[rgb]{0,0,1}\putrule from 10.478 19.526 to 10.478 20.955
}%
%
% Fig POLYLINE object
%
\linethickness=3pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'162}}})
{\color[rgb]{0,0,1}\plot 10.478 20.955 10.480 20.957 /
\plot 10.480 20.957 10.486 20.959 /
\plot 10.486 20.959 10.494 20.963 /
\plot 10.494 20.963 10.509 20.970 /
\plot 10.509 20.970 10.530 20.980 /
\plot 10.530 20.980 10.558 20.991 /
\plot 10.558 20.991 10.592 21.006 /
\plot 10.592 21.006 10.632 21.021 /
\plot 10.632 21.021 10.676 21.038 /
\plot 10.676 21.038 10.725 21.054 /
\plot 10.725 21.054 10.778 21.074 /
\plot 10.778 21.074 10.835 21.088 /
\plot 10.835 21.088 10.894 21.103 /
\plot 10.894 21.103 10.958 21.118 /
\plot 10.958 21.118 11.024 21.129 /
\plot 11.024 21.129 11.091 21.135 /
\plot 11.091 21.135 11.163 21.139 /
\putrule from 11.163 21.139 to 11.240 21.139
\plot 11.240 21.139 11.318 21.133 /
\plot 11.318 21.133 11.402 21.122 /
\plot 11.402 21.122 11.494 21.105 /
\plot 11.494 21.105 11.589 21.080 /
\plot 11.589 21.080 11.690 21.048 /
\plot 11.690 21.048 11.796 21.006 /
\plot 11.796 21.006 11.906 20.955 /
\plot 11.906 20.955 12.002 20.904 /
\plot 12.002 20.904 12.095 20.849 /
\plot 12.095 20.849 12.184 20.792 /
\plot 12.184 20.792 12.268 20.731 /
\plot 12.268 20.731 12.351 20.669 /
\plot 12.351 20.669 12.427 20.606 /
\plot 12.427 20.606 12.499 20.540 /
\plot 12.499 20.540 12.569 20.477 /
\plot 12.569 20.477 12.634 20.411 /
\plot 12.634 20.411 12.698 20.345 /
\plot 12.698 20.345 12.757 20.280 /
\plot 12.757 20.280 12.816 20.214 /
\plot 12.816 20.214 12.871 20.149 /
\plot 12.871 20.149 12.926 20.083 /
\plot 12.926 20.083 12.977 20.017 /
\plot 12.977 20.017 13.028 19.954 /
\plot 13.028 19.954 13.075 19.892 /
\plot 13.075 19.892 13.117 19.833 /
\plot 13.117 19.833 13.159 19.778 /
\plot 13.159 19.778 13.195 19.727 /
\plot 13.195 19.727 13.227 19.681 /
\plot 13.227 19.681 13.257 19.641 /
\plot 13.257 19.641 13.280 19.607 /
\plot 13.280 19.607 13.299 19.579 /
\plot 13.299 19.579 13.314 19.558 /
\plot 13.314 19.558 13.324 19.543 /
\plot 13.324 19.543 13.331 19.535 /
\plot 13.331 19.535 13.333 19.528 /
\plot 13.333 19.528 13.335 19.526 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}x}%
} [lB] at 6.905 19.526
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}y}%
} [lB] at 13.811 19.526
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}a}%
} [lB] at 8.333 16.432
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}b}%
} [lB] at 10.357 14.764
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}c}%
} [lB] at 12.501 16.432
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}d}%
} [lB] at 10.001 19.526
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}e}%
} [lB] at 10.478 21.552
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}IV}%
} [lB] at 7.857 20.479
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}VI}%
} [lB] at 6.905 17.503
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}III}%
} [lB] at 9.165 15.955
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}II}%
} [lB] at 11.430 15.955
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}V}%
} [lB] at 13.572 17.742
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}III}%
} [lB] at 9.762 17.503
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}V}%
} [lB] at 10.835 17.503
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}I}%
} [lB] at 9.525 19.289
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}I}%
} [lB] at 11.309 19.289
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}IV}%
} [lB] at 12.501 20.718
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}4}%
} [lB] at 8.452 20.955
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}1}%
} [lB] at 7.144 18.098
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}2}%
} [lB] at 9.644 16.432
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}2}%
} [lB] at 10.954 16.432
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}1}%
} [lB] at 9.049 19.647
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}0}%
} [lB] at 11.667 19.645
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}2}%
} [lB] at 9.404 17.979
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}3}%
} [lB] at 11.311 18.098
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}5}%
} [lB] at 10.120 20.123
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}V}%
} [lB] at 10.596 20.123
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}0}%
} [lB] at 12.143 21.076
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}5}%
} [lB] at 13.572 18.337
\linethickness=0pt
\putrectangle corners at 6.873 22.149 and 13.843 14.732
\endpicture}
\end{center}
\caption{\label{cap:nenasycena-cesta}$f$-nenasycená cesta v síti}
\end{figure}
\end{example*}
\begin{thm}
Tok $f$ v síti $N=(D,x_{0},y_{0},c)$ je maximální tehdy a jen tehdy,
když neexistuje $f$-nenasycená cesta končící ve spotřebiči $y_{0}$.
\end{thm}
\begin{proof}
$\boxed{{\Rightarrow:}}$
Důkaz této implikace bude v podstatě shrnutím úvah provedených v minulém
příkladu. Postupujme sporem: nechť existuje $f$-nenasycená cesta
$P$ končící v $y_{0}$. Potom definujeme zobrazení $\tilde{f}$ takto:
\begin{itemize}
\item $\forall a\in A,a\notin P$ položíme $\tilde{f}(a)=f(a)$,
\item $\forall a\in A,a\in P$, která je po cestě $P$ orientována ve směru
z $x_{0}$ do $y_{0}$, položíme $\tilde{f}(a)=f(a)+\iota(P)$,
\item $\forall a\in A,a\in P$, která je po cestě $P$ orientována ve směru
z $y_{0}$ do $x_{0}$, položíme $\tilde{f}(a)=f(a)-\iota(P)$.
\end{itemize}
Potom je opět $\left(\forall a\in A\right)\left(0\leq\tilde{f}(a)\leq c(a)\right)$
a rovněž $\left(\forall v\in I\right)\left(\sum\limits _{(u,v)\in A}\tilde{f}\left((u,v)\right)=\sum\limits _{(v,u)\in A}\tilde{f}\left((v,u)\right)\right)$,
takže $\tilde{f}$ je tok a pro jeho hodnotu platí \[
\val\tilde{f}=\val f+\iota(P)>\val f,\]
což je spor s maximalitou toku $f$.
$\boxed{{\Leftarrow:}}$
Definujme\[
M=\left\{ \left.v\in V\right|\exists f\textrm{-nenasycená cesta z }x_{0}\textrm{ do }v\right\} .\]
Potom $x_{0}\in M$ a z předpokladu platí $y_{0}\notin M$. $(M,\bar{M})$
je tedy řez v síti $N$. Potom na každé hraně $a=(u,v)\in A,u\in M,v\in\bar{M}$
musí z definice $M$ platit $\iota(a)=0$, neboli $f(a)=c(a)$, jinak
by totiž $v\in M$. Stejně tak i na každé hraně $a=(u,v)\in A,u\in\bar{M},v\in M$
musí být $\iota(a)=0$, což v tomto případě odpovídá (z definice $\iota(a)$)
rovnosti $f(a)=0$. Proto platí\[
c\left((M,\bar{M)}\right)=\sum_{\begin{matrix}{\scriptstyle (u,v)\in A}\\
{\scriptstyle u\in M,v\in\bar{M}}\end{matrix}}c\left((u,v)\right)=f^{+}(M)=f^{+}(x_{0})=\val f.\]
Našli jsme tedy řez, pro nějž je $c\left((M,\bar{M)}\right)=\val f$,
a tedy podle poznámky \ref{rem:max-rez-min-tok} je $f$ maximální
tok.
\end{proof}
\begin{rem*}
Celočíselnost kapacit hran (tj. funkce $c$) zaručuje, že algoritmus
hledání maximálního toku fungující na principu hledání nenasycených
cest je finitní. Pokud totiž začíná s tokem $f(a)=0$ pro každé $a\in A$,
tak v každém kroku zvedne hodnotu toku o $\iota(P)\geq1$, přičemž
kapacita minimálního řezu, které nakonec hodnota toku $f$ dosáhne,
je rovněž konečné přirozené číslo. Navíc $\val f\in\N_{0}$ v každém
kroku.
\end{rem*}
\begin{example*}
Na obrázku \ref{cap:alg-nenasyc-cest} je vidět, že algoritmus nemusí
být příliš efektivní. Pokud bude střídavě volit $f$-nenasycené cesty
$P_{1}$ a $P_{2}$, zvýší v každém kroku hodnotu toku pouze o $1$.
(čísla $m$ a $1$ u jednotlivých hran udávají jejich kapacity)%
\begin{figure}
\begin{center}
%Title: alg_nenasyc_cest.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:45:28 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.144 24.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 4.286 23.813
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 4.286 25.718
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 1.429 24.765
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{1,0,0}\plot 1.547 24.528 4.523 23.457 /
\putrule from 4.523 23.457 to 4.523 25.957
\plot 4.523 25.957 7.144 25.004 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,1}\plot 1.784 24.765 4.047 25.241 /
\putrule from 4.047 25.241 to 4.047 24.170
\plot 4.047 24.170 6.428 24.765 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 4.286 25.718 to 4.286 23.813
%
% arrow head
%
\plot 4.134 24.320 4.286 23.813 4.439 24.320 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 4.286 23.813 7.144 24.765 /
%
% arrow head
%
\plot 6.710 24.460 7.144 24.765 6.614 24.749 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 1.429 24.765 4.286 23.813 /
%
% arrow head
%
\plot 3.756 23.829 4.286 23.813 3.853 24.118 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 4.286 25.718 7.144 24.765 /
%
% arrow head
%
\plot 6.614 24.781 7.144 24.765 6.710 25.070 /
%
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 1.429 24.765 4.286 25.718 /
%
% arrow head
%
\plot 3.853 25.412 4.286 25.718 3.756 25.701 /
%
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}%
} [lB] at 4.286 24.765
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}m}%
} [lB] at 5.715 25.480
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}m}%
} [lB] at 5.713 23.815
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}m}%
} [lB] at 2.381 23.813
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}m}%
} [lB] at 2.379 25.480
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{1,0,0}$P_{2}$}%
} [lB] at 4.405 22.981
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,1}$P_{1}$}%
} [lB] at 3.334 24.646
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$y_{0}$}%
} [lB] at 7.620 24.646
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_{0}$}%
} [lB] at 0.476 24.646
\linethickness=0pt
\putrectangle corners at 0.444 26.077 and 7.652 22.782
\endpicture}
\end{center}
\caption{\label{cap:alg-nenasyc-cest}Algoritmus hledání maximálního toku
pomocí $f$-nenasycených cest}
\end{figure}
\end{example*}
\begin{rem*}
Algoritmus hledání maximálního toku pomocí $f$-nenasycených cest
lze použít k nalezení perfektního párování v bipartitiním grafu $G=(V_{1}\cup V_{2},E)$.
Tomuto grafu přiřadíme síť $N=(D,x_{0},y_{0},c)$ definovanou takto:
\begin{itemize}
\item $D=(\{ x_{0},y_{0}\}\cup V,A)$, kde
\item $A=\left\{ \left.(x_{0},v)\right|v\in V_{1}\right\} \cup\left\{ \left.(u,v)\right|u\in V_{1}\wedge v\in V_{2}\wedge\{ u,v\}\in E\right\} \cup\left\{ \left.(v,y_{0})\right|v\in V_{2}\right\} $
a
\item $\left(\forall a\in A\right)\left(c(a)=1\right)$.
\end{itemize}
To znamená, že přidáme vrcholy $x_{0}$ a $y_{0}$, z $x_{0}$ vedeme
hrany do všech vrcholů ve $V_{1}$, mezi $V_{1}$ a $V_{2}$ orientujeme
existující hrany ve směru do $V_{2}$ a ze všech vrcholů z $V_{2}$
vedeme hrany do $y_{0}$. Všechny hrany mají jednotkovou kapacitu.
Najděme nyní maximální tok pomocí našeho algoritmu. Potom $\left(\forall a\in A\right)\left(f(a)\in\{0,1\}\right)$,
tj. neexistují hrany s neceločíselným tokem%
\footnote{Obecně lze najít maximální tok i s neceločíselnými hodnotami funkce
$f$. Proto je důležité, že používáme algoritmus hledání $f$-nenasycených
cest!%
}. Označme\[
M=\left\{ \left.\{ u,v\}\in E\right|f(\underbrace{(u,v)}_{\in A})=1\right\} .\]
Potom $M$ je maximální párování: Především se zřejmě jedná o párování,
jinak by byla porušena druhá podmínka v definici toku \ref{def:definice-toku}.
Například z žádného $v\in V_{1}$ nemohou vycházet dvě hrany, pro
něž je $f=1$, protože do $v$ může přitékat maximálně jednotkový
tok (z $x_{0}$). Dále platí, že $\val f=\# M$, z čehož už plyne,
že párování $M$ je maximální. V opačném případě by totiž existovalo
párování $M'$, $\# M'>\# M$ a k němu by bylo možné najít tok $f'$,
pro který $\# M'=\val f'>\val f=\# M$, a tok $f$ by nebyl maximální.
\end{rem*}
