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

\begin{document}
\maketitle

\subsubsection{Лемма 16}
	Любые 2 блока имеют не более одной общей вершины.
	
\subsubsection{Лемма 17}
	Если блок содержит вершины и рёбра, то он содержит $\forall(u,v)$ - цепь графа $G$.
	
\subsubsection{Лемма 18}
	Если вершина $v$ входит более, чем в один блок графа $G$, то $v$ - точка сочленения графа $G$
	
\subsubsection{парам-пам-пам}
	$B=\{B_1, B_2, B_3 \}$ - мно-во всех блоков графа $G$.\\
	$C = \{c_1, ..., c_l\}$ - мно-во точек сочленения графа $G$.\\
	$bc(G) = (B\cup C, M) \quad M=\{B_iC_j \mid B_i \in B, \, S \in C, \, C_j \in C, \, C_j \in B_i \}$.
	
\subsubsection{Лемма 19}
	Если $G$ - связен, то $ \operatorname{bc}(G)$ - дерево.
	\begin{proof}
		$G$ - связен, то $ \operatorname{bc}(G)$ - связен.\\
		Пусть циклов нет, тогда в $ \operatorname{bc}(G)$ есть цикл. $C_{j1}, B_{i1}, C_{j2}, B_{j2}, ..., C_{jk}, B_{ik}, C_{j1}$.\\
		$B_{j_s}$ содержит $C_j$ и $C_{j_s+1}$ по лемме 17. $B_{js}$ содержит $(C_{js}, C_{js_1}$ - цепь.\\
		Обощения $ \Rightarrow $ цикл в $G$. Этот цикл содержит по кр. мере 2 вершины из каждого блока $ \overset{\text{Лемма 17}}{\Rightarrow} $ весь цикл содержит все вершины из блоков $ \Rightarrow $ все блоки содержит 3 общих вершины $ \overset{\text{Лемма 16}}{\Rightarrow} $ противоречие.
	\end{proof}

\subsubsection{Определение}
	$S \subseteq VG, \, S$ - разделяет несмежные вершины $u$ и $v$, если в графе $G-S$ вершины $u$ и $v$ принадлежат разным компонентам связности.\\
	Дву $(u,v)$-цепи не пересекаются, если нет общих вершин, кроме конечных.

\subsubsection{Теорема 13 (Менгер, 1927)}
	Минимальное число вершин, разделяющих две несмежные вершины $u$ и $v$ равно максимальному числу попарно непересекающихся простых $(u,v)$-цепей.
	\begin{proof}
		Наибольшее число попарно непересекающихся простых $(u,v)$-цепей не больше минимального числа вершин, разделяющих $u$ и $v$. Докажем, что если наименьшее число
		вершин, разделяющих $u$ и $v$ в графе $G$ равно $k$, то существует $k$ попарно непересекающихся простых цепей.\\
		При $k=1$ - очевидно.\\
		Пусть для некоторого $k>1$ -- неверно. Пусть $t$ -- наименьшее такое $k$. $F$ - граф с наименьшим числом вершин, для которого не выполненено условие
		(которое после слова ``доказать'') для $t$.\\
		Бдем удалять из $F$ рёбра до тех пор, пока не получим некоторый граф $G$ такой, что $\forall e \in EG$ для разделения $u$ и $v$ в графе $G$ надо $t$ вершин,
		а в графе $G-e$ надо $t-1$ вершину.\\
		Т.о. имеется $G$ и $t$ такие, что теорема верна для
		\begin{enumerate}
			\item $\forall k < t$.
			\item $\forall$ графа с числом вершин, меньшим, чем $|VG|$.
			\item $\forall$ графа $G-e \, \forall e \in EG$.
		\end{enumerate}
		\textit{(док-во ниже)}
	\end{proof}

\subsubsection{Утверждение 1}
	В гарфе $G$ нет вершин, которые одновременно смежны с $u$ и $v$.
	\begin{proof}
		Пусть $w$ смежно с $u$ и $v$. Тогда в $G-w$ для разделения $u$ и $v$ достаточно $t-1$ вершины по пункту 2 в $G-w$ существует $t-1$ попарно непересекающихся
		простых $(u,v)$-цепей. Добавляем цепь $u,w,v \Rightarrow t$ попарно непересекающихся простых $(u,v)$ цепей в графе $G$. Противоречие с выбором графа $G$.
	\end{proof}
	
\subsubsection{Утверждение 2}
	Любое мно-во вершин $W$, разделяющих $u$ и $v$, $|W|=t$ смежно либо с $u$, либо с $v$.
	\begin{proof}
		Цепь, соединяющую $u$ с нек...
		
	\end{proof}

\begin{proof}\textit{(продолжение)}\\
	Рассмотрим некоторе $e=xy \in EG$. По условию 3 в $G-e$ существует $t-1$ вершина, разделяющая $u$ и $v$.\\
	В $(G-S_e)$ существует $(u,v)$-цепь и каждая точка цепи содержит ребро $e$.\\
	$(**)\forall e = xy: \Rightarrow $ 1) $x,y \not\in S_e$\\
	2) если $x\ne u, x \ne v$, то $S_e \cup \{x\}$ разделяет $u$ и $v$ в $G$.\\
	Рассмотрим кратчайшую $(u,v)$-цепь в графе $G$. $P=u, x_1, x_2, x_3, ..., x_m, v$.\\
	Рассмотрим $e=x_1x_2$. Из утвержджения 1 $x_2 \ne v$.\\
	$S_e = \{ y_1, ..., y_{t-1} \}$\\
	$W_1 = S_e \cup \{x_1\}$ по (**) разделяет $u$ и $v$. По утверждению 1, $x_1,v \not\in EG$. По утверждению 2, $W_1$ смежно с $u$. $\{y_1, ..., y{t-1} \}$ смежно с $u$ и не смежно с $v$.\\
	$W_2 = S_e \cup \{x_2\}$ по (**) разделяет $u$ и $v$. По утверждению 2 $x_2$ смежно с $u$. Противорчеие с выбором кратчайшей цепи
\end{proof}



\end{document}
