Application to Network Flow

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\npnoround }[0]{\nprounddigits {-1}} \newcommand {\npnoroundexp }[0]{\nproundexpdigits {-1}} \newcommand {\npunitcommand }[1]{\ensuremath {\mathrm {#1}}} \newcommand {\tdplotsinandcos }[3]{\pgfmathsetmacro {#1}{sin(#3)}\pgfmathsetmacro {#2}{cos(#3)}} \newcommand {\tdplotmult }[3]{\pgfmathsetmacro {#1}{#2*#3}} \newcommand {\tdplotdiv }[3]{\pgfmathsetmacro {#1}{#2/#3}} \newcommand {\tdplotcheckdiff }[5]{\par \par \pgfmathparse { abs(#2 -#1)<#3 } \par \ifthenelse {\equal {\pgfmathresult }{1}}{#4}{#5} } \newcommand {\tdplotsetmaincoords }[2]{\pgfmathsetmacro {\tdplotmaintheta }{#1} \pgfmathsetmacro {\tdplotmainphi }{#2} \tdplotcalctransformmainscreen \tikzset {tdplot_main_coords/.style={x={(\raarot cm,\rbarot cm)},y={(\rabrot cm,\rbbrot cm)},z={(\racrot cm,\rbcrot cm)}}}} \newcommand {\tdplotcalctransformmainscreen }[0]{\tdplotsinandcos {\sintheta }{\costheta }{\tdplotmaintheta }\tdplotsinandcos {\sinphi }{\cosphi }{\tdplotmainphi }\tdplotmult {\stsp }{\sintheta }{\sinphi }\tdplotmult {\stcp }{\sintheta }{\cosphi }\tdplotmult {\ctsp }{\costheta }{\sinphi }\tdplotmult {\ctcp }{\costheta }{\cosphi }\pgfmathsetmacro {\raarot }{\cosphi }\pgfmathsetmacro {\rabrot }{\sinphi }\pgfmathsetmacro {\racrot }{0}\pgfmathsetmacro {\rbarot }{-\ctsp }\pgfmathsetmacro {\rbbrot }{\ctcp }\pgfmathsetmacro {\rbcrot }{\sintheta }\pgfmathsetmacro {\rcarot }{\stsp }\pgfmathsetmacro {\rcbrot }{-\stcp }\pgfmathsetmacro {\rccrot }{\costheta }} \newcommand {\tdplotcalctransformrotmain }[0]{\tdplotsinandcos {\sinalpha }{\cosalpha }{\tdplotalpha } \tdplotsinandcos {\sinbeta }{\cosbeta }{\tdplotbeta } \tdplotsinandcos {\singamma }{\cosgamma }{\tdplotgamma } \tdplotmult {\sasb }{\sinalpha }{\sinbeta } \tdplotmult {\sbsg }{\sinbeta }{\singamma } \tdplotmult {\sasg }{\sinalpha }{\singamma } \tdplotmult {\sasbsg }{\sasb }{\singamma } \tdplotmult {\sacb }{\sinalpha }{\cosbeta } \tdplotmult {\sacg }{\sinalpha }{\cosgamma } \tdplotmult {\sbcg }{\sinbeta }{\cosgamma } \tdplotmult {\sacbsg }{\sacb }{\singamma } \tdplotmult {\sacbcg }{\sacb }{\cosgamma } \tdplotmult {\casb }{\cosalpha }{\sinbeta } \tdplotmult {\cacb }{\cosalpha }{\cosbeta } \tdplotmult {\cacg }{\cosalpha }{\cosgamma } \tdplotmult {\casg }{\cosalpha }{\singamma } \tdplotmult {\cacbsg }{\cacb }{\singamma } \tdplotmult {\cacbcg }{\cacb }{\cosgamma } \pgfmathsetmacro {\raaeul }{\cacbcg -\sasg } \pgfmathsetmacro {\rabeul }{-\cacbsg -\sacg } \pgfmathsetmacro {\raceul }{\casb } \pgfmathsetmacro {\rbaeul }{\sacbcg + \casg } \pgfmathsetmacro {\rbbeul }{-\sacbsg + \cacg } \pgfmathsetmacro {\rbceul }{\sasb } \pgfmathsetmacro {\rcaeul }{-\sbcg } \pgfmathsetmacro {\rcbeul }{\sbsg } \pgfmathsetmacro {\rcceul }{\cosbeta } } \newcommand {\tdplotcalctransformmainrot }[0]{\tdplotsinandcos {\sinalpha }{\cosalpha }{\tdplotalpha } \tdplotsinandcos {\sinbeta }{\cosbeta }{\tdplotbeta } \tdplotsinandcos {\singamma }{\cosgamma }{\tdplotgamma } \tdplotmult {\sasb }{\sinalpha }{\sinbeta } \tdplotmult {\sbsg }{\sinbeta }{\singamma } \tdplotmult {\sasg }{\sinalpha }{\singamma } \tdplotmult {\sasbsg }{\sasb }{\singamma } \tdplotmult {\sacb }{\sinalpha }{\cosbeta } \tdplotmult {\sacg }{\sinalpha }{\cosgamma } \tdplotmult {\sbcg }{\sinbeta }{\cosgamma } \tdplotmult {\sacbsg }{\sacb }{\singamma } \tdplotmult {\sacbcg }{\sacb }{\cosgamma } \tdplotmult {\casb }{\cosalpha }{\sinbeta } \tdplotmult {\cacb }{\cosalpha }{\cosbeta } \tdplotmult {\cacg }{\cosalpha }{\cosgamma } \tdplotmult {\casg }{\cosalpha }{\singamma } \tdplotmult {\cacbsg }{\cacb }{\singamma } \tdplotmult {\cacbcg }{\cacb }{\cosgamma } \pgfmathsetmacro {\raaeul }{\cacbcg -\sasg } \pgfmathsetmacro {\rabeul }{\sacbcg + \casg } \pgfmathsetmacro {\raceul }{-\sbcg } \pgfmathsetmacro {\rbaeul }{-\cacbsg -\sacg } \pgfmathsetmacro {\rbbeul }{-\sacbsg + \cacg } \pgfmathsetmacro {\rbceul }{\sbsg } \pgfmathsetmacro {\rcaeul }{\casb } \pgfmathsetmacro {\rcbeul }{\sasb } \pgfmathsetmacro {\rcceul }{\cosbeta } } \newcommand {\tdplottransformmainrot }[3]{\tdplotcalctransformmainrot \par \pgfmathsetmacro {\tdplotresx }{\raaeul * #1 + \rabeul * #2 + \raceul * #3} \pgfmathsetmacro {\tdplotresy }{\rbaeul * #1 + \rbbeul * #2 + \rbceul * #3} \pgfmathsetmacro {\tdplotresz }{\rcaeul * #1 + \rcbeul * #2 + \rcceul * #3} } \newcommand {\tdplottransformrotmain }[3]{\tdplotcalctransformrotmain \par \pgfmathsetmacro {\tdplotresx }{\raaeul * #1 + \rabeul * #2 + \raceul * #3} \pgfmathsetmacro {\tdplotresy }{\rbaeul * #1 + \rbbeul * #2 + \rbceul * #3} \pgfmathsetmacro {\tdplotresz }{\rcaeul * #1 + \rcbeul * #2 + \rcceul * #3} } \newcommand {\tdplottransformmainscreen }[3]{\tdplotcalctransformmainscreen \par \pgfmathsetmacro {\tdplotresx }{\raarot * #1 + \rabrot * #2 + \racrot * #3} \pgfmathsetmacro {\tdplotresy }{\rbarot * #1 + \rbbrot * #2 + \rbcrot * #3} } \newcommand {\tdplotsetrotatedcoords }[3]{\pgfmathsetmacro {\tdplotalpha }{#1} \pgfmathsetmacro {\tdplotbeta }{#2} \pgfmathsetmacro {\tdplotgamma }{#3} \tdplotcalctransformrotmain \par \tdplotmult {\raaeaa }{\raarot }{\raaeul } \tdplotmult {\rabeba }{\rabrot }{\rbaeul } \tdplotmult {\raceca }{\racrot }{\rcaeul } \tdplotmult {\raaeab }{\raarot }{\rabeul } \tdplotmult {\rabebb }{\rabrot }{\rbbeul } \tdplotmult {\racecb }{\racrot }{\rcbeul } \tdplotmult {\raaeac }{\raarot }{\raceul } \tdplotmult {\rabebc }{\rabrot }{\rbceul } \tdplotmult {\racecc }{\racrot }{\rcceul } \tdplotmult {\rbaeaa }{\rbarot }{\raaeul } \tdplotmult {\rbbeba }{\rbbrot }{\rbaeul } \tdplotmult {\rbceca }{\rbcrot }{\rcaeul } \tdplotmult {\rbaeab }{\rbarot }{\rabeul } \tdplotmult {\rbbebb }{\rbbrot }{\rbbeul } \tdplotmult {\rbcecb }{\rbcrot }{\rcbeul } \tdplotmult {\rbaeac }{\rbarot }{\raceul } \tdplotmult {\rbbebc }{\rbbrot }{\rbceul } \tdplotmult {\rbcecc }{\rbcrot }{\rcceul } \pgfmathsetmacro {\raarc }{\raaeaa + \rabeba + \raceca } \pgfmathsetmacro {\rabrc }{\raaeab + \rabebb + \racecb } \pgfmathsetmacro {\racrc }{\raaeac + \rabebc + \racecc } \pgfmathsetmacro {\rbarc }{\rbaeaa + \rbbeba + \rbceca } \pgfmathsetmacro {\rbbrc }{\rbaeab + \rbbebb + \rbcecb } \pgfmathsetmacro {\rbcrc }{\rbaeac + \rbbebc + \rbcecc } \tikzset {tdplot_rotated_coords/.append style={x={(\raarc cm,\rbarc cm)},y={(\rabrc cm,\rbbrc cm)},z={(\racrc cm,\rbcrc cm)}}}} \newcommand {\tdplotsetrotatedcoordsorigin }[1]{\tikzset {tdplot_rotated_coords/.append style={shift=#1}}} \newcommand {\tdplotresetrotatedcoordsorigin }[0]{\tikzset {tdplot_rotated_coords/.append style={shift={(0,0,0)}}}} \newcommand {\tdplotsetthetaplanecoords }[1]{\tdplotresetrotatedcoordsorigin \tdplotsetrotatedcoords {270 + #1}{270}{0}} \newcommand {\tdplotsetrotatedthetaplanecoords }[1]{\tdplotsetrotatedcoords {\tdplotalpha }{\tdplotbeta }{\tdplotgamma + #1}\tikzset {tdplot_rotated_coords/.append style={y={(\raarc cm,\rbarc cm)},z={(\rabrc cm,\rbbrc cm)},x={(\racrc cm,\rbcrc cm)}}}} \newcommand {\tdplotsetcoord }[4]{\tdplotsinandcos {\sinthetavec }{\costhetavec }{#3}\tdplotsinandcos {\sinphivec }{\cosphivec }{#4}\tdplotmult {\stcpv }{\sinthetavec }{\cosphivec }\tdplotmult {\stspv }{\sinthetavec }{\sinphivec }\coordinate (#1) at ($#2*(\stcpv ,\stspv ,\costhetavec )$); \coordinate (#1xy) at ($#2*(\stcpv ,\stspv ,0)$); \coordinate (#1xz) at ($#2*(\stcpv ,0,\costhetavec )$); \coordinate (#1yz) at ($#2*(0,\stspv ,\costhetavec )$); \coordinate (#1x) at ($#2*(\stcpv ,0,0)$); \coordinate (#1y) at ($#2*(0,\stspv ,0)$); \coordinate (#1z) at ($#2*(0,0,\costhetavec )$); } \newcommand {\tdplotsimplesetcoord }[4]{\tdplotsinandcos {\sinthetavec }{\costhetavec }{#3}\tdplotsinandcos {\sinphivec }{\cosphivec }{#4}\tdplotmult {\stcpv }{\sinthetavec }{\cosphivec }\tdplotmult {\stspv }{\sinthetavec }{\sinphivec }\coordinate (#1) at ($#2*(\stcpv ,\stspv ,\costhetavec )$); } \newcommand {\tdplotsetpolarplotrange }[4]{\pgfmathsetmacro {\tdplotlowerphi }{#3} \pgfmathsetmacro {\tdplotupperphi }{#4} \pgfmathsetmacro {\tdplotlowertheta }{#1} \pgfmathsetmacro {\tdplotuppertheta }{#2} } \newcommand {\tdplotresetpolarplotrange }[0]{\pgfmathsetmacro {\tdplotlowerphi }{0} \pgfmathsetmacro {\tdplotupperphi }{360} \pgfmathsetmacro {\tdplotlowertheta }{0} \pgfmathsetmacro {\tdplotuppertheta }{180} } \newcommand {\tdplotdosurfaceplot }[6]{\par \pgfmathsetmacro {\nextphi }{\curphi + \tdplotsuperfudge *\viewphistep } \par \begin {scope}[opacity=1] \par \par \tdplotcheckdiff {\nextphi }{360}{\origviewphistep }{#2}{} \tdplotcheckdiff {\nextphi }{0}{\origviewphistep }{#2}{} \par \tdplotcheckdiff {\nextphi }{90}{\origviewphistep }{#3}{} \tdplotcheckdiff {\nextphi }{450}{\origviewphistep }{#3}{} \end {scope} \par \foreach \curtheta in{\viewthetastart ,\viewthetainc ,...,\viewthetaend } { \par \pgfmathsetmacro {\curlongitude }{90 -\curphi } \pgfmathsetmacro {\curlatitude }{90 -\curtheta } \par \ifthenelse {\equal {\leftright }{-1.0}}{\pgfmathsetmacro {\curphi }{\curphi -\origviewphistep } }{} \par \pgfmathsetmacro {\tdplottheta }{mod(\curtheta ,360)} \pgfmathsetmacro {\tdplotphi }{mod(\curphi ,360)} \par \pgfmathparse {\tdplotphi <0} \ifthenelse {\equal {\pgfmathresult }{1}}{ \pgfmathsetmacro {\tdplotphi }{\tdplotphi + 360} }{}\par \pgfmathparse {\tdplottheta >\tdplotuppertheta } \pgfmathsetmacro {\logictest }{1 -\pgfmathresult } \par \pgfmathparse {\tdplottheta <\tdplotlowertheta } \pgfmathsetmacro {\logictest }{\logictest * (1 -\pgfmathresult )} \par \pgfmathsetmacro {\tdplottheta }{\tdplottheta + \viewthetastep } \pgfmathparse {\tdplottheta >\tdplotuppertheta } \pgfmathsetmacro {\logictest }{\logictest * (1 -\pgfmathresult )} \par \pgfmathparse {\tdplottheta <\tdplotlowertheta } \pgfmathsetmacro {\logictest }{\logictest * (1 -\pgfmathresult )} \par \pgfmathparse {\tdplotphi >\tdplotupperphi } \pgfmathsetmacro {\logictest }{\logictest * (1 -\pgfmathresult )} \par \pgfmathparse {\tdplotphi <\tdplotlowerphi } \pgfmathsetmacro {\logictest }{\logictest * (1 -\pgfmathresult )} \par \pgfmathsetmacro {\tdplotphi }{\tdplotphi + \viewphistep } \par \pgfmathparse {\tdplotphi <0} \ifthenelse {\equal {\pgfmathresult }{1}}{ \pgfmathsetmacro {\tdplotphi }{\tdplotphi + 360} }{}\par \pgfmathparse {\tdplotphi >\tdplotupperphi } \pgfmathsetmacro {\logictest }{\logictest * (1 -\pgfmathresult )} \par \pgfmathparse {\tdplotphi <\tdplotlowerphi } \pgfmathsetmacro {\logictest }{\logictest * (1 -\pgfmathresult )} \par \par \pgfmathsetmacro {\tdplottheta }{\curtheta } \pgfmathsetmacro {\tdplotphi }{\curphi } \par \ifthenelse {\equal {#6}{parametricfill}}{\ifthenelse {\equal {\logictest }{1.0}}{\pgfmathsetmacro {\radius }{#1} \pgfmathsetmacro {\tdplotr }{\radius *360} \par \pgfmathlessthan {\radius }{0} \pgfmathsetmacro {\phaseshift }{180 * \pgfmathresult } \par \pgfmathsetmacro {\colorarg }{#5} \pgfmathsetmacro {\colorarg }{\colorarg + \phaseshift } \pgfmathsetmacro {\colorarg }{mod(\colorarg ,360)} \par \pgfmathlessthan {\colorarg }{0} \pgfmathsetmacro {\colorarg }{\colorarg + 360*\pgfmathresult } \par \pgfmathdivide {\colorarg }{360} \definecolor {tdplotfillcolor}{hsb}{\pgfmathresult ,1,1} \color {tdplotfillcolor} }{}}{\pgfsetfillcolor {#5} } \pgfsetstrokecolor {#4} \par \ifthenelse {\equal {\leftright }{-1.0}}{\pgfmathsetmacro {\curphi }{\curphi + \origviewphistep } }{} \par \ifthenelse {\equal {\logictest }{1.0}}{\pgfmathsetmacro {\radius }{abs(#1)} \pgfpathmoveto {\pgfpointspherical {\curlongitude }{\curlatitude }{\radius }} \par \pgfmathsetmacro {\tdplotphi }{\curphi + \viewphistep } \pgfmathsetmacro {\radius }{abs(#1)} \pgfpathlineto {\pgfpointspherical {\curlongitude -\viewphistep }{\curlatitude }{\radius }} \par \pgfmathsetmacro {\tdplottheta }{\curtheta + \viewthetastep } \pgfmathsetmacro {\radius }{abs(#1)} \pgfpathlineto {\pgfpointspherical {\curlongitude -\viewphistep }{\curlatitude -\viewthetastep }{\radius }} \par \pgfmathsetmacro {\tdplotphi }{\curphi } \pgfmathsetmacro {\radius }{abs(#1)} \pgfpathlineto {\pgfpointspherical {\curlongitude }{\curlatitude -\viewthetastep }{\radius }} \pgfpathclose \par \pgfusepath {fill,stroke} }{} } } \newcommand {\tdplotshowargcolorguide }[4]{ \par \pgfmathsetmacro {\tdplotx }{#1} \pgfmathsetmacro {\tdploty }{#2} \pgfmathsetmacro {\tdplothuestep }{5} \pgfmathsetmacro {\tdplotxsize }{#3} \pgfmathsetmacro {\tdplotysize }{#4} \par \pgfmathsetmacro {\tdplotyscale }{\tdplotysize /360} \par \foreach \tdplotphi in {0,\tdplothuestep ,...,360} { \pgfmathdivide {\tdplotphi }{360} \definecolor {tdplotfillcolor}{hsb}{\pgfmathresult ,1,1} \color {tdplotfillcolor} \par \pgfmathsetmacro {\tdplotstarty }{\tdploty + \tdplotphi * \tdplotyscale } \pgfmathsetmacro {\tdplotstopy }{\tdplotstarty + \tdplothuestep * \tdplotyscale } \pgfmathsetmacro {\tdplotstartx }{\tdplotx } \pgfmathsetmacro {\tdplotstopx }{\tdplotx + \tdplotxsize } \filldraw [tdplot_screen_coords] (\tdplotstartx ,\tdplotstarty ) rectangle (\tdplotstopx ,\tdplotstopy ); } \par \pgfmathsetmacro {\tdplotstopy }{\tdploty + (360+\tdplothuestep )*\tdplotyscale } \pgfmathsetmacro {\tdplotstopx }{\tdplotx + \tdplotxsize } \par \draw [tdplot_screen_coords] (\tdplotx ,\tdploty ) rectangle (\tdplotstopx ,\tdplotstopy ); \par \node [tdplot_screen_coords,anchor=west,xshift=5pt] at (\tdplotstopx ,\tdploty ) {$0$}; \node [tdplot_screen_coords,anchor=west,xshift=5pt] at (\tdplotstopx ,\tdplotstopy ) {$2\pi $}; \par \pgfmathsetmacro {\tdplotstopy }{\tdploty + (360+\tdplothuestep )/2*\tdplotyscale } \node [tdplot_screen_coords,anchor=west,xshift=5pt] at (\tdplotstopx ,\tdplotstopy ) {$\pi $}; } \newcommand {\tdplotgetpolarcoords }[3]{\pgfmathsetmacro {\vxcalc }{#1} \pgfmathsetmacro {\vycalc }{#2} \pgfmathsetmacro {\vzcalc }{#3} \pgfmathsetmacro {\vcalc }{ sqrt((\vxcalc )^2 + (\vycalc )^2 + (\vzcalc )^2) } \par \pgfmathsetmacro {\vxycalc }{ sqrt((\vxcalc )^2 + (\vycalc )^2) } \par \pgfmathsetmacro {\tdplotrestheta }{asin(\vxycalc /\vcalc )} \pgfmathparse {\vzcalc <0} \ifthenelse {\equal {\pgfmathresult }{1}}{\pgfmathsetmacro {\tdplotrestheta }{180 -\tdplotrestheta } } {} \ifthenelse {\equal {\vxcalc }{0.0}}{\pgfmathparse {\vycalc <0} \ifthenelse {\equal {\pgfmathresult }{1}}{\pgfmathsetmacro {\tdplotresphi }{270} } {\pgfmathparse {\vycalc >0} \ifthenelse {\equal {\pgfmathresult }{1}}{\pgfmathsetmacro {\tdplotresphi }{90} } {\pgfmathsetmacro {\tdplotresphi }{0} } } } {\pgfmathsetmacro {\tdplotresphi }{atan(\vycalc /\vxcalc )} \pgfmathparse {\vxcalc <0} \ifthenelse {\equal {\pgfmathresult }{1}}{\pgfmathsetmacro {\tdplotresphi }{\tdplotresphi +180} } { } \par \pgfmathparse {\tdplotresphi <0} \ifthenelse {\equal {\pgfmathresult }{1}}{\pgfmathsetmacro {\tdplotresphi }{\tdplotresphi +360} } {} } } \newcommand {\vec }[0]{\mathbf } \newcommand {\RR }[0]{\mathbb {R}} \newcommand {\dfn }[0]{\textit } \newcommand {\dotp }[0]{\cdot } \newcommand {\id }[0]{\text {id}} \newcommand {\norm }[1]{\left \lVert #1\right \rVert } \newcommand {\mathtoolsset }[1]{\setkeys {\MT_options_name: }{#1}} \newcommand {\refeq }[1]{\textup {\ref {#1}}} \newcommand {\lparen }[0]{(} \newcommand {\rparen }[0]{)} \newcommand {\ordinarycolon }[0]{:} \newcommand {\MT_test_for_tcb_other:nnnnn }[1]{\if:w t#1\relax \expandafter \MH_use_choice_i:nnnn \else: \if:w c#1\relax \expandafter \expandafter \expandafter \MH_use_choice_ii:nnnn \else: \if:w b#1\relax \expandafter \expandafter \expandafter \expandafter \expandafter \expandafter \expandafter \MH_use_choice_iii:nnnn \else: \expandafter \expandafter \expandafter \expandafter \expandafter \expandafter \expandafter \MH_use_choice_iv:nnnn \fi: \fi: \fi: } \newcommand {\newcases }[6]{\newenvironment {#1}{\MT_start_cases:nnnn {#2}{#3}{#4}{#5}}{\MH_end_cases: \right #6}} \newcommand {\renewcases }[6]{\renewenvironment {#1}{\MT_start_cases:nnnn {#2}{#3}{#4}{#5}}{\MH_end_cases: \right #6}} \newcommand {\SwapAboveDisplaySkip }[0]{\noalign {\vskip -\abovedisplayskip \vskip \abovedisplayshortskip }} \newcommand {\vdotswithin }[1]{{\mathmakebox [\widthof {\ensuremath {{}#1{}}}][c]{{\vdots }}}} \newcommand {\MTFlushSpaceBelow }[0]{\\\noalign {\nobreak \vskip -\lineskip \vskip -\l_MT_shortvdotswithinadjustbelow_dim \vskip -\origjot \vskip \jot }} \newcommand {\mathmbox }[0]{\mathpalette \MT_mathmbox:nn } \newcommand {\prescript }[3]{\mathchoice {\MT_prescript_inner: {#1}{#2}{#3}{\scriptstyle }}{\MT_prescript_inner: {#1}{#2}{#3}{\scriptstyle }}{\MT_prescript_inner: {#1}{#2}{#3}{\scriptscriptstyle }}{\MT_prescript_inner: {#1}{#2}{#3}{\scriptscriptstyle }}} \newcommand {\spreadlines }[1]{\setlength {\jot }{#1}\ignorespaces } \newcommand {\newgathered }[4]{\newenvironment {#1}{\def \MT_gathered_pre: {#2}\def \MT_gathered_post: {#3}\def \MT_gathered_env_end: {#4}\MT_gathered_env }{\endMT_gathered_env }} \newcommand {\renewgathered }[4]{\renewenvironment {#1}{\def \MT_gathered_pre: {#2}\def \MT_gathered_post: {#3}\def \MT_gathered_env_end: {#4}\MT_gathered_env }{\endMT_gathered_env }} \newcommand {\lgathered }[0]{\def \MT_gathered_pre: {}\def \MT_gathered_post: {\hfil }\def \MT_gathered_env_end: {}\MT_gathered_env } \newcommand {\rgathered }[0]{\def \MT_gathered_pre: {\hfil }\def \MT_gathered_post: {}\def \MT_gathered_env_end: {}\MT_gathered_env } \newcommand {\gathered }[0]{\def \MT_gathered_pre: {\hfil }\def \MT_gathered_post: {\hfil }\def \MT_gathered_env_end: {}\MT_gathered_env } \newcommand {\splitfrac }[2]{\genfrac {}{}{0pt}{1}{\textstyle #1\quad \hfill }{\textstyle \hfill \quad \mathstrut #2}} \newcommand {\splitdfrac }[2]{\genfrac {}{}{0pt}{0}{#1\quad \hfill }{\hfill \quad \mathstrut #2}} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument } \newcommand {\dblcolon }[0]{\vcentcolon \mathrel {\mkern -.9mu}\vcentcolon } \newcommand {\coloneqq }[0]{\vcentcolon \mathrel {\mkern -1.2mu}=} \newcommand {\Coloneqq }[0]{\dblcolon \mathrel {\mkern -1.2mu}=} \newcommand {\coloneq }[0]{\vcentcolon \mathrel {\mkern -1.2mu}\mathrel {-}} \newcommand {\Coloneq }[0]{\dblcolon \mathrel {\mkern -1.2mu}\mathrel {-}} \newcommand {\eqqcolon }[0]{=\mathrel {\mkern -1.2mu}\vcentcolon } \newcommand {\Eqqcolon }[0]{=\mathrel {\mkern -1.2mu}\dblcolon } \newcommand {\eqcolon }[0]{\mathrel {-}\mathrel {\mkern -1.2mu}\vcentcolon } \newcommand {\Eqcolon }[0]{\mathrel {-}\mathrel {\mkern -1.2mu}\dblcolon } \newcommand {\colonapprox }[0]{\vcentcolon \mathrel {\mkern -1.2mu}\approx } \newcommand {\Colonapprox }[0]{\dblcolon \mathrel {\mkern -1.2mu}\approx } \newcommand {\colonsim }[0]{\vcentcolon \mathrel {\mkern -1.2mu}\sim } \newcommand {\Colonsim }[0]{\dblcolon \mathrel {\mkern -1.2mu}\sim } \newcommand {\nuparrow }[0]{\MH_nuparrow: } \newcommand {\ndownarrow }[0]{\MH_ndownarrow: } \newcommand {\bigtimes }[0]{\MH_csym_bigtimes: }$

Application to Network Flow

There are many types of problems that concern a network of conductors along which some sort of flow is observed. Examples of these include an irrigation network and a network of streets or freeways. There are often points in the system at which a net flow either enters or leaves the system. The basic principle behind the analysis of such systems is that the total flow into the system must equal the total flow out. In fact, we apply this principle at every junction in the system.

Junction Rule At each of the junctions in the network, the total flow into that junction must equal the total flow out.

This requirement gives a linear equation relating the flows in conductors emanating from the junction.

A network of one-way streets is shown in the accompanying diagram. The rate of flow of cars into intersection $A$ is 500 cars per hour, and 400 and 100 cars per hour emerge from $B$ and $C$ , respectively. Find the possible flows along each street.

Suppose the flows along the streets are $f_1$ , $f_2$ , $f_3$ , $f_4$ , $f_5$ , and $f_6$ cars per hour in the directions shown.

Then, equating the flow in with the flow out at each intersection, we get

$\begin{equation*} \begin{array}{lrl} \mbox{Intersection } A & 500 & = f_1 + f_2 + f_3 \\ \mbox{Intersection } B & \quad f_1 + f_4 + f_6 & = 400 \\ \mbox{Intersection } C & f_3 + f_5 & = f_6 + 100 \\ \mbox{Intersection } D & f_2 & = f_4 + f_5 \\ \end{array} \end{equation*}$ These give four equations in the six variables $f_1, f_2, \dots , f_6$ . $\begin{equation*} \begin{array}{rlrlrlrlrlrcr} f_1 & + & f_2 & + & f_3 & & & & & & & = & 500 \\ f_1 & & & & & + & f_4 & & & + & f_6 & = & 400 \\ & & & & f_3 & & & + & f_5 & - & f_6 & = & 100 \\ & & f_2 & & & - & f_4 & - & f_5 & & & = & 0 \\ \end{array} \end{equation*}$ The reduction of the augmented matrix is $\begin{equation*} \left[ \begin{array}{rrrrrr|r} 1 & 1 & 1 & 0 & 0 & 0 & 500 \\ 1 & 0 & 0 & 1 & 0 & 1 & 400 \\ 0 & 0 & 1 & 0 & 1 &-1 & 100 \\ 0 & 1 & 0 &-1 &-1 & 0 & 0 \end{array} \right] \rightarrow \left[ \begin{array}{rrrrrr|r} 1 & 0 & 0 & 1 & 0 & 1 & 400 \\ 0 & 1 & 0 &-1 &-1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 &-1 & 100 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right] \end{equation*}$ Hence, when we use $f_4$ , $f_5$ , and $f_6$ as parameters, the general solution is $\begin{equation*} f_1 = 400 - f_4 - f_6 \quad\quad f_2 = f_4 + f_5 \quad\quad f_3 = 100 - f_5 + f_6 \end{equation*}$ This gives all solutions to the system of equations and hence all the possible flows.

Of course, not all these solutions may be acceptable in the real situation. For example, the flows $f_1, f_2, \dots , f_6$ are all positive in the present context (if one came out negative, it would mean traffic flowed in the opposite direction). This imposes constraints on the flows: $f_1 \geq 0$ and $f_3 \geq 0$ become

$\begin{equation*} f_4 + f_6 \leq 400 \quad\quad f_5 - f_6 \leq 100 \end{equation*}$ Further constraints might be imposed by insisting on maximum values on the flow in each street.

Practice Problems

Find the possible flows in each of the following networks of pipes.

(a)
(b): Click the arrow to see the answer.

$\begin {array}[t]{rcrrr} f_1 & = & 85 & - f_4 & - f_7 \\ f_2 & = & 60 & - f_4 & - f_7 \\ f_3 & = & -75 & + f_4 & + f_6 \\ f_5 & = & 40 & - f_6 & - f_7 \\ \end {array}$
$f_4$ , $f_6$ , $f_7$ parameters

A proposed network of irrigation canals is described in the accompanying diagram. At peak demand, the flows at interchanges $A$ , $B$ , $C$ , and $D$ are as shown.

(a): Find the possible flows.
(b): If canal $BC$ is closed, what range of flow on $AD$ must be maintained so that no canal carries a flow of more than 30?
Click the arrow to see the answer.

$\begin {array}[t]{l} f_5 = 15 \\ 25 \leq f_4 \leq 30 \end {array}$

A traffic circle has five one-way streets, and vehicles enter and leave as shown in the accompanying diagram.

(a): Compute the possible flows.
(b): Which road has the heaviest flow?

AB BC CD DE EA

Text Source

This application was adapted from Section 1.4 of Keith Nicholson’s Linear Algebra with Applications. (CC-BY-NC-SA)

W. Keith Nicholson, Linear Algebra with Applications, Lyryx 2018, Open Edition, p. 27