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

\begin{document}
\maketitle

\subsubsection{Лемма 10}
	Алгебрарические дополения всех элементов матриц Кирхгофа равны между собой.
	
\subsubsection{Определение}
	$G$ - помеченный $n$-граф, $VG=\{1,...,n\},\, EG = \{e_1,...,e_n\}$.\\
	Матрица инцедентности графа $G$:\\
	$ \displaystyle I = I(G)=(\alpha_{ij})_{n\times m}, \quad \alpha_{ij} = \begin{cases}1, \quad \text{вершина $j$ и ребро $e_i$ - инцидентны}\\0 \end{cases} $\\
	Матрица инцидентности для орграфа $G,  \quad VG=\{1,...,n\}, \, DG=\{e_1,...,e_m\}, \, \alpha_{ij} = \begin{cases} 1, \quad \text{$e_i$ выходит из $j$} \\
	                                                                                                      -1, \quad \text{$e_i$ входит в $j$} \\ 0
	                                                                                                     \end{cases}$\\
	$G$ - ориентируем $\forall$ ребра. Полученный орграф - ориентматрица графа $G$.
	
\subsubsection{Лемма 11}
	$B$ - матрица Крихгофа графа $G$, $I$ - матрица инцидентности некоторая ориентация графа $G$ (нумерация с единицы).\\ Тогда $B=II^T$.



\subsection{Деревья}

\subsubsection{Определение}
	Ациклический граф - \textbf{лес}. Ациклический связный граф - \textbf{дерево}.
	
\subsubsection{Теорема 4 (Характеризация деревьев}
	$(n,m)$-граф $G$. Следующие условия эквивалентны:
	\begin{enumerate}
		\item $G$ - дерево.
		\item $G$ - связный, $m=n-1$
		\item $G$ - ациклический, $m=n-1$
		\item В графе $G$ любые 2 вершины связаны одной простой цепью.
		\item $G$ - ациклический и добавление одного нового ребра приводит к появлению ровно одного простого цикла.
	\end{enumerate}
	\begin{proof}\hfil
		\begin{description}
			\item[$1  \Rightarrow 2)$] Докажем, что в любом $(n,m)$-дереве $m=n-1$. Индукцией по $m$:\\
				$m=0 \Rightarrow n=1$.\\
				Пусть $G$ - произвольное $(n,m)$-дерево и для всех деревьев с меньшим числом рёбер наше равенство выполняется.\\
				Возбмём некоторое ребро $e \in EG$. $e$ не принадлежит никакому циклу, т.к. в нашем графе их нет $\overset{\text{по лемме 7}}{\Rightarrow}$ в $G-e$ ровно 2 компонентны
				связности $G_1$ и $G_2$ - деревья $(n_1,m_1)$ и $(n_2,m_2)$. По индукционному предположению $m_1 = n_1-1, \, m_2=n_2-1$. Тогда для нашего графа имеем
				$m=m_1+m_2+1=n_1+n_2-1=n-1$.
			\item[$2  \Rightarrow 3)$] Пусть в графе $G$ есть цикл, рассмотрим некоторе ребро $e$ из этого цикла $\overset{\text{по лемме 7}}{\Rightarrow} $  $G-e$ - связан. и является
				$(n,n-2)$-графом, что противоречит первой теореме.
			\item[$3  \Rightarrow 4)$] Докажем, что $G$ - связен. $G$ - ациклический - лес. Каждая компонента связности $G_1,...,G_k$ - дерево. Т.к. доказано, что из
				$1 \Rightarrow 2 (\forall i\, G_i)$ - $(n,m)$-граф, то $m_i=n_i-1$. $n-1=m=m_1+...+m_k = n_1+...+n_k-k=n-k \Rightarrow k=1 \Rightarrow $ граф связен
				$ \Rightarrow \forall u,v \quad \exists (u,v)$ - цепь.\\
				Пусть $\exists u,v$ - в $G$ есть две различные $(u,v)$-простоые цепи $L_1$ и $L_2$. Пусть $x$ - последняя вершина общего начала путей $L_1$ и $L_2$
				начиная с $u$, $y$ - следующая на цепи $L_1$ $ \Rightarrow $ $G-xy$ - остаётся связным $\overset{\text{по лемме 7}}{ \Rightarrow }$ $xy$ принадлежит
				некоторому циклу $ \Rightarrow $ противоречие с ацикличностью.
			\item[$4  \Rightarrow 5)$] В любом цикле 2 вершины соединены не менее 2 различными путями $ \Rightarrow $ в $G$ нет циклов (чё?). Пусть $u,v \in VG$.
				$uv \not\in EG$, тогда единственная $(n,v)$-цепь в $G$ вместе с ребром $uv$ даёт единственный цикл
			\item[$5  \Rightarrow 1)$] Докажем, что $G$ - связный. От противного: пусть $G$ - не связен. Пусть $u$ и $v$ в разных компонентах связности $ \Rightarrow $
				$G + uv$ не имеет циклов (по лемме 7).
		\end{description}
	\end{proof}
	
\subsubsection{Следствие 3}
	В любом дереве порядка $n\ge 2$, то в нём имеется не менее 2 висячих вершин. (т.е. вершин степени 1).
	\begin{proof}
		$G$ - $(n,m)$-дерево, $n\ge2$. Тогда по лемме о рукопожатиях $ \displaystyle \sum_{v \in VG}  \operatorname{deg}(v)=2m = 2n-2 \Rightarrow $ по принципу Дирихле
		$\exists$ 2 вершины степени 1.
	\end{proof}

