\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[TS1,T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}

\hoffset=-3cm
\textwidth=18cm
\voffset=-3cm
\textheight=26cm

\date{2010-04-30}
\title{Лекции по дискретке}
\author{Зайцев Вадим}

\begin{document}
\maketitle

\subsubsection{Лемма 23}
	Для всякого графа $G$: $\alpha_1(G) \le \beta_0(G)$
	
\subsubsection{Теорема 20 (Кёниг, 1916)}
	Для любого двудольного графа $G$: $\alpha_1(G) = \beta_0(G)$.
	\begin{proof}
		Пусть $G$-граф. Докажем, что $\alpha_1(G) \ge \beta_0(G)$.\\
		Обозначин $\beta_0 = \beta_0(G)$\\
		Удаляем рёбра из $G$ пока не получим некоторый граф $G'$ такой, что $\forall e \in EG' \quad \beta_0(G-e)=\beta_0-1$.\\
		
		Докажем утверждение, что в $G'$ нет смежных рёбер.\\
		Пусть это гон и в $\exists e,g \in EG'$: $e$ и $g$ смежны в $G'$, общая вершина $v$. В графе $G'-e$ существуют вершин. покрытие $S_e \quad |S_e|=\beta_0-1$ и
		концы ребра $e$ не лежат в $S_e$.\\
		В графе $G'-g$ существует вершинное покрытие $S_g$ и концы ребра $g$ не принадлежат $S_g$.\\
		Рассмотрим порождённый подграф графа $G'$: $G''=G'( \{v\} \cup (S_e \setminus S_g) \cup (S_g \setminus S_e))$\\
		$|S_e \cap S_g| = t \quad |VG''|=1+2(\beta_0-1)-2t$\\
		$G''$ подграф графа $G \quad \Rightarrow  \quad G''$ - двудольный.\\
		Пусть $A$ - меньшая доля графа $G$. $|A| \le \frac{1}{2}|VG''| = \beta_0-1-t$. $A$ - верш. покрытия графа $G''$.\\
		Покажем, что $A'=A \cup (S_e \cup S_g)$ - вершинное покрытие графа $G'$.\\
			Возьмём произвольное ребро. Пусть $h \in EG'$.\\
			\begin{enumerate}
				\item $h\in\{e, g\}$\\
					$e,g \in EG'' \Rightarrow e,g$ покрыты мно-ом $A$, а значит и $A'$.	
				\item $h\not\in\{e, g\}$\\
					Тогда $h$ покрывается как $S_e$, так и $S_g$.
					\begin{enumerate}
						\item $x \in S_g \quad x \in S_e \Rightarrow x \in S_g \cap S_e \Rightarrow$ покр. $A'$.
						\item один конец приндалежит $S_e \setminus S_g$, а другой: $S_g \setminus S_e \Rightarrow h \in EG'' \Rightarrow h$ покрывается $A$.
					\end{enumerate}
			\end{enumerate}
			Следовательно $\beta_0(G') \le |A'| \le |A| + |S_e \cap S_g| \le \beta_0-1-t + t = \beta_0-1$ - противоречие с выбором графа $G'$ (противоречие с тем, что
			существуют 2 смежных ребра).\\
			
	Граф $G'$ состоит из независимых рёбер. $\beta_0(G') = \alpha_1(G') \quad \beta_0(G) = \beta_0(G') = \alpha_1(G') \le \alpha_1(G)$.\\
	Из леммы 23 следует, что $\beta_0(G) = \alpha_1(G)$.
	\end{proof}
	
\subsubsection{Теорема 21 (Кёниг о (0, 1)-матрицах)}
	Для любой (0, 1)-матриц максимальное число единиц, никакие 2 из которых не стоят в одном столбце и в одной строке, равно минимальному числу строк и столбцов,
	содержащих все единицы.
	\begin{proof}
		Пусть $G$ - двудольный граф, с долями $\{ v_1, v_2 ... v_n\}, \, \{ u_1 ... u_n \}$. Матрица смежности двудольного графа $G$:\\
		$A(G) = (a_{ij}) \mid a_{ij} = \begin{cases} 1,  \quad v_iu_j \in EG \\ 0, \quad else \end{cases}$. \quad
\begin{tabular}{|l|l|}
\hline
0 & $A$\\
\hline
$A^T$ & 0 \\
\hline		                                                                                                          \end{tabular}\\
		Биекция между двудольным графом с долями мощности $n$ и $m$ и мно-ом (0, 1)-матрица размера $n\times m$.\\
		Максимальное число единиц, никакие две из котрых не стоят в одной строке или столбце равно $\alpha_1(G)$ для соотв. графа $G$.\\
		Миниальнео число строк и столбцов, содержащих единицы рафно $\beta_0(G)$ соотв. графа $G$.
	\end{proof}
	
\subsubsection{Теорема 22 (Холл, 1935)}
	Пусть $G = (A, B, E)$ - двудольный граф. В $G$ существует паросочетание, покр. $A \quad \Leftrightarrow \quad \forall x \subseteq A \quad |N(X)) \ge |X|$
	\begin{proof}\hfil
		\begin{description}
			\item[$ \Rightarrow $)] Если существет $X \subseteq A:  \quad |N(X)| < |X|$, тогда паросоч., покр. $X$ не существует, а знчит нет паросч., поркывающего $A$.
			\item[$ \Leftarrow $)]Док-во индукцией по числу вершин в доле $A$:\\
				Если $|A|=1$ - очевидно верно\\
				Пусть $|A| \ge 2$. Рассмотрим 2 случая:
				\begin{enumerate}
					\item $\forall X \subset A \quad |X| < |N(X)|$\\
						Выберем ребро $uv \in E \quad v\in A, u \in B$.\\
						Рассмотрим новый граф $G' = G- v-u$. Обозначим $A' = A \setminus \{ v\}$.\\
						Пусть $X \subseteq A'$. $|X| < |N_G(X)|$, $|N_{G'}(X)| \ge |N_G(X)|-1$\\
						$|X| < |N_{G'}(X)|+1 \Rightarrow |X| \le |N_{G'}| + 1$. По индукционному предположению в графу $G'$ существуют паросчитания,
						покарывающие $A' \quad  \Rightarrow  \quad $ объединениям его с ребром $vu \quad  \Rightarrow  \quad $ получаем паросчитание в $G$ подграфа $A$.
					\item $\exists A' \subset A \quad |A'| = |N(A')|$\\
						Рассмотрим 2 порождённых подграфа:\\
						$G_1 = G(A' \cup N(A')) \quad G_2 = G(VG \setminus (A' \cup N(A')))$ - всё оставшееся\\
						Покажем, что $G_1$ и $G_2$ удовлетворяют условиям теоремы.\\
						В $G_1$: $\forall X \subseteq A' \quad N_G(A)=N_{G'}(X)$\\
						$|X| \le |N_G(X)| = |N_{G'}(X)| \quad  \Rightarrow  \quad G_1$ удовлетворяет условию теоремы.\\
						Пусть $X\subseteq A \setminus A'$. Рассмотрим $X \cup A'$ в $G$.\\
						$|X \cup A'| \le |N_G(X \cup A')| \le |N_{G_2}(X)| + |N_G(A')|$\\
						Вспоминаем, что $|A' \cup X| = |X| + |A'|$\\
						$|A'| = |N_G(A')|  \quad  \Rightarrow  \quad |X| \le |N_{G_2}(X)|$\\
						По индукционному предположению в $G_1$ существует паросоч., покрывающ. $A'$, в $G_2$ существует паросоч., покрывающ. $A\setminus A'$.
						Следовательно, их объединение - искомое паросо., покр. $A$.
				\end{enumerate}
		\end{description}
	\end{proof}
	
