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

\begin{document}
\maketitle

\section{Теория графов}

\subsection{Опеределения}

\subsubsection{Определение}
	$V$ - непустое конечное мно-во.\\
	$V^{(2)}$ - всех двухэлементные подмно-ва мно-ва $V$.\\ \\
	$(V,E), \, E \subseteq V^{2}$ - называется граф (обыкновенный граф, простой граф, \textit{etc}).\\
	$V$ - вершнины, $E$ - рёбра.\\
	$G=(V,E) \quad VG$ - мно-во вершни, $EG$ - мно-во рёбер.\\
	$|VG|$ - порядок графа.\\
	$|G| = |VG|=n  \Rightarrow G$ - $n$-граф\\
	$|G|=n, \quad |EG|=m, \quad G\,-\, (n,m)$ - граф.\\
	
\subsubsection{Пример простого графа}
	--- picture 1 ----\\
	
\subsubsection{Ещё пара определений}
	\textbf{мультграф} - пара $(V,E)$, где $V$ - непустое конечное мно-во, $E$ - семейство (могут повторяться элементы) элементов из $V^{(2)}$.\\
	\textbf{псевдограф} - пара $(V,E)$, где $V$ - непустое конечное мно-во, $E$ - семейство нупорядоченных пар элементов из $V$, не обязательно различных.\\
	
\subsubsection{Пример графа с петялми}
	 --- picture 2 ----\\
	 
\subsubsection{Определения}
	Две вершины $u$ и $v$ \textbf{смежные}, если $\{u, v\} \in E$ и \textbf{не смежные} в противном случае.\\
	Если $e = \{u, v\} \in E  \Rightarrow $ ребро $e$ соединяет $u$ и $v$. $e=uv=vu$.\\
	Два \textbf{ребра смежные}, если они имеют общий конец.\\
	Ребро $e$ и вершина $v$ инцедентны, если $v$ является концом $e$.
	
\subsubsection{Адекватные примеры графов}
	\begin{enumerate}
		\item $K_n$ - полный граф из $n$ вершин.\\
			$|VK_n| = n, \quad K_n = (V, V^{(2)})$\\
			--- picture 3 ---\\
			$|EK_n| = \binom{n}{2}$.
		\item $O_n$ - пустой граф на $n$ вершинах.\\
			$O_n = \{ V, \\varnothing \}$ (нулевой, вполне несвязный граф.\\
		\item $P_n$ - простая цепь на $n$ вершни\\
			--- picture 4 ---
		\item $C_n$ - простой цикл на $n$ вершин.\\
			--- picture 5 ---
		\item Граф Петерсена\\
			--- picture 6 ----
		\item $Q_n$ - $n$-мерный куб.\\
			$VQ_n$ - мно-во всевозможных двоичных слов длины $n$. $VQ_n = \{ 0, 1\}^n$\\
			$EQ_n$ - две вершины смежные, если они различаются ровно одной позицией.\\
			--- picture 7 ---
	\end{enumerate}

\subsubsection{о\_О}
	$G=(V,E), \quad G'=(V', E')$.\\
	$G$ и $G'$ изоморфны ($ G \cong G'$), если $\exists$ биекция $\varphi:V \rightarrow V': \quad uv \in E \Leftrightarrow \varphi(u)\varphi(v) \in E'$.\\
	$\varphi$ - изоморфизм графов $G$ и $G'$.
	Если $G=G'$, то $\varphi$ - автоморфизм графа ($V$ и $V'$ совпадают).
	
\subsubsection{Определение}
	\textbf{Степень} вершины $v$ - число рёбер, инцедентных с вершиной $v$. $ \operatorname{deg}_G(v) =  \operatorname{deg}(v)$.\\
	\textbf{Окружение} вершины $v$ - это мно-во всех вершин, смежных с $v$. $ N_G(v) = N(v) $.\\
	Для обыкновенного графа $ \operatorname{deg}(v) = |N(v)|$.\\
	Если $ \operatorname{deg}(v)=0$, то $v$ - \textbf{изолировнная}.\\
	Если $ \operatorname{deg}(v)=1$, то $v$ - \textbf{висячая}. А ребро, инцедентное висячей вершине, тоже \textbf{висячее}.
	
\subsubsection{Лемма 1 (о рукопожатиях)}
	Пусть $G$ - произвольный граф, тогда $ \displaystyle \sum_{v \in VG}  \operatorname{deg}_G(v) = 2|EG|$.
	\begin{proof} К. О.\end{proof}

\subsubsection{Следствие 1}
	Любой граф содержит чётное число вершин нечётной степени.
	
\subsubsection{Определение}
	Если в $G$, $\forall v \in VG \quad  \operatorname{deg}(v) = K  \Rightarrow G$ - $k$-регулярный граф.\\
	Полный граф является $(n-1)$-регулярный, граф Петерсена является 3-регулярным графом, $Q_n$ - $n$-регулярным.



