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

\begin{document}
\maketitle

\subsubsection{Лемма 7}
Пусть $G$ - связанный граф, $e \in G$.
\begin{enumerate}
	\item если $e$ принадлежит некоторому циклу нашего графа, $G-e$ - связан.
	\item если $e$ не принадлежит никакому циклу, то граф $G-e$ не связан и имеет две компоненты связанности.
\end{enumerate}
	\begin{proof}\hfill
		\begin{enumerate}
			\item $e=vu \in C$ - цикл. $C$ состоит зи $vu$ и $(u,v)$-цепи.\\
				$\forall x,y$ в $(x,y)$-цепи, содержащей ребро $e$ заменим $e$ на $(u,v)$-цепь. Получим $(x,y)$-маршрут, не содержащий $e$.\\
				$x$ и $y$ связаны в $G-e  \Rightarrow G-e$ - связн.
			\item $G-e$ - не связан. $v$ и $u$ в разных компонентах связанности: $G_v, G_u$.\\
				$\forall x\ne u \quad \exists (x,y)$-цепь в графе $G$.\\
				Если $e$ входило в эту цепь, тогда $x\in G_v$, иначе $x \in G_u$.
		\end{enumerate}
	\end{proof}

\subsubsection{Теорема 1}
	$\forall (n,m)$-графа с $k$ компонентами связности верны два неравенства: $ \displaystyle n-k \le l \le \frac{(n-k)(n-k+1)}{2}$, при чём обе оценки достижими.
	\begin{proof}\hfil
		\begin{description}
			\item[верхняя)] Пусть $G$ - $n$-граф с $k$ компонентами связности с максимальным число рёбер. Очевидно, что $G$ - дизъюнктное объединение полных графов
				($G = K_{n_1} \cup ... \cup K_{n_k}$). Пусть $n_1 \ge n_2 \ge ... \ge n_k$. Покажем, что $n_2 = n_3 = ... = n_k = 1$.\\
				Пусть не так ($n_2 > 1$). Рассмотрим $v \in K_{n_2}$. Рассмотрим граф $G' = (K_{n_1} + v) \cup (K_{n_2} - v) \cup K_{n_3} \cup ... \cup K_{n_k} $ - 
				удалили $n_2-1$ рёбёр. Добавили $n_1$ ребёр. Получили, что в $G'$ добавили больше, чем удалили. Противоречие к предположению в самом начале.\\
				В $G$ у нас $\frac{n-k+1}{2}$ рёбер.
			\item[нижняя)] Индукция по числу рёбер:\\
				$m=0$ - всё очевидно, равенство есть.\\
				Пусть $m>0$ и для всех графов с меньшим число рёбер наше неравенство верно.\\
				Рассмотрим $(n,m)$-граф $G$ с $k$ комп. связности. Возьмём некоторое $e \in EG$ и безжалостно удалим его: $G_1 = G-e$. $G_1$ - $(n,m-1)$-граф с
				$k_1$ компонентами связности. По лемме 7 имеет, что $k_1 \le k+1$. По индукционному предположению $n-k_1 \le m-1 \Rightarrow m\ge n-k_1+1 \ge n-k+1-1=n-k$.\\
				Пимер такого графа: $G = O_{k-1} \cup P_{n-k}$.
		\end{description}

	\end{proof}

\subsubsection{Следствие 2}
	Пусть $G$ - $(n,m)$-граф. Если $ \displaystyle m>\frac{(n-2)(n-1)}{2}$, то $G$ - cвязный.
	\begin{proof}\hfil\\
		Пусть у $G$ - $k$ компонент связности. Если $k\ge 2$, то по теореме 1 $m \le \binom{n-k+1}{2} \le \binom{n-1}{2}$ - противоречие.
	\end{proof}

\subsubsection{Определение}
	Пусть $G=(V,E)$ - связен. $d(v,u)$ - длина кратчейшей $(v,u)$-цепи, положим $d(v,v)=0$.
	\begin{enumerate}
		\item $d(v,u) \ge 0, \quad d(v,u) = 0\Leftrightarrow v=u$
		\item $d(v,u) = d(u,v)$
		\item $d(u,v) + d(v,w) \ge d(u, w) $
	\end{enumerate}
	$d(u,v)$ - расстояине меджу $u$ и $v$.\\
	\textbf{Эксцентриситет} вершины $v$ - $e(v) =  \underset{n\in VG}{\max} d(v,u)$.\\
	\textbf{Радиус} графа $G$ - $r(G) = \underset{v \in VG}{\min} e(v)$. \textbf{Диаметр} графа $G$ - $d(G) = \underset{v\in VG}{\max} e(v)$.\\
	Вершина $v \in VG\mid e(v) = r(G)$ называется \textbf{центральной} вершиной. Мно-во всех центральных вершин - \textbf{центр графа}.\\
	Вершина $v \in VG\mid e(v) = r(G)$ называется \textbf{периферийной} вершиной.
	
	
	
\subsection{Двудольные графы}
	
\subsubsection{Лемма 8}
	$\forall G$ - связного, $r(G) \le d(G) \le 2\cdot r(G)$.

\subsubsection{Определение}
	Граф $G=(V,E)$ - двудольный, если $\exists V(\text{разбиение}) = A \cup B \mid \forall e \in G$ концы этого ребра лежат в разных мно-вах.\\
	$K_{n,m}$ - полный двудольный граф $V = A \cup B,\, |A|=n,\, |B|=m, \quad E = \{ ev \mid u \in A, v \in B \}$.
	
