9.5. Hall–König のマッチング定理の証明

\[ \max\left\{ \left\vert f\right\vert \mid f\text{ は } N \text{ 上のフロー}\right\} =\min\left\{ c\left( S,\overline{S}\right) \mid S\subseteq V\ \wedge\ s\in S\ \wedge\ t\notin S\right\} \]

\[ \begin{aligned} \left\vert M\right\vert = \left\vert f\right\vert & = c\left( S,\ \overline {S}\right) \\ & = \underbrace{c\left( \left\{ s\right\} ,\ \overline{S}\right)}_{\substack{=\left\vert X\setminus U\right\vert \\[3pt]\text{[なぜ？]}}}+c\left(\underbrace{X\cap S}_{=U},\ \overline{S}\right) +\underbrace{c\left( Y\cap S,\ \overline{S}\right) }_{\substack{=\left\vert Y\cap S\right\vert \\[3pt]\text{[なぜ？]}}}\\ & \quad \left(\because\ S\text{ は共通要素を持たない三つの集合 }\left\{ s\right\},\ X\cap S,\ Y\cap S \text{ の和集合}\right) \\[5pt] & =\underbrace{\left\vert X\setminus U\right\vert }_{=\left\vert X\right\vert -\left\vert U\right\vert }\hspace{15pt}+\hspace{-15pt}\underbrace{c\left( U,\ \overline{S}\right) +\left\vert Y\cap S\right\vert }_{\substack{\geq\left\vert N\left( U\right) \right\vert \\[4pt](\because\ \text{任意の頂点 } y\in N\left( U\right) \text{ は } Y\cap\, S \text{ に属し } \left\vert Y\cap\, S\right\vert \text{ に } \\[2pt] \text{ 寄与するか、 } \overline{S}\text{ に属し }c\left( U,\ \overline{S}\right) \text{ に寄与する} )}}\\[40pt] & \geq\left\vert X\right\vert -\left\vert U\right\vert +\left\vert N\left(U\right) \right\vert \\[4pt] & =\left\vert N\left( U\right) \right\vert +\left\vert X\right\vert -\left\vert U\right\vert \end{aligned} \]