\subsection{Подграфы, операции над графами}

	Граф $H$ называется подграфом графа $G$, если $VH \subseteq VG, \, EG \subseteq EG$.\\
	--- picutre 8 ---(?)\\
	Если $VH = VG$, то $H$ - оставный подграф.
	
\subsubsection{Определения подграфов}
	Пусть $U \subseteq VG \quad D=\{ uv \mid u,v \in U, \quad uv \in EG$ \}.\\
	Тогда $G(U) = (U, D)$ - подграф, порождённый мно-вом вершин $U$.\\
	Пусть $ \subseteq EG, \quad U$ - мно-во концевых вершин рёбер из $D$.\\
	Тогда $G(D) = (U,D)$ - подргаф, порождённый мно-вом рёбер $D$.

\subsubsection{Определения операций}
	Пусть $v \in VG$, $G - v$ - граф, получающийся из $G$ удалением вершинки $v$ и всех рёбер, ей инцедентных.
	$e \in EG$, $G-e$ - удаление ребра. $V(G-e) = VG, \, E(G-e) = EG \setminus \{ e \}$.\\
	Если $uv \not\in EG, \, u,v \in VG \quad G+uv = (VG, EGV\{uv\})$.\\
	Граф $H$ называется объединением графов $G$ и $F$, если $VH = VG \cup VF, \, EH = EG \cup EF$, будем обозначать $H=G \cup F$.\\
	Если $VG \cap VG \ne \varnothing  \quad \Rightarrow  \quad G \cup F$ - дизъюнктивное объедиение.\\
	Пусть $G_1 = (V_1, E_1), \, G_2 = (V_2, E_2)$.\\
	Произведение $G = G_1 \times G_2$ называется $G = ( V_1 \times V_2, E)$.\\
	$(v_1, v_2)$ смежные с $(u_1, u_2)  \quad \Leftrightarrow \quad $ или ($ v_1 = u_1, \quad  v_2,u_2 \in E_2 $) или ($ v_2 = u_2,  \quad v_1,u_1 \in E_2$).

\subsubsection{Лемма 2}
	$Q_1=K_1,\, \forall n \ge 2 \quad G_n = G_{n+1} \times K_1$
	\begin{proof}
		упражнение :(
	\end{proof}

\subsubsection{тра-ля-ля}
	Дополнение к графу $G = (V,E)$ есть $\overline{Q} = (V, \overline{E})$, где $\overline{E} = \{ uv \mid uv \not\in E, \quad u,v \in V \}$.\\
	Соединение графов $G_1 = (V_1, E_1)$ и $G_2 = (V_2, E_2)$ и $ V_1 \cap V_2 = \varnothing$ - граф $ G_1 + G_2$ - дизъюнктное объединения $G_1$ и $G_2$ и добавлением ребёр $v_1v_2 = v_2 \in V_1, v_2 \in V_2$.\\
	Для графа $G = (V,E)$ рёберным графом называется $L(G), \quad VL(G) = EG, \, e_1e_2 \in EL(G) \Leftrightarrow e_1$ и $e_2$ смежные в $G$.
	
	через последовательность $v_1, e_1, v_2, e_2, \ldots v_t, e_t, v_{t+1}, \quad \forall i \in \{1, \ldots t\}, e_k = v_iv_{i+1}$ называются маршрутом, соединяющим $v_1$ и $v_t$. $(v_1, v_{t+1})$ - маршрут. $t$ - длина.\\
	Маршрут называется цепным, если все его рёбра различны.\\
	Если в цепи все вершины разные (кроме, возможно, конечной), то такая цепь назывется простой.\\
	Маршрут назывется называется циклическим, если $v_1 = v_t$. Тогад циклическая цепь называется циклом, а циклическая простая цепь называется простым циклом.
	
\subsubsection{Лемма 3}
	При $v \ne u$ всякий $(u, v)$ маршрут содержит простую $(u,v)$ цепь.
	
\subsubsection{Лемма 4}
	Всякий цикл содержит простой цикл.
	
\subsubsection{adf}
	$v$ и $u$ - связные в $G$, если $\exists (u,v)$ - простая цепь. $G$ - связный, если $\forall u,v \in VG,  \quad u,v $ - связные.\\
	Отноешние связнаости в $G$ - отношение эквивалентности.\\
	$\forall $ кл. экваивалентности - подграф, порождённый веринами этого класса - компоненты связности.\\
	Максимальный по включению вершин и рёбер связный подграф графа $G$ назывется компонентной связности графа $G$.

\subsubsection{Лемма 5}
	Любой граф является дизъюнктным объединением своих компонент связности.
	
\subsubsection{Лемма 6}
	Для любого графа либо он сам, либо его дополнение является связным.

\end{document}