\subsubsection{Теорема 2 (критерий двудольности)}
	$G$ - двудольнй $\Leftrightarrow$ в $G$ нет циклов нечётной длины.
	\begin{proof}\hfil
		\begin{description}
			\item[$ \Rightarrow $)] $C$ - цикл в $G$. $C = v_1v_2v_3v_4...v_e,_v{e+1}=v_1$. $V = A \cup B, \quad v_1,v_3,v_5... \in A, \quad v_2,v_4,v_6 \in B$,
				т.е. все нечётные в $A$, все чётные $B$.
			\item[$\Leftarrow$)] По лемме 5 граф - двудольный $\Leftrightarrow$ все его комп. связности - двудольные. Пусть $G$ - связен, $n>1$, нет циклов
				нечётной длины. Докажем, что он - двудольный. Рассмотрим $v \in VG$.\\
				$V = A \cup B$: $v \in A$. $d(v,u)$ - чётно, то $u \in A$, $d(v,u)$ - нечётно, то $v \in B$.\\
				Докажем, что в $A$ и в $B$ нет рёбер.\\
				Предположим, что это не так. $e = uw \in EG$, $u, w \in$ одному мно-ву ($A$ или $B$). По построение $u, w \ne v$. Рассмотрим кратчаяшие цепи:
				$U$ - кратчайшая $(u,v$-цепь, $W$ - кратчайшая $(w,v)$-цепь. Длины этих цепей имеют одинаковую чётность. Пусть $v_1$ - последняя, начиная с $v$,
				общая вершина цепей $U$, $W$, лежащая на $U$.\\
				$(v, v_1)$ - подцепи цепей $U$ и $W$ имеют одинаковую длину, поэтому $(v_1, u)$-подцепь цепи $U$ и $(v, w)$-подцепь цепи $W$ имеют одинаковую
				чётность длины. Их объединение с ребром $uw$ даёт цикл нечётной длины. Противоречие. Следовательно, граф является двудольным.
		\end{description}
	\end{proof}
	
\subsection{Ориентированный граф}
\subsubsection{Определения}
	Орграф - это пара $G=(V,D)$, где $V$ - непустое мно-во, а $D \subseteq V \times V$. Элементы $V$ - вершины, элементы $D$ - дуги.\\
	$(v,u) \in D$. $vu$ - выходит из $v$ и входит в $u$.\\
	Мультиграф, диаграмма.\\
	Если в мультиграфе убрать все ориентации, то получим некоторый псевдограф, который называется основанием орграфа.\\
	Ормаршрут, орцепь, орцикл (контур).\\
	Вершина $v$ достижима из $u$, если $\exists$ ориентированная $(u,v)$-цепь.\\
	Орграф $G$ - сильносвязанный, если любая вершинка достижима из любой другой.\\
	Пуст $G$ - орграф, $v\in VG$. Полустепень исхода $v$ обозначается $ \operatorname{deg}^+ v$ - кол-во дуг графа, исходящих из вершины $v$.
	Полустепень захода $v$ - $ \operatorname{deb}^-v$ - кол-во дуг, входящих в $v$.
	
\subsubsection{Лемма 9 (Орлемма о рукопожатиях)}
	$\forall$ орграфа $G=(V,D)$: $ \displaystyle \sum_{v \in V}  \operatorname{deg}^+v = \sum_{v\in V}  \operatorname{deg}^- v = |D|$.

\subsection{Матрицы}
	Граф $G$ - помеченный, если вершины $\{1, ..., n\}$. Помеченные графы $G$ и $H$ равны $\Leftrightarrow VG=VG,\, EG=EH$.\\
	$G$ - помеченный граф, тогда матрица смежности графа $G$ - это $n \times n$ матрица $A = A(G) = (a_{ij})$, определяемая следующим образом:\\
	$a_{ij} = \begin{cases} 1, \quad ij \in EG \\ 0 \end{cases}$.\\
	$A$ - бинарная симметричная матрица с нулевой главой диагональю.\\
	Если у нас мультиграф или псевдо граф, то $a_{ij}$ - это кол-во рёбер, соединяющих $i$ и $j$, петли отмечаются дважды.\\
	Если $G$ - оргаф, то $A(G)$:\\
	$a_{ij} = \begin{cases} 1,  \quad ij \in DC \\ 0 \end{cases}$.\\
	Матрицы смежности для $G$ - подобны.
	
\subsubsection{Теорема 3}
	Пусть $A = (a_{ij})_{n\times n}$ - матрица смежности мультиграфа $G$. Рассмотрим $A^k = (\gamma_{ij}), \, k \in \mathbb{Z_+}$.\\
	Тогда $\gamma_{ij}$ - число маршрутов из $(i, j)$-маршрутов длины $k$.
	\begin{proof}
		Индукция по $k$:\\
		$k=1$ - очевидно.\\
		Пусть $k>1$. По индукционному предположению $^{k-1} = (\beta_{ij})_{n\times n}$, где $\beta_{ij}$ - число $(i,j)$-маршрутов длины $k-1$.\\
		$ \displaystyle A^k = (\gamma_{ij}) = A^{k-1} \cdot A. \quad \gamma_{ij} = \sum_{s=1}^n \beta_{is} a_{sj} $ - число $(i,j)$-маршрутов длины $k$.
	\end{proof}
	
\subsubsection{Определение ?}
%	$G$ - помеченный. $VG = \{
	Матрица Крихгофа.\\
	$B = B(G) = (b_{ij})_{n\times n}$\\
	$b_{ij} = \begin{cases} -1, \quad ij \in EG \\ 0, \quad ij \not\in EG, i\ne j \\  \operatorname{deg}(i), \quad i=j \end{cases}$.


\end{document}
