01ZTGA:Kapitola1 8
Z WikiSkripta FJFI ČVUT v Praze
Verze z 15. 1. 2012, 14:40, kterou vytvořil Karel.brinda (diskuse | příspěvky)
[ 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. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01ZTGA
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu 01ZTGA | Karel.brinda | 16. 1. 2012 | 00:45 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 14:51 | ||
Header | editovat | Hlavičkový soubor | Karel.brinda | 15. 1. 2012 | 13:34 | header.tex | |
Kapitola0 | editovat | Úvod | Karel.brinda | 15. 1. 2012 | 13:36 | cast0.tex | |
Kapitola1_1 | editovat | Základní pojmy | Karel.brinda | 15. 1. 2012 | 13:46 | cast1_kapitola1.tex | |
Kapitola1_2 | editovat | Souvislost | Karel.brinda | 15. 1. 2012 | 13:49 | cast1_kapitola2.tex | |
Kapitola1_3 | editovat | Bipartitní grafy | Karel.brinda | 15. 1. 2012 | 13:50 | cast1_kapitola3.tex | |
Kapitola1_4 | editovat | Stromy | Kubuondr | 5. 1. 2019 | 10:06 | cast1_kapitola4.tex | |
Kapitola1_5 | editovat | Hledání minimální kostry grafu | Karel.brinda | 15. 1. 2012 | 13:51 | cast1_kapitola5.tex | |
Kapitola1_6 | editovat | Jednotažky | Karel.brinda | 15. 1. 2012 | 13:53 | cast1_kapitola6.tex | |
Kapitola1_7 | editovat | Hamiltonovské kružnice a grafy | Karel.brinda | 15. 1. 2012 | 14:34 | cast1_kapitola7.tex | |
Kapitola1_8 | editovat | Párování v grafech | Karel.brinda | 15. 1. 2012 | 14:40 | cast1_kapitola8.tex | |
Kapitola1_9 | editovat | Toky v sítích | Karel.brinda | 15. 1. 2012 | 14:44 | cast1_kapitola9.tex | |
Kapitola1_10 | editovat | Hranové obarvení grafu | Karel.brinda | 15. 1. 2012 | 14:48 | cast1_kapitola10.tex | |
Kapitola1_11 | editovat | Vrcholové obarvení grafu | Karel.brinda | 15. 1. 2012 | 14:52 | cast1_kapitola11.tex | |
Kapitola1_12 | editovat | Planární grafy | Karel.brinda | 15. 1. 2012 | 14:56 | cast1_kapitola12.tex | |
Kapitola1_13 | editovat | Vlastní čísla adjacenční matice grafu | Karel.brinda | 15. 1. 2012 | 14:57 | cast1_kapitola13.tex | |
Kapitola2_1 | editovat | Brouwerova věta o pevném bodě | Karel.brinda | 15. 1. 2012 | 15:11 | cast2_kapitola1.tex | |
Kapitola2_2 | editovat | Pravděpodobnostní důkazy v teorii grafů | Karel.brinda | 15. 1. 2012 | 15:12 | cast2_kapitola2.tex | |
Kapitola2_3 | editovat | Extremální teorie grafů | Karel.brinda | 15. 1. 2012 | 15:16 | cast2_kapitola3.tex | |
Kapitola2_4 | editovat | Ramseyovská čísla | Karel.brinda | 15. 1. 2012 | 15:18 | cast2_kapitola4.tex | |
Kapitola3_1 | editovat | Obyčejné mocninné řady | Karel.brinda | 15. 1. 2012 | 15:22 | cast3_kapitola1.tex | |
Kapitola3_2 | editovat | Exponenciální generující funkce | Karel.brinda | 15. 1. 2012 | 15: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}