\subsubsection{Теорема 5}
	Центр любого дерева состоит из одной или двух смежных вершин.
	\begin{proof}\hfil\\
		$n=1$ - очевидно.\\
		$n=2$ - аналогично.\\
		Пусть $T$ - дерево порядка $n\ge2$. Рассмотрим дерево $T'$, которое получается из $T$ удалением всех висячих вершин.\\
		$\forall v \in T' \quad  \operatorname{e}_{T'}(v)= \operatorname{e}_T(v)-1  \Rightarrow$ центра $T$ и $T'$ совпали.\\
		Продолжаем, пока порядок дерева $>2$.
	\end{proof}

\subsubsection{Определение}
	$G$ - связный. Оставной подрграф графа $G$, явля-ся деревом, называется, как ни странно, оставным деревом графа $G$.\\
	Оставной подграф графа $G$, являющийся дизъюнктным объединением оставным деревьев его компонент связности - \textbf{остов} графа $G$.

\subsubsection{Лемма 12}
	Число рёбер произвольного $(n,m)$-графа $G$ с $k$ компонентами связности, которое надо удалить, чтобы получить остов нашего графа $G$ не зависит от последовательности
	удаления и равно $m-n+k$.

\subsubsection{Лемма 13}
	Каждый ациклический подграф графа $G$ содержится в некотором его оставе.
	\begin{proof}
		Пусть $G$ связен, $H$ - ациклический подграф графа $G$. Если $H$ - не остов, то рассмотрим $H'$ - $H$ с добавленными вершинами, не покрытми $H$, тогда $H'$
		- оставный, ациклический. Если $H'$ не явялется оставным $ \Rightarrow $ не связен.\\
		Пусть $H_1$ - комп. связности графа $H$. Тогда $\exists u,v \in VG \quad u \in VH_1,\, v \not\in VH_1, \, uv \in EG$.\\
		Тогда $H'+uv$ - ациклический подграф графа $G$, имеющий меньшее число компонент связности, чем $H'$.\\
		Повторяем до тех ор, пока не остаентся одна компонента связности $ \Rightarrow $ остов $G$, содержащий граф $H$.
	\end{proof}

\subsubsection{Лемма 14}
	Если $S$ и $T$ - остовы графа $G$, то $\forall e_1 \in ES \quad \exists e_2 \in ET: \quad S-e_1+e_2$ - остов графа $G$.
	\begin{proof}
		Пусть $G$ - связен. Граф $S-e_1$ имеет две компоненты связности $A$ и $B$. Но $T$ - связен $ \Rightarrow $ $\exists$ ребро $e_2 \in ET$ с концами в $A$ и $B$
		$S-e_1+e_2$ - остов $G$.
	\end{proof}

\subsubsection{Теорема 6 (Кирхгоф, 1847)}
	Число ост. деревьев в связном графе $G$ порядка $n\ge 2$ равно алгебрарическому дополнению каждого элемента матрицы Кирхгофа $B(G)$.
	\begin{proof}
		Доказательства есть, но нам его учить не надо *YAHOO*.
	\end{proof}

\subsubsection{Следствие 4}
	При $n>1$ число остовных деревьев в полном графе $K_n$ равно $n^{n-2}$.
	\begin{proof}
		тут должны быть матрицы, которые мне было лень набирать...
	\end{proof}

\subsubsection{Теорема 7 (Кэли, 1897)}
	Число помеченнымх деревьев подрядка $n\ge 2$ равно $n^{n-2}$.
	
\subsubsection{Определение (Код Прюфера)}
	Пусть $T$ - помеченное дерево $VT=\{1,...,n\}$. Сопоставим $a=(a_1,...,a_{n-1})$:\\
	\begin{enumerate}
		\item В дереве $T$ находим висячую вершинку $v$ с наименьшим номеров, тогда $a_1$ - номер вершины, смежной с $v$. $T_1 = T-v$. 
		\item $\forall i \quad 2\le i \le n-1 \quad $ в $T_{i-1}$ находим висячую вершинку $v_i$ с наименьшим номеров $ \Rightarrow $ $a_i$ - номер её соседа, 
			$T_i = T_{i-1} - v_i$.
	\end{enumerate}
	Сво-ва $a$:
	\begin{enumerate}
		\item $a_{n-1} = n$
		\item $a_i \in \{a_1,...,a_n\} \quad \forall i: 1 \le i \le n-2$
	\end{enumerate}


\subsubsection{Теорема 8 (Код Прюфера}
	Если $a=(a_1,...,a_n)$, обладает сво-ми 1 и 2, то существует и единственным помеченным деревом $T$, для каждого $a$ - код Прюфера.
	\begin{proof}\textit{?}\\
		$b_1,b_2,...,b_{n-1}$\\
		$b_i =  \operatorname{min} \{ 1,2,...,n\} \setminus \{b_1,..., b_{i-1}, a_i, ..., a_{n-1} \}$\\
		$T: \quad VT=\{1,2,...,n\} \quad ET=\{a_ib_i \mid i=1,....,n-1 \}$.
	\end{proof}


\end{document}
