Součásti dokumentu 01ZTGA
Zdrojový kód
%\wikiskriptum{01ZTGA}
\section{Párování v grafech}
\begin{defn}
Buď $G=(V,E)$ graf. \textbf{Párování} (angl. \emph{matching}) v $G$
je podmnožina $M\subset E$ taková, že\[
\left(\forall e,f\in E\right)\left(e\neq f\Rightarrow e\cap f=\emptyset\right),\]
tj. žádné dvě hrany nesdílí koncový vrchol.
\end{defn}
\begin{defn}
Řekneme, že párování $M$ je maximální, pokud pro každé jiné párování
$M'$ platí $\# M\geq\# M'$.
\end{defn}
\begin{example*}
K tomuto párování nelze přidat žádnou hranu, ale není to maximílní
párování:
\hfill{}
\begin{center}
%Title: parovani1.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:14:24 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 9.049 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.620 20.955
}%
%
% Fig POLYLINE object
%
\linethickness=2pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'161}}})
{\color[rgb]{0,0,0}\putrule from 9.049 20.955 to 10.478 20.955
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\putrule from 7.620 20.955 to 11.906 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 11.906 20.955
}%
\linethickness=0pt
\putrectangle corners at 7.485 21.088 and 12.042 20.822
\endpicture}
\end{center}
\hfill{}~
Maximální párování je až toto:
\hfill{}
\begin{center}
%Title: parovani2.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:16:56 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 9.049 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.620 20.955
}%
%
% Fig POLYLINE object
%
\linethickness=2pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'161}}})
{\color[rgb]{0,0,0}\putrule from 10.478 20.955 to 11.906 20.955
}%
%
% Fig POLYLINE object
%
\linethickness=2pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'161}}})
{\color[rgb]{0,0,0}\putrule from 7.620 20.955 to 9.049 20.955
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\putrule from 7.620 20.955 to 11.906 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 11.906 20.955
}%
\linethickness=0pt
\putrectangle corners at 7.485 21.088 and 12.042 20.822
\endpicture}
\end{center}
\hfill{}~
\end{example*}
\begin{defn}
Nechť $M$ je párování v $G=(V,E)$. Vrchol $v\in V$ takový, že $\left(\exists e\in M\right)\left(v\in e\right)$,
nazýváme $M$-\textbf{saturovaný}. Je-li každý vrchol z $V$ $M$-saturovaný,
říkáme, že $M$ je \textbf{perfektní} párování.
\end{defn}
\begin{rem*}
Každé perfektní párování je maximální. Nutná podmínka pro existenci
perfektního párování je, aby $\# V$ byl sudý.
\end{rem*}
\begin{rem*}
Takto se zlepšovala složitost známých algoritmů pro nalezení perfektního
párování:
\end{rem*}
\begin{lyxlist}{00.00.0000}
\item [1965]$O(n^{4})$
\item [1969]$O(n^{3})$
\item [1974]$O(n\cdot m)$ (přitom ovšem $m\leq\binom{n}{2}=O(n^{2})$)
\item [1980]$O(n^{\frac{1}{2}}\cdot m)$
\end{lyxlist}
\begin{rem*}
Nechť $G=(V_{1}\cup V_{2},E)$ je bipartitní graf (třeba množina žen
a mužů - hrany pak určují, kdo se s kým zná). Ptejme se, zda má graf
perfektní párování (zda si každý může vybrat partnera mezi těmi, které
zná, a nikdo nezůstane sám). Nutnou podmínkou je zřejmě\[
\# V_{1}=\# V_{2}.\]
Dále si připomeňme, jak vypadá adjacenční matice bipartitního grafu
s vhodně uspořádanými vrcholy:\[
\vec{A}_{G}=\left(\begin{array}{cc}
\vec{0} & \vec{B}\\
\vec{B}^{\T} & \vec{0}\end{array}\right),\]
kde $\vec{B}=\left(b_{ij}\right).$ Je-li $\pi\in S_{n}$, tj. je
to permutace $\pi:\hat{n}\mapsto\hat{n}$ , pak\[
M=\left\{ \left.\{ v_{i},v_{\pi(i)}\}\right|i\in\hat{n}\right\} \]
představuje perfektní párování, právě když\[
b_{1\pi(1)}b_{2\pi(2)}\cdots b_{n\pi(n)}=1.\]
Počet perfektních párování v $G$ je potom roven permanentu matice
$\vec{B}$, tj. číslu\[
\textrm{per}\,\vec{B}=\sum_{\pi\in S_{n}}b_{1\pi(1)}b_{2\pi(2)}\cdots b_{n\pi(n)}.\]
Na rozdíl od výpočtu determinantu je však výpočet permanentu matice
NP-úplná úloha. O existenci perfektního párování v bipartitním grafu
tedy není vhodné rozhodovat na základě podmínky $\textrm{per}\,\vec{B}>0$.
Následující výklad ukáže mimo jiné postačující podmínku existence
perfektního párování.
\end{rem*}
\begin{example*}
Pojem perfektní párování nenalézá uplatnění pouze v tanečních kursech,
nýbrž například i v organické chemii. Jak známo, dvojné vazby v benzenovém
jádře nemají ve skutečnosti jednoznačné umístění, a proto se někdy
v jeho vzorci kreslí místo samotných vazeb jen ,,kolečko{}``. Platí,
že nutnou podmínkou pro existenci sloučeniny složené z benzenových
jader je, aby graf tvořený jejím vzorcem měl perfektní párování. Přitom
sloučenina je tím stabilnější, čím více různých perfektních párování
existuje. (viz. obrázek \ref{cap:benzen})%
\begin{figure}
\begin{center}
%Title: benzen.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 20:12:16 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 POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 8.308 25.161 7.711 24.564 /
\putrule from 7.711 24.564 to 7.711 23.817
\plot 7.711 23.817 8.308 23.220 /
\plot 8.308 23.220 8.905 23.817 /
\putrule from 8.905 23.817 to 8.905 24.564
\plot 8.905 24.564 8.308 25.161 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 8.905 26.507 8.308 25.910 /
\putrule from 8.308 25.910 to 8.308 25.163
\plot 8.308 25.163 8.905 24.564 /
\plot 8.905 24.564 9.504 25.163 /
\putrule from 9.504 25.163 to 9.504 25.910
\plot 9.504 25.910 8.905 26.507 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 7.711 26.507 7.112 25.910 /
\putrule from 7.112 25.910 to 7.112 25.163
\plot 7.112 25.163 7.711 24.564 /
\plot 7.711 24.564 8.308 25.163 /
\putrule from 8.308 25.163 to 8.308 25.910
\plot 8.308 25.910 7.711 26.507 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 5.916 25.087 5.319 24.490 /
\putrule from 5.319 24.490 to 5.319 23.743
\plot 5.319 23.743 5.916 23.144 /
\plot 5.916 23.144 6.515 23.743 /
\putrule from 6.515 23.743 to 6.515 24.490
\plot 6.515 24.490 5.916 25.087 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 4.720 25.087 4.123 24.490 /
\putrule from 4.123 24.490 to 4.123 23.743
\plot 4.123 23.743 4.720 23.144 /
\plot 4.720 23.144 5.319 23.743 /
\putrule from 5.319 23.743 to 5.319 24.490
\plot 5.319 24.490 4.720 25.087 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 4.123 26.433 3.524 25.834 /
\putrule from 3.524 25.834 to 3.524 25.089
\plot 3.524 25.089 4.123 24.490 /
\plot 4.123 24.490 4.720 25.089 /
\putrule from 4.720 25.089 to 4.720 25.834
\plot 4.720 25.834 4.123 26.433 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 2.254 26.507 1.655 25.910 /
\putrule from 1.655 25.910 to 1.655 25.163
\plot 1.655 25.163 2.254 24.564 /
\plot 2.254 24.564 2.851 25.163 /
\putrule from 2.851 25.163 to 2.851 25.910
\plot 2.851 25.910 2.254 26.507 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 0.834 26.507 0.237 25.910 /
\putrule from 0.237 25.910 to 0.237 25.163
\plot 0.237 25.163 0.834 24.564 /
\plot 0.834 24.564 1.433 25.163 /
\putrule from 1.433 25.163 to 1.433 25.910
\plot 1.433 25.910 0.834 26.507 /
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.523:0.671 360 degrees
from 2.777 25.535 center at 2.254 25.535
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 4.123 26.359 4.646 25.834 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\putrule from 3.600 25.834 to 3.600 25.089
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 4.720 23.220 4.197 23.743 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 4.720 25.013 4.197 24.490 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\putrule from 5.393 24.414 to 5.393 23.743
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 6.439 23.743 5.916 23.220 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 5.916 25.013 6.439 24.490 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\putrule from 1.357 25.910 to 1.357 25.163
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 0.311 25.163 0.834 24.640 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 0.311 25.910 0.834 26.433 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}benzen}%
} [lB] at 0.804 23.743
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}neexistuje}%
} [lB] at 7.542 22.396
\linethickness=0pt
\putrectangle corners at 0.212 26.532 and 9.529 22.197
\endpicture}
\end{center}
\caption{\label{cap:benzen}Benzenové jádro a teoretické sloučeniny}
\end{figure}
\end{example*}
\begin{defn}
Nechť $M$ je párování v grafu $G=(V,E)$. Řekneme, že cesta $v_{0},v_{1},...,v_{k}$
je $M$-\textbf{střídající}, pokud $\forall i\in\{1,2,...,k-1\}$
platí $\{ v_{i-1},v_{i}\}\in M\Leftrightarrow\{ v_{i},v_{i+1}\}\notin M$.
$M$-střídající cestu $v_{0},v_{1},...,v_{k}$ nazveme $M$-\textbf{zlepšující},
pokud vrcholy $v_{0}$ a $v_{k}$ nejsou $M$-saturovány.
\end{defn}
\begin{rem*}
Každá $M$-zlepšující cesta má zřejmě lichou délku. Na obrázku \ref{cap:M-stridajici}
je $M$-střídající cesta, která není $M$-zlepšující. Ani její úsek
$v_{1},...,v_{4}$ není $M$-zlepšující, protože vrchol $v_{1}$ je
$M$-saturován.%
\begin{figure}
\begin{center}
%Title: m_stridajici.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:29:04 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 1.190 24.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 2.618 25.718
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 3.571 24.289
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 5.476 25.241
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 4.523 23.336
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 1.190 24.765 2.618 25.718 /
\plot 2.618 25.718 3.571 24.289 /
\plot 3.571 24.289 5.476 25.241 /
\plot 5.476 25.241 4.523 23.336 /
}%
%
% Fig POLYLINE object
%
\linethickness=2pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'161}}})
{\color[rgb]{0,0,0}\plot 1.190 24.765 2.618 25.718 /
}%
%
% Fig POLYLINE object
%
\linethickness=2pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'161}}})
{\color[rgb]{0,0,0}\plot 3.571 24.289 5.476 25.241 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{2}$}%
} [lB] at 3.334 23.694
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{3}$}%
} [lB] at 5.831 25.123
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{4}$}%
} [lB] at 5.000 23.218
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{0}$}%
} [lB] at 0.474 24.765
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at 2.976 25.599
\linethickness=0pt
\putrectangle corners at 0.442 26.082 and 5.863 23.019
\endpicture}
\end{center}
\caption{\label{cap:M-stridajici}$M$-střídající cesta}
\end{figure}
V následujících důkazech bude potřeba si podobné skutečnosti plynoucí
z definic dobře uvědomovat.
\end{rem*}
\begin{defn*}
Buďte $A,B$ dvě množiny. \textbf{Symetrickou diferencí} množin $A,B$
rozumíme množinu\[
A\Delta B=\left(A\backslash B\right)\cup\left(B\backslash A\right)=\left(A\cup B\right)\backslash\left(A\cap B\right).\]
\end{defn*}
\begin{thm}
\textbf{\emph{\label{thm:bergeova-veta}(Berge, 1957)}}
Párování v grafu $G$ je maximální právě tehdy, když v $G$ neexistuje
$M$-zlepšující cesta.
\end{thm}
\begin{proof}
Oba směry ekvivalence dokážeme sporem.
$\boxed{{\Rightarrow:}}$
Nechť $M$ je maximální a přitom existuje $M$-zlepšující cesta, kterou
označíme $P$. Definujeme nyní párování\[
M'=M\Delta P.\]
Řečeno slovy: $M'$ vznikne tak, že mimo cestu necháme $M$ jak je
a na cestě dáme do $M'$ naopak jen ty hrany, které nejsou v $M$.
Je zřejmé, že $M'$ bude opět párování, přičemž $\# M'>\# M$, a to
je spor.
$\boxed{{\Leftarrow:}}$
Nechť v $G$ neexistuje $M$-zlepšující cesta a přitom $M$ není maximální.
Potom existuje párování $M'$ takové, že $\# M'>\# M$. Definujme
nyní graf\[
H=(V,M\Delta M').\]
Potom je zřejmé, že $H$ se skládá jen z kružnic a cest, na nichž
se střídají hrany z $M$ a z $M'$ (to také znamená, že v $H$ jsou
všechny kružnice sudé délky). Protože $\# M'>\# M$, tak také $M\Delta M'$
obsahuje více hran z $M'$ než z $M$. Z toho plyne, že v $H$ musí
existovat alespoň jedna cesta liché délky, která obsahuje $2k+1$
($k\in\N_{0}$) hran, z toho $k$ hran je z $M$ a $k+1$ hran je
z $M'$, a navíc její koncové vrcholy nejsou $M$-saturovány v $G$.
(Poslední vlastnost lze formulovat i tak, že uvedená cesta není vlastním
podgrafem nějaké cesty v $H$ - nejde už prodloužit.). Tato cesta
je ovšem $M$-zlepšující, což je spor.
\end{proof}
\subsection{Párování v bipartitních grafech}
\begin{defn}
Množinou \textbf{sousedů} (angl. \emph{neighbours}) vrcholu $v$ v
grafu $G=(V,E)$ rozumíme množinu\[
N(v)=\left\{ \left.u\in V\right|\{ u,v\}\in E\right\} .\]
Množinou sousedů vrcholů z množiny $S\subset V$ rozumíme množinu\[
N(S)=\bigcup_{v\in S}N(v).\]
\end{defn}
\begin{thm}
\textbf{\emph{(Hall, 1935)}}
Nechť $G=(V_{1}\cup V_{2},E)$ je bipartitní graf. Potom v $G$ existuje
párování saturující celé $V_{1}$ právě tehdy, když \[
\left(\forall S\subset V_{1}\right)\left(\# N(S)\geq\# S\right).\]
\end{thm}
\begin{proof}
$\boxed{{\Rightarrow:}}$
Je-li celé $V_{1}$ saturováno, je každý vrchol z $V_{1}$ spárován
s nějakým vrcholem z $V_{2}$. Pro libovolnou $S\subset V_{1}$ je
tedy $\# S$ vrcholů z $V_{1}$ spojeno s nejméně $\# S$ vrcholy
z $V_{2}$, takže $\# N(S)\geq\# S$.
$\boxed{{\Leftarrow:}}$
Sporem. Buď $M$ maximální párování v $G$, které podle předpokladu
nesaturuje celé $V_{1}$. Existuje tedy $u\in V_{1}$ takové, že není
$M$-saturováno. Pokud zvolíme $S=\{ u\}$, tak $\# N(S)\geq1$, takže
$d(u)\geq1$. Definujme množiny\[
X=\left\{ \left.v\in V_{1}\right|\textrm{z }u\textrm{ do }v\textrm{ existuje }M\textrm{-st\v{r}ídající cesta}\right\} ,\]
\[
Y=\left\{ \left.v\in V_{2}\right|\textrm{z }u\textrm{ do }v\textrm{ existuje }M\textrm{-st\v{r}ídající cesta}\right\} .\]
Potom zřejmě $u\in X$ (existuje $M$-střídající cesta délky 0 z $u$
do $u$). Protože $u$ není $M$-saturován, tak na $M$-střídajících
cestách z $u$ do vrcholů ve $V_{1}$ i $V_{2}$ není první hrana
z $M$. Po každé takové cestě tedy jdeme z $V_{1}$ do $V_{2}$ po
hraně, která není v $M$, a do $V_{1}$ se vracíme po hraně, která
je v $M$. Dále platí, že každá maximální%
\footnote{Maximální $M$-střídající cestou rozumíme takovou cestu, která není
vlastním podgrafem nějaké $M$-střídající cesty. Jinými slovy to znamená,
že už nejde prodloužit, aniž by přestala být $M$-střídající.%
} $M$-střídající cesta vycházející z $u$ končí ve $V_{1}$, protože
v opačném případě by byla $M$-zlepšující. To by ale podle Bergeovy
věty byl spor s tím, že $M$ je maximální párování. Každý vrchol $v\in Y$
je tedy spojen hranou z množiny $M$ s nějakým vrcholem $w\in X$,
$w\neq u$. Je také jasné, že každý soused libovolného vrcholu z $X$
musí ležet v $Y$. Shrneme-li provedené úvahy, lze psát\[
\# X=\# Y+1\]
a také\[
N(X)=Y,\]
takže $\# X>\# Y=\# N(X)$, což je spor.
\end{proof}
\begin{cor}
\label{cor:bipart_perfekt_par}Když $G=(V_{1}\cup V_{2},E)$ je bipartitní
graf, tak v $G$ existuje perfektní párování, právě když\[
\left(\forall S\subset V_{1}\right)\left(\# N(S)\geq\# S\right)\]
a zároveň\[
\left(\forall S\subset V_{2}\right)\left(\# N(S)\geq\# S\right).\]
\end{cor}
\begin{defn}
Graf $G=(V,E)$ nazveme $r$-\textbf{regulární}, jestliže \[
\delta(G)=\Delta(G)=r,\]
tj. $\left(\forall v\in V\right)$$\left(d_{G}(v)=r\right)$.
\end{defn}
\begin{cor}
\textbf{\emph{\label{cor:snatkovy-problem}(,,sňatkový problém{}``)}}
Nechť $G=(V_{1}\cup V_{2},E)$ je $r$-regulární bipartitiní graf,
$r\geq1$. Potom $G$ má perfektní párování.
\end{cor}
\begin{proof}
Ověříme předpoklady na pravé straně ekvivalence v důsledku \ref{cor:bipart_perfekt_par}.
Vezměme $S\subset V_{1}$, označme $E_{1}$ množinu hran, které mají
jeden konec v $S$ (druhé konce těchto hran tvoří $N(S)$) a dále
označme $E_{2}$ množinu hran, které mají jeden konec v $N(S)$. Potom
je zřejmé, že $E_{1}\subset E_{2}$, takže $\# E_{2}\geq\# E_{1}$.
Z $r$-regularity grafu $G$ však plyne\begin{eqnarray*}
\# E_{1} & = & r\cdot\# S,\\
\# E_{2} & = & r\cdot N(S).\end{eqnarray*}
Po zkrácení číslem $r>0$ dostáváme pro libovolnou podmnožinu $S\subset V_{1}$
nerovnost $\# N(S)\geq\# S$. Naprosto totéž lze provést i pro $S\subset V_{2}$,
čímž je důkaz ukončen. Poznamenejme, že z obou nerovností též okamžitě
plyne samozřejmá podmínka $\# V_{1}=\# V_{2}$.
\end{proof}
\begin{thm}
Nechť $G=(V,E)$ je graf. Potom v $G$ existuje perfektní párování,
právě když\[
\left(\forall S\subset V\right)\left(\# S\geq o(G\backslash S)\right),\]
kde $o(G\backslash S)$ je počet komponent grafu $G\backslash S$,
které mají lichý počet vrcholů.
\end{thm}
\begin{proof}
Ukážeme pouze implikaci zleva doprava, opačný směr je obtížný. %
\begin{figure}
\begin{center}
%Title: perf_par_komp.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:41: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=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.318:0.315 360 degrees
from 6.350 22.877 center at 6.032 22.877
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.318:0.318 360 degrees
from 6.668 24.306 center at 6.350 24.306
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.318:0.318 360 degrees
from 6.350 25.734 center at 6.032 25.734
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.318:0.315 360 degrees
from 1.429 22.877 center at 1.111 22.877
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.318:0.318 360 degrees
from 1.111 24.306 center at 0.794 24.306
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.318:0.318 360 degrees
from 1.429 25.734 center at 1.111 25.734
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.318:0.318 360 degrees
from 4.921 25.734 center at 4.604 25.734
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.318:0.318 360 degrees
from 5.239 24.306 center at 4.921 24.306
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.318:0.315 360 degrees
from 4.921 22.877 center at 4.604 22.877
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.635:0.635 360 degrees
from 3.493 24.306 center at 2.857 24.306
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdots < 0.0953cm>
{\color[rgb]{0,0,0}\plot 2.381 24.623 1.270 25.576 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 2.381 24.306 0.953 24.306 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 2.540 23.988 1.270 22.877 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 3.175 23.829 4.445 22.877 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 3.334 24.306 4.763 24.306 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 3.334 24.623 4.445 25.576 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{20}{24.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}S}%
} [lB] at 2.699 23.971
%
% Fig TEXT object
%
\put{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}L}%
} [lB] at 0.953 21.766
%
% Fig TEXT object
%
\put{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}S}%
} [lB] at 4.604 21.766
\linethickness=0pt
\putrectangle corners at 0.444 26.082 and 6.699 21.734
\endpicture}
\end{center}
\caption{\label{cap:komponenty-sud-lich}Komponenty se sudým (S) a lichým
(L) počtem vrcholů}
\end{figure}
Pro libovolnou $S\subset V$ lze situaci znázornit jako na obrázku
\ref{cap:komponenty-sud-lich}. V původním grafu zřejmě nemohla existovat
komponenta s lichým počtem vrcholů, protože v ní nelze nalézt párování
saturující všechny vrcholy. Po odebrání množiny $S$ vznikne určitý
počet komponent s lichým počtem vrcholů, a každá z nich musí obsahovat
alespoň jeden vrchol, který je v perfektním párování spárován s vrcholem
z $S$. To už znamená, že $\# S\geq o(G\backslash S)$.
\end{proof}