\subsubsection{Теорема 23 (Фребениус, 1917), теорема о свадьбах}
	Двудольный граф $G=(A,B,E)$ имеет совершенное паросочетание $ \quad \Leftrightarrow \quad |A|=|B|$ и для любого $X \subseteq A \quad |N(X)| \ge |X|$.
	
\subsubsection{Упражнение}
	\begin{enumerate}
		\item Вывести теоремы 20 и 22 из теоремы 23.
		\item Вывести теорему 20 из 22 и теорему 22 из 20.
	\end{enumerate}
	
\subsubsection{Теорема 24 (следствие из теоремы 22)}
	В любом непустом регулярном двудольном графе существую совершенные паросоч.
	
\subsubsection{Следствие 7}	
	Мно-во рёбер $k$-регулярного двудольного графа разбивается на $k$ совершенных паросоч.
	
\subsubsection{Следствие 8 (из теоремы 21)}
	Пусть $G=(A,B,E)$ - двудольный граф, $t \in Z^+, \, t \le |A|$.\\
	Тогда в графе $G$ существует паросоч. мощности $t \quad  \Leftrightarrow \quad \forall X \subseteq A$ верно $|N(X)| \ge |X| + t - |A|$.
	\begin{proof}
		$G' = (A, B', E')$, который получается следующим макаром:\\
		$B' = B \cup T \quad |T|=|A|-t$\\
		$E' = E \cup \{ uv \mid u \in T, \, v \in A \}$\\
		В $G$ существует паросоч. мощности $t \quad  \Leftrightarrow  \quad $ в $G'$ существует паросоч., покр. $A$ по т. 21 $\quad  \Leftrightarrow  \quad \forall X \subseteq A$\\
		$|X| \le |N_{G'}(X)| = |N_{G}(X)| + |A| - t$
	\end{proof}
	
\subsubsection{парам-пам-пам}
	$A$ - некоторое непустое конечное мно-во. $S = (S_1...S_n)$ - семейство подмно-в мно-ва $A$.\\
	Тогда $\{ x_1...x_n \} \subseteq A$ - система различных представителей для $S$ (с.р.п., трансверсаль), eсли $x_i \in S_i \, \forall i \, x_i \ne x_j\, i\ne j$\\
	Если $A=\{1,2...6\}$, то {{1,2,3}, {2,4,5}, {1,2}, {1,6}, {2,3}, {1,3}} не будет тем, чем надо, а если в последнем 3 заменить на 4, то будет.


\end{document}