01ZTGA:Kapitola1 8

Z WikiSkripta FJFI ČVUT v Praze
Verze z 15. 1. 2012, 13:40, kterou vytvořil Karel.brinda (diskuse | příspěvky)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání
PDF [ znovu generovat, výstup z překladu ] Kompletní WikiSkriptum včetně všech podkapitol.
PDF Této kapitoly [ znovu generovat, výstup z překladu ] Přeložení pouze této kaptioly.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01ZTGA

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01ZTGAKarel.brinda 15. 1. 201223:45
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:51
Header editovatHlavičkový souborKarel.brinda 15. 1. 201212:34 header.tex
Kapitola0 editovatÚvodKarel.brinda 15. 1. 201212:36 cast0.tex
Kapitola1_1 editovatZákladní pojmyKarel.brinda 15. 1. 201212:46 cast1_kapitola1.tex
Kapitola1_2 editovatSouvislostKarel.brinda 15. 1. 201212:49 cast1_kapitola2.tex
Kapitola1_3 editovatBipartitní grafyKarel.brinda 15. 1. 201212:50 cast1_kapitola3.tex
Kapitola1_4 editovatStromyKubuondr 5. 1. 201909:06 cast1_kapitola4.tex
Kapitola1_5 editovatHledání minimální kostry grafuKarel.brinda 15. 1. 201212:51 cast1_kapitola5.tex
Kapitola1_6 editovatJednotažkyKarel.brinda 15. 1. 201212:53 cast1_kapitola6.tex
Kapitola1_7 editovatHamiltonovské kružnice a grafyKarel.brinda 15. 1. 201213:34 cast1_kapitola7.tex
Kapitola1_8 editovatPárování v grafechKarel.brinda 15. 1. 201213:40 cast1_kapitola8.tex
Kapitola1_9 editovatToky v sítíchKarel.brinda 15. 1. 201213:44 cast1_kapitola9.tex
Kapitola1_10 editovatHranové obarvení grafuKarel.brinda 15. 1. 201213:48 cast1_kapitola10.tex
Kapitola1_11 editovatVrcholové obarvení grafuKarel.brinda 15. 1. 201213:52 cast1_kapitola11.tex
Kapitola1_12 editovatPlanární grafyKarel.brinda 15. 1. 201213:56 cast1_kapitola12.tex
Kapitola1_13 editovatVlastní čísla adjacenční matice grafuKarel.brinda 15. 1. 201213:57 cast1_kapitola13.tex
Kapitola2_1 editovatBrouwerova věta o pevném boděKarel.brinda 15. 1. 201214:11 cast2_kapitola1.tex
Kapitola2_2 editovatPravděpodobnostní důkazy v teorii grafůKarel.brinda 15. 1. 201214:12 cast2_kapitola2.tex
Kapitola2_3 editovatExtremální teorie grafůKarel.brinda 15. 1. 201214:16 cast2_kapitola3.tex
Kapitola2_4 editovatRamseyovská číslaKarel.brinda 15. 1. 201214:18 cast2_kapitola4.tex
Kapitola3_1 editovatObyčejné mocninné řadyKarel.brinda 15. 1. 201214:22 cast3_kapitola1.tex
Kapitola3_2 editovatExponenciální generující funkceKarel.brinda 15. 1. 201214:22 cast3_kapitola2.tex

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}