01ZTGA:Kapitola1 8

Z WikiSkripta FJFI ČVUT v Praze
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}

Citováno z „https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01ZTGA:Kapitola1_8&oldid=4516“