\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-23}
\title{Лекции по дискретке}
\author{Зайцев Вадим}

\begin{document}
\maketitle

\subsubsection{Теорема 14 (Уитни, 1932). Следстиве из предыдущего}
	Граф $G$ является $k$-связным $\Leftrightarrow$ любая пара несовпадающих вершин соединены по карйней мере $k$ непересекающимися цепями.
	
\subsection{Независимость и покрытие}
	Мно-во вершин $W\subseteq VG$ называется \textbf{независимым}, если $\forall w, u \in W \quad uw\not\in EG$.\\
	Независимое мно-во \textbf{тупиковое (максимальное)}, если оно не является собственным подмножеством другого независимого мно-ва.\\
	Независимое мно-во наибольшей мощности - \textbf{наибольшее} назависимое мно-во. Мощность такого мно-ва называется \textbf{числом нзависимости} ($\alpha_0(G)$).
	
\subsubsection{Оценка числа независимости}
	$ \displaystyle \forall G \quad \alpha_0(G) \ge \sum_{v \in VG} (1+ \operatorname{deg}(v))^{-1}$
	\begin{proof}
		Пусть $G = K_n$. Тогда $\alpha_0(K_n) = 1$.\\
		$ \displaystyle \sum_{v \in VG} n^{-1} = \frac{n}{n} = 1$.\\
		Индукция по числу вершин для $G\ne K_n$:\\
		$|VG| \le 2$ - всё очевидно.\\
		Пусть $|VG| = n \ge 3$, для любого графа с меньшим число вершин теорема верна, $ G \ne K_n$.\\
		Выбираем $v$ - вершинка $G$ наименьшей степени. Т.к. $ G \ne K_n$, то $x \cup N(x) \ne VG$.\\
		$G' = G - x - N(x)$. По индукционному предположению в $ \displaystyle G': \, \alpha_0(G') \ge \sum_{v \in VG'} (1+ \operatorname{deg}(v))^{-1}$.\\
		Пусть $M' \subseteq VG', \, M'$ - независимо в $G'$, $|M'| = \alpha_0(G')$.\\
		$v \cup M'$ - независимо в $G \quad  \Rightarrow  \quad \alpha_0(G) \ge |x \cup M'| = \alpha_0(G')+1$.\\
		$\forall v \in VG' \quad  \operatorname{deg}_G(v) \ge  \operatorname{deg}_{G'}(v)$\\
		$ \displaystyle \sum_{v \in VG'} (1+ \operatorname{deg}_{G'} v)^{-1} \ge\sum_{v \in VG'} (1+ \operatorname{deg}_{G} v)^{-1}$\\
		$\forall v \in N(x) \quad  \operatorname{deg}_G(v) \ge  \operatorname{deg}_G(x)$\\
		$ \displaystyle \sum_{v \in N(x)} (1+ \operatorname{deg}_G(v))^{-1} \le \sum_{v \in N(x)}( \operatorname{deg}_G(x)+1)^{-1} = \frac{ \operatorname{deg}_G(x)}{\operatorname{deg}_G(x)+1}$\\
		Берём неравенства 1 и 3 строчками выше и подставляем их куда-то в начало:\\
		$ \displaystyle \alpha_0(G) \ge 1 + \sum_{v \in VG'} (1+ \operatorname{deg}_G(v))^{-1} \ge \frac{ \operatorname{deg}_G(x)+1}{\operatorname{deg}_G(x)+1}+\sum_{v\in VG'}(1+ \operatorname{deg}_G(v))^{-1} = \frac{ \operatorname{deg}_G(x)}{1+\operatorname{deg}_G(x)} + (1+ \operatorname{deg}_G(x))^{-1} + \sum_{v \in VG'} (1+ \operatorname{deg}_G(v))^{-1}$
		$ \displaystyle \ge \sum_v \in N(x)( \operatorname{deg}_G(v)+1)^{-1} + (1+ \operatorname{deg}_G(x))^{-1} + \sum_{v \in VG'}(1 +  \operatorname{deg}_G(v))^{-1} = \sum_{v\in VG}(1+ \operatorname{deg}_G(v))^{-1}$
	\end{proof}

\subsubsection{Следствие 5}
	Пусть $ \displaystyle d=\frac{1}{|VG|}\sum_{v \in VG}  \operatorname{deg}(v)$. Если $|VG|=n$, то $\alpha_0(G) \ge \frac{n}{1+d}$
	\begin{proof}
		С помощью неравенство Коши-Буняковского:\\
		$ \displaystyle \sum_{i=1}^n a^{^1/_2}_i b^{^1/_2}_i \ge (\sum_{i=1}^n a_i)^{^1/_2} + (\sum_{i=1}^n b_i)^{^1/_2}$\\
		$a_i = 1 +  \operatorname{deg} (v_i)$\\
		$b_i = (1+ \operatorname{deg}(v_i))^{-1}$\\
		Подставляем, попутно возводя в квадрат:
		$ \displaystyle n^2 \le \sum_{i=1}^n(1+ \operatorname{deg}(v_i) \cdot \sum_{i=1}^n(1+ \operatorname{deg}(v_i)^{-1}$\\
		$ \displaystyle  n \le (d+1) \sum_{i=1}^n (1+ \operatorname{deg} (v_i))^{-1} \Rightarrow \frac{n}{d+1} \le \alpha(G)$ по т. 15.
	\end{proof}
	
\subsubsection{Определение}
	Вершина покрывет вёбра, инциндентные ей. Мно-во вершин, покрывающих, все рёбра - \textbf{покрытие} (вершинное покрытие).\\
	Покрытие $W$ - тупиковое (минимальное), если $\forall V \subset W, \, V$ - не покрытие. Покрытие наименьшей мощности - наименьшее покрытие и его мощность
	обозначается $\beta_0(G)$ - число покрытия графа $G$.
	
\subsubsection{Лемма 20}
	Мно-во $U$ вершин графа $G$ является независимым $\Leftrightarrow$ $VG\setminus U$ - покрытие.
	\begin{proof}
		Упражнение
	\end{proof}
	
\subsubsection{Теорема 16}
	Для любого графа $G$: $\alpha_0(G) + \beta_0(G) = |VG|$.
	
\subsubsection{тра-ля-ля}
	Подмно-во вершин графа $G$ называется кликой, если все вершины попарно смежные.
	
\subsubsection{Лемма 21}
	Подмно-в вершин графа $G$ - кликой $\Leftrightarrow$ оно является независимым мно-вом в $\overline{G}$.

\subsubsection{Определение}
	Мно-во попарно несмежных рёбер называется \textbf{паросочетанием} (независимым мно-ом рёбер). Тупиковое и наибольшее паросочетнаия определяются аналогично вершинам
	и обозначается $\alpha_1(G)$.\\
	$\alpha_1(G) = \alpha_0(L(G))$ (по опред. рёберного графа(?))\\
	$\alpha_1(G) \le \frac{|VG|}{2}$
	
	Мно-во рёбер, покрывающих все вершин - рёберное покрытие. Тупиковое и наименьшее рёберное покрытие определяются аналогично. Обозначается $\beta_1(G)$.
	
\subsubsection{Теорема 17 (Галлан, 1959)}
	Для любого графа $G$ порядка $n$ без изолированных вершин верно $\alpha_1(G) + \beta_1(G) = n$.
	\begin{proof}
		Пусть $\alpha_1 = \alpha_1(G), \, \beta_1 = \beta_1(G)$\\
		Докажем: $\alpha_1 + \beta_1 \le n \quad \alpha_1 + \beta_1 \ge n$
		\begin{enumerate}
			\item Пусть $M$ - наибольшее паросочетание в $G$. Пусть $V'$ - мно-во вершин, не покрытых $M$. \\
				Либо $V'$ - пусто, либо $V'$ - независимое мно-во вершин. Для каждой вершины из $V'$ выберем ребро, инциндентне ей. получаем $E'$. (если $V' = \varnothing  \Rightarrow E' = \varnothing$).\\
				Поскольку $V'$ - независимо, то $|E'| = |V'| = n - 2 \cdot \alpha_1$.\\
				$E' \cup M$ - рёберное покрытие $\beta_1 \le |E' \cup M| = |E'| + |M| = n - 2\alpha_1 + \alpha_1 = n - \alpha_1$.
			\item Пусть $P$ - наименьшее рёберное покрыти графа $G$. $G' = G(P)$. В $G'$ нет циклов (собсна, очевидна). Нет даже цепей длины 3 (аналогична). Получаем, что $G'$ - есть.\\
				Каждая компонента связности графа $G'$ - дерево. Пусть $t$ компонент связности и число рёбер $k_1, k_2, ..., k_t$.\\
				В каждой компоненте выберем по одному ребру $ \Rightarrow $ получим паросочетания $M$. $|M| = t$.\\
				Имеем, $t \le \alpha_1$. Получаем, что $ \displaystyle n = \sum_{i=1}^t (k_i + 1) = t + \sum_{i=1}^t k_i = t + \beta_1 \le \alpha_1 + \beta_1$.
		\end{enumerate}
	\end{proof}

\subsubsection{Определение}
	Совершенное паросочитание - паросочитание, являющееся рёберным покрытием.
	
\subsubsection{Теорема 18}
	Мно-во рёбер полного графа $K_{2n}$ разбивается на совершенные паросочитания (1-факторизуем).
	\begin{proof}
		$V(K_{2n}) = \{ v_0, v_1, ..., v_{2n-1} \} \quad E_1 \cup E_2 \cup ... \cup E_{K_{2n}}$\\
		$E_1 =  \{ v_i v_{2n-1} \} \cup \{ v_{i-j} v_{i+j} \mid j=1,2...n \}$\\
		Упр. доказать, что $E_i$ - паросочитание. $E_i \cap E_j = \varnothing, \, i\ne j$.
	\end{proof}

\subsubsection{Теорема 19}
	Мно-во рёбер графа $Q_n$ разбивается на совершенные паросочитания
	\begin{proof}
		Упражнение.
	\end{proof}

\subsubsection{Лемма 21}
	Тупиковое рёберное покрытие является - наименьшее $\Leftrightarrow$ оно содержит наибольшее паросочитание.
	
\subsubsection{Лемма 22}
	Тупиковое паросочитание является наибольшим $\Leftrightarrow$ оно содержится в наименьшем рёберном покрытии.

\end{document}
