Добавлена окончательная версия теории по экзамену по графам

1 files changed, 2647 insertions, 54 deletions

diff --git a/graphs-exam/graphs-exam.tex b/graphs-exam/graphs-exam.tex
index 338b357..571c862 100644
--- a/graphs-exam/graphs-exam.tex
+++ b/graphs-exam/graphs-exam.tex
@@ -12,6 +12,8 @@
 \usepackage{amssymb}
 \usepackage{braket} % \set
 \usepackage{hyperref}
+\usepackage{graphicx}
+\graphicspath{ {./images/} }
 
 \renewcommand{\emptyset}{\varnothing}
 \renewcommand{\qedsymbol}{$\blacksquare$}
@@ -20,8 +22,15 @@
 
 \input{style.tex}
 
+\title{Теория графов}
+\date{\the\year}
+
 \begin{document}
 
+\maketitle
+
+\tableofcontents
+
 \chapter*{Введение}
 
 \section{Декартово произведение. Бинарные отношения. Пустое и универсальное
@@ -309,7 +318,7 @@ $0_n$.
 \end{definition}
 
 \begin{definition}
-  Полный двудольный граф вида называется звездным графом или звездой.
+  Полный двудольный граф вида $K_{1,n}$ называется звездным графом или звездой.
   \label{def:star}
 \end{definition}
 
@@ -602,6 +611,17 @@ layoff. Критерий графичности Эрдеша-Галлаи.}
 \end{definition}
 
 \begin{definition}
+  Немым изображением графа называют его изображение, в котором опущены имена
+  меток.
+\end{definition}
+
+Очевидно, что два графа изоморфны $\iff$ они допускают одинаковое немое
+изображение.
+
+Очевидно, что отношение изоморфизма является отношением эквивалентности. Классы
+этого отношения называются абстрактными графами.
+
+\begin{definition}
   Метод канонических представителей:
   \begin{enumerate}
     \item Определить способ кодирования объектов;
@@ -644,8 +664,8 @@ layoff. Критерий графичности Эрдеша-Галлаи.}
 \begin{definition}
   Два ребра $\set{u_1, v_1}$ и $\set{u_2, v_2}$ называются подобными, если
   существует автоморфизм $\varphi$, такой, что образом первого ребра будет
-  второе ребро ($\varphi(\set{u_1, v_1}) = \set{u_2, v_2}$). Если $\varphi(u) =
-  u_2, \varphi(v_1) = v_2$, или $\varphi(u_1) = v_2, \varphi(v_2) = v_1$.
+  второе ребро ($\varphi(\set{u_1, v_1}) = \set{u_2, v_2}$). Если $\varphi(u_1)
+  = u_2, \varphi(v_1) = v_2$, или $\varphi(u_1) = v_2, \varphi(v_2) = v_1$.
 \end{definition}
 
 \begin{definition}
@@ -738,6 +758,15 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл�
 \section{Отказоустойчивые реализации. Вершинные и реберные расширения.
 Минимальные, неприводимые, тривиальные, точные расширения.}
 
+Пусть граф является функциональной моделью некоторой технической системы.
+Вершины графа соответствуют элементам, а рёбра --- связям. Элементы могут
+иметь различные типы, и в этом случае вершинам приписывают метки.
+
+Система, представленная орграфом $\vec{G_1}$, моделируется системой,
+представленной графом $\vec{G_2}$, если $\vec{G_1}$ вкладывается в $\vec{G_2}$
+с сохранением типов элементов (вершина одного типа переходит в вершину того же
+типа).
+
 \begin{definition}
   Под отказом элемента системы будем понимать удаление из графа системы
   соответствующей вершины и всех её рёбер или дуг.
@@ -759,6 +788,14 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл�
   Система $\Sigma^*$ --- $k$-отказоустойчивая реализация системы $\Sigma$.
 \end{definition}
 
+Если рассматривать вместо отказов вершин отказы рёбер, то будет определение
+рёберной отказоустойчивости. Если рассматривать отказы элементов (вершин или
+рёбер), то будет комбинированная отказоустойчивость.
+
+Отказоустойчивость – это способность системы противостоять ошибке и продолжать
+работу в присутствии этой ошибки. Два уровня – полная отказоустойчивость и
+амортизация отказов.
+
 \begin{definition}
   Система $\Sigma^*$ называется оптимальной $k$-отказоустойчивой реализацией
   (вершинной) системы $\Sigma$, если выполняются следующие условия:
@@ -828,27 +865,13 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл�
 \begin{lemma}
   Если в графе $G$ минимальная из степеней вершин $d > 0$, то МВ-kР не содержит
   вершин степени меньше $d + k$.
+  \label{lem:mv-kr-less}
 \end{lemma}
-
-\begin{lemma}
-  Если в графе $G$ максимальная из степеней вершин есть $d$, и таких вершин
-  $m$, то МВ-kР содержит не менее, чем $(m + k)$ вершин степени не ниже $d$.
-\end{lemma}
-
-\begin{lemma}
-  Если в графе $G$ максимальная из степеней вершин есть $d$, то МВ-kР содержит
-  не менее, чем $kd$ дополнительных рёбер.
-\end{lemma}
-
-\begin{lemma}
-  \textbf{TODO:} ЧТО??
-
+\begin{proof}
   $G = (V, \alpha)$, $d > 0$ --- минимальная из степеней вершин.
 
   $G^* = (V^*, \alpha^*)$ и в $G^*$ $d(v) < d + k$.
-\end{lemma}
-
-\begin{lemma}
+  
   Рассмотрим граф, получающийся из $G^*$ удалением $k$ вершин, смежных с $v$.
   (Если $d(v) < k$, то удаление всех вершин, смежных с $v$, и $k - d(v)$
   произвольных вершин, отличных от $v$).
@@ -856,24 +879,27 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл�
   В получившемся графе степень вершины $v < d$. Очевидно, что $G$ нельзя будет
   вложить в получившийся граф, это противоречит предположению $\implies
   d(v) < d + k$.
-\end{lemma}
+\end{proof}
 
 \begin{lemma}
-  \textbf{TODO:} ЧТО?? №2
-
+  Если в графе $G$ максимальная из степеней вершин есть $d$, и таких вершин
+  $m$, то МВ-kР содержит не менее, чем $(m + k)$ вершин степени не ниже $d$.
+\end{lemma}
+\begin{proof}
   $G = (V, \alpha)$, $d > 0$ --- максимальная из степеней вершин.
 
   $G^* = (V^*, \alpha^*)$ и в $G^*$ менее чем $m + k$ вершин имеют степень $\geq
   d$.
-\end{lemma}
-
-\begin{lemma}
   Рассмотрим граф, получающийся из $G^*$ удалением $k$ вершин наибольшей степени.
   В получившемся графе меньше, чем $m$ вершин будут иметь степень не меньшую
   $d$. И, очевидно, что граф $G$ нельзя будет вложить в получившийся граф.
-\end{lemma}
+\end{proof}
 
 \begin{lemma}
+  Если в графе $G$ максимальная из степеней вершин есть $d$, то МВ-kР содержит
+  не менее, чем $kd$ дополнительных рёбер.
+\end{lemma}
+\begin{proof}
   $G = (V, \alpha)$, $d > 0$ --- максимальная из степеней вершин.
 
   В $G^*$ по крайней мере на $k$ вершин степени $\geq d$ больше, чем в графе
@@ -882,11 +908,11 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл�
   Рассмотрим граф, получающийся удалением $k$ вершин максимальной степени.
   Исходный граф по условию вкладывается в получившийся граф, а сам граф
   отличается от МВ-kР не менее, чем на $dk$ рёбер.
-\end{lemma}
+\end{proof}
 
 \begin{definition}
   Граф $G = (V, \alpha)$ называется $n$-вершинной цепью и обозначается $P_n$,
-  или его вершины $V = \set{v_1, \dots, v_n}$ могут быть занумерованы таким
+  если его вершины $V = \set{v_1, \dots, v_n}$ могут быть занумерованы таким
   способом, чтобы $\alpha$ имело вид:
   \begin{equation*}
     \alpha = \set{\set{v_i, v_{i + 1}}, i = \overline{1, n - 1}}
@@ -894,13 +920,13 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл�
 \end{definition}
 
 \begin{definition}
-  Вершины $u$ и $v$ называются подобными, если существует автоморфизм $\varphi :
-  \varphi(u) = v$.
-\end{definition}
-
-\begin{definition}
-  Граф, все вершины которого подобны, называется вершинно"=симметрическим
-  (вершинно"=транзитивным).
+  Граф $G = (V, \alpha)$ называется $n$-вершинным циклом и обозначается $C_n$,
+  если его вершины $V = \set{v_1, \dots, v_n}$ могут быть занумерованы таким
+  способом, чтобы $\alpha$ имело вид:
+  \begin{equation*}
+    \alpha = \set{\set{v_i, v_{i + 1}},
+    i = \overline{1, n - 1} \cup \set{v_1, v_n}}
+  \end{equation*}
 \end{definition}
 
 \begin{theorem}[О МВ-1В цепи, Хейз]
@@ -908,8 +934,8 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл�
   $C_{n + 1}$.
 \end{theorem}
 \begin{proof}
-  По лемме ??? для любого МВ-1Р цепи не может содержать вершин степени меньше
-  двух. Очевидно, что $C_{n + 1}$ является В-1Р цепи $P_n$.
+  По лемме \ref{lem:mv-kr-less} для любого МВ-1Р цепи не может содержать вершин
+  степени меньше двух. Очевидно, что $C_{n + 1}$ является В-1Р цепи $P_n$.
 
   С другой стороны, цикл $C_{n + 1}$ имеет все вершины степени 2, то есть имеет
   минимально возможное число рёбер $\implies C_{n + 1}$ --- МВ-1Р цепи $P_n$.
@@ -931,18 +957,91 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл�
   Цикл $C_{n + 1}$ является ТВ-1Р цепи $P_n$.
 \end{definition}
 
-\textbf{TODO:} Лекция 3, страница 67 --- Лекция 5
+\begin{theorem}[О МВ-1Р циклов, Хейз]
+  Графы, построенные по предлагаемым схемам, являются МВ-1Р циклов.
+
+  \begin{center}
+    \includegraphics[width=0.8\textwidth]{lec4-mv-1r-hayes}
+  \end{center}
+  \label{thm:cycles-mv-1r}
+\end{theorem}
+\begin{proof}
+  По лемме \ref{lem:mv-kr-less} любое МВ-1Р цикла не может содержать вершин
+  степени $< 3$.
+
+  С учётом теоремы Эйлера, число нечётных вершин должно быть чётно. Минимальное
+  вершинное 1-расширение цикла $C_n$ с чётным числом вершин не может иметь
+  все вершины степени 3 $\implies$ по крайней мере одна вершина должна иметь
+  степень $> 3$. Построенное расширение в точности удовлетворяет требованиям
+  минимальности.
+
+  Непосредственной проверкой убеждаемся, что графы, построенные по предлагаемой
+  схеме, являются В-1Р соответствующего цикла $\implies$ предлагаемые схемы
+  позволяют строить МВ-1Р.
+\end{proof}
+
+\begin{theorem}[МВ-1Р циклов, Абросимов]
+  Графы, построенные по предлагаемым схемам, являются МВ-1Р цикла с соответствующим
+  числом вершин и при $n > 5$ строят графы, не изоморфные соответствующим
+  реализациям из теоремы \ref{thm:cycles-mv-1r}.
+  
+  \begin{center}
+    \includegraphics[width=0.8\textwidth]{lec4-mv-1r-abrosimov}
+  \end{center}
+\end{theorem}
+\begin{proof}
+  \textbf{TODO}: Написать доказательство
+\end{proof}
+
 
 \section{Минимальные реберные расширения, основные свойства. Минимальные
 реберные 1-расширения цепей и циклов.}
 
-\dots
+\begin{theorem}[МР-1Р цепи, Харари, Хейз]
+  МР-1Р цепи $P_n$ при $n > 2$ является цикл $C_n$. Причём МР-1Р единственное
+  с точностью до изоморфизма.
+\end{theorem}
+\begin{proof}
+  \textbf{TODO}: Написать доказательство
+\end{proof}
+
+\begin{theorem}[О МР-1Р цикла, Харари, Хейз]
+  Графы, построенные по схемам из теоремы \ref{thm:cycles-mv-1r}, позволяют
+  строить МР-1Р соответствующих циклов.
+  \begin{center}
+    \includegraphics[width=0.8\textwidth]{lec4-mr-1r-harari}
+  \end{center}
+\end{theorem}
+
+\begin{theorem}[МР-1Р цикла, Абросимов]
+  Графы, построенные по предлагаемым схемам, являются МР-1Р цикла с
+  соответствующим числом вершин, и при $n > 6$ строят графы, не изоморфные
+  соответствующим реализациям из теоремы \ref{thm:cycles-mv-1r}.
+  \begin{center}
+    \includegraphics[width=0.8\textwidth]{lec4-mr-1r-abrosimov}
+  \end{center}
+\end{theorem}
 
 \section{Связь точных расширений и симметричности.}
 
-\dots
+\begin{theorem}
+  Только полные и вполне несвязные графы $K_n$ и $0_n$ имеют ТВ-kР при $\forall
+  k \in \mathbb{N} > 1$.
+\end{theorem}
+
+\begin{theorem}
+  При $k = 1$ граф является ТВ-kР $\iff$ он является вершинно"=симметрическим
+  графом (у него все вершины подобны).
+\end{theorem}
 
+\begin{theorem}
+  При $k = 1$ граф является ТР-kР $\iff$ он является рёберно"=симметрическим.
+\end{theorem}
 
+\begin{remark}
+  Для орграфов задача описания точных $k$-расширений пока не имеет полного
+  решения.
+\end{remark}
 
 \chapter{Основные типы неориентированных графов}
 
@@ -974,70 +1073,1661 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл�
   \label{def:chain}
 \end{definition}
 
+\begin{definition}
+  Длиной пути называется количество входящих в его состав рёбер.
+
+  Очевидно, что в $n$-вершинном графе цепь не может иметь длину больше, чем $n -
+  1$, а цикл не может иметь длину больше, чем $n$.
+  \label{def:path-length}
+\end{definition}
+
+\begin{definition}
+  Вершины $u$ и $v$ называются связанными в $G$, если существует путь, концами
+  которого они являются.
+
+  Очевидно, что если вершины $u$ и $v$ связанные, то это возможно лишь тогда,
+  когда существует соединяющая их цепь.
+  \label{def:connected-vert}
+\end{definition}
+
+\begin{definition}
+  Если вершины $u$ и $v$ связанные, то наименьшая из длин путей, соединяющих
+  $u$ и $v$, называется расстоянием между $u$ и $v$. Обозначается $d(u, v)$.
+
+  Для неориентированного графа $d(u, v) = d(v, u)$.
+\end{definition}
+
+\begin{definition}
+  Наибольшее из расстояний от вершины до всех оставшихся вершин называется
+  эксцентриситетом вершины. $E(u)$ --- эксцентриситет, $E(u) = \max d(u, v),
+  v \in V$.
+\end{definition}
+
+\begin{definition}
+  Минимальное из значений эксцентриситетов вершин графа называется его радиусом
+  $r(G) = \min E(u)$, максимальное --- диаметром $d(G) = \max E(u)$.
+\end{definition}
+
+\begin{definition}
+  Вершины, имеющие эксцентриситет, равный радиусу графа, называются
+  центральными.
+\end{definition}
+
+\begin{definition}
+  Множество центральных вершин называется центром графа.
+\end{definition}
+
+\begin{definition}
+  Вершины, эксцентриситет которых равен диаметру графа, называются окраинами или
+  периферийными, а множество таких вершин в графе называется окраиной или
+  периферией.
+\end{definition}
+
+\begin{definition}
+  Будем считать, что каждая вершина удалена от себя на расстояние 0 и связана
+  сама с собой.
+
+  Тогда отношение связности в графе $G$ будет отношением эквивалентности.
+\end{definition}
+
+\begin{definition}
+  Классы отношения связность графа называются его связными компонентами или
+  просто компонентами.
+\end{definition}
+
+\begin{definition}
+  Граф с универсальным отношением связности называется связным графом. Граф
+  с тождественным отношением связности называется вполне несвязным.
+\end{definition}
+
 \section{Теорема о связности двух нечетных вершин. Достаточное условие
 связности.}
 
-\dots
+\begin{theorem}
+  Если вершины $u$ и $v$ являются единственными нечётными вершинами графа $G$,
+  то они связаны в этом графе.
+\end{theorem}
+\begin{proof}
+  Предположим, противное, то есть $u$ и $v$ не связаны в графе $G = (V, \alpha)$.
+  Обозначим через $G_1$ и $G_2$ компоненты связности графа $G$, содержащие
+  соответственно вершины $u$ и $v$.
+
+  В графе $G_1$ вершина $u$ является единственной нечётной вершиной, что
+  противоречит теореме Эйлера (количество нечётных вершин должно быть чётно).
+\end{proof}
+
+\begin{theorem}[Достаточное условие связности]
+  Если граф $G = (V, \alpha)$ с $n$ и $m$ рёбрами такой, что для него
+  выполняется условие $m > C_{n - 1}^2 = \frac{(n - 1)(n - 2)}{2}$, то $G$ ---
+  связный.
+\end{theorem}
+\begin{proof}
+  От противного. Предположим, что в графе $G$ выполняется неравенство $m > C_{n
+  - 1}^2 = \frac{(n - 1)(n - 2)}{2}$ и он не является связным.
+
+  Тогда граф $G$ имеет по крайней мере две компоненты. Пусть $G_1$ --- некоторая
+  компонента связности графа $G$ и пусть она содержит $k$ вершин.
+
+  Рассмотрим два случая:
+  \begin{enumerate}
+    \item
+      $2 \leq k \leq n - 2$. В $G_2$ $(n - k)$ вершин. Каждое ребро графа $G$
+      входит или в состав $G_1$, или в состав $G_2$. Если предположить, что
+      $G_1$ и $G_2$ --- полные графы, то число рёбер в них будет $C_k^2$ и
+      $C_{n - k}^2$, $m \leq C_k^2 + C_{n - k}^2$.
+      \begin{align*}
+        C_k^2 + C_{n - k}^2 &= \frac{k(k - 1)}{2} + \frac{(n - k)(n - k - 1)}{2} = \\
+                            &= \frac{k^2 - k + n^2 - nk - n - nk + k^2 + k}{2} =  \\
+                            &= \frac{n^2 - (2k + 1)n + 2k^2}{2}
+      \end{align*}
+
+      Из условия теоремы: $m > C_{n - 1}^2 = \frac{(n - 1)(n - 2)}{2}$.
+
+      \begin{align*}
+        C_{n - 1}^2 - m &\geq C_{n - 1}^2 - (C_k^2 + C_{n - k}^2) = \\
+                        &= \frac{(n - 1)(n - 2)}{2} - \frac{n^2 - (2k + 1)n + 2k^2}{2} = \\
+                        &= kn - n - k^2 + 1 = (k - 1)n - (k^2 - 1) = \\
+                        &= (k - 1)(n - (k + 1)) > 0
+      \end{align*}
+
+      Получаем $C_{n - 1}^2 \geq m$. Противоречие.
+    \item
+      Пусть $G_1$ содержит только одну вершину, $k = 1$. Тогда в $G_2$ входит
+      $n - 1$ вершина. $m \leq C_{n - 1}^2$ --- противоречие.
+
+      Аналогично при $k = n - 1$.
+  \end{enumerate}
+\end{proof}
 
 \section{Точки сочленения, мосты.}
 
-\dots
+\begin{definition}
+  Вершина, удаление которой приводит к увеличению числа компонент связности,
+  называется точкой сочленения. А ребро с таким свойством называется мостом.
+\end{definition}
 
 \section{Деревья. Лист и корень. Характеристическая теорема о деревьях. Теорема
 о центре дерева.}
 
-\dots
+\begin{definition}
+  Дерево --- связный граф без циклов.
+
+  При $n = 1$ получается тривиальное дерево. При $n = 4$ получается $P_4$ и
+  $K_{1, 3}$. При $n = 5$ получается $P_5, K_{1, 4}$ и ещё одно дерево.
+\end{definition}
+
+\begin{definition}
+  Вершина дерева, имеющая степень 1, называется висячей вершиной или листом.
+\end{definition}
+
+Дерево может иметь выделенную вершину --- корень. Дерево с корнем называется
+корневым, а без корня --- свободным.
+
+\begin{theorem}[О характеризации деревьев, Кэли]
+  Граф с $n$ вершинами и $m$ рёбрами $\iff$ является деревом, когда выполняется
+  одно из следующих условий:
+  \begin{enumerate}
+    \item Любые две вершины графа соединены единственной цепью;
+    \item Граф связный и $n = m + 1$;
+    \item Граф ациклический и $n = m + 1$.
+  \end{enumerate}
+\end{theorem}
+\begin{proof}
+  \textbf{Необходимость.}
+
+  Пусть граф $G$ имеет $n$ вершин, $m$ рёбер и является деревом. Покажем, что
+  условия 1--3 выполняются.
+
+  Пусть $u$ и $v$ --- две вершины $G$, между которыми существует по крайней
+  мере две различные цепи. Очевидно, что в $G$ можно выделить цикл.
+
+  Докажем, что $n = m + 1$. Рассмотрим деревья при $n = 1, 2$.
+  \begin{align*}
+    n = 1 &\implies m = 0 \\
+    n = 2 &\implies m = 1
+  \end{align*}
+
+  Пусть это справедливо для деревьев с числом вершин меньше, чем $n$.
+
+  Рассмотрим $T_{n + 1}$. Пусть $u$ и $v$ --- две смежные вершины в этом
+  дереве. Удалим из $T$ ребро $\set{u, v}$. В силу первого пункта, $\set{u, v}$
+  --- мост, и после его удаления дерево $T$ распадётся на две компоненты
+  (два дерева).
+
+  В одном из них $k$ вершин, во втором --- $(n + 1) - k$ вершин.
+  \begin{align*}
+    &G_1 : n_1 = k = m_1 + 1 \\
+    &G_2 : n_2 = (n + 1) - k = m_2 + 1 \\
+    &\implies n_1 + n_2 = n + 1 = (m_1 + 1 + m_2) + 1 \\
+    &\implies n + 1 = m + 1
+  \end{align*}
+
+  \textbf{Достаточность.}
+
+  \begin{enumerate}
+    \item
+      Пусть в графе $G$ между любыми двумя вершинами существует единственная
+      цепь. Предположим, что в нём есть цикл, содержащий вершины $u$ и $v$.
+      Тогда между вершинами $u$ и $v$ будет две цепи $\implies$ противоречие
+      $\implies$ $G$ --- связный и не содержит циклов, то есть --- это дерево.
+    \item
+      $G$ --- связный и $n = m + 1$. Покажем, что в $G$ нет циклов.
+
+      Предположим, что это не так. Удалим из $G$ одну висячую вершину вместе с
+      её ребром. Получим граф $G_1 : 1 = n - m = n_1 - m_1$. Продолжаем
+      процесс с графом $G_1$ пока будут оставаться висячие вершины.
+      \begin{equation*}
+        1 = n - m = n_1 - m_1 = \dots = n_k - m_k
+      \end{equation*}
+
+      По теореме Эйлера $\ds\sum_{v_i \in G_k} d(v_i) = 2m_k$.
+
+      $d(v_i) \geq 2 \implies 2n_k \leq \sum_{i = 1}^{n_k} d(v_i) = 2m_k$.
+
+      Получаем $n_k \leq m_k$ --- противоречие.
+    \item
+      Пусть $G$ --- ациклический и $n = m + 1$. Допустим, что $G$ связный.
+
+      Пусть это не так. $G = G_1 \cup G_2 \cup \dots \cup G_k,\, k \geq 2$.
+      Так как $G$ ациклический, то любая его компонента ациклический граф.
+      Причём он является связным, то есть деревом. Для любой компоненты выполняется
+      $n_i = m_i + 1,\, i = 1, \dots, k$.
+
+      Тогда имеет место следующее:
+      \begin{equation*}
+        n = \sum_{i = 1}^k n_i = \sum_{i = 1}^k (m_i + 1) = \sum_{i = 1}^k
+        m_i + k = m + k
+      \end{equation*}
+
+      Так как $k \geq 2$, получаем противоречие.
+  \end{enumerate}
+\end{proof}
+
+\begin{theorem}[О центре дерева, Жордан]
+  Центр дерева состоит либо из одной вершины, либо из двух смежных вершин.
+\end{theorem}
+\begin{proof}
+  Рассмотрим маленькие деревья. $T_1$ --- центр состоит из одной вершины.
+  $T_2$ --- центр состоит из двух смежных вершин.
+
+  ММИ. Пусть справедливо для $T_n$. Рассмотрим $T_{n + 1}$.
+
+  Удалим в дереве $T_{n + 1}$ все листья. Очевидно, что для любой вершины
+  дерева эксцентриситет достигается на висячих вершинах. Удаление всех листьев
+  приведёт к уменьшению эксцентриситета оставшихся вершин на 1. Следовательно,
+  в дереве $T_{n + 1}$ и в получившемся после удаления листьев дереве центры
+  будут состоять из одних и тех же вершин. Получившееся дерево будет иметь не
+  более $n$ вершин. Для него выполняется предположение.
+
+  Следовательно, верно и для $T_{n + 1}$.
+\end{proof}
+
+\begin{definition}
+  Дерево с одной центральной вершиной называется центральным. С двумя ---
+  бицентральным.
+\end{definition}
 
 \section{Изоморфизм деревьев: алгоритм Эдмондса, алгоритм WAV. Кодирование
 деревьев.}
 
-\dots
+\begin{itemize}
+  \item Алгоритм проверяет изоморфизм деревьев,
+  \item Все вершины дерева получают метки,
+  \item Если метки корней совпадут, деревья являются изоморфными.
+\end{itemize}
+
+Два корневых дерева будут изоморфны только если количество уровней и число
+вершин на этих уровнях будет одинаковым.
+
+Алгоритм:
+\begin{enumerate}
+  \item
+    Каждой вершине будем приписывать метки следующим образом: листовые вершины
+    --- метка 0. Для остальных вершин расставление меток будет начинаться с
+    последнего уровня (от листьев);
+  \item
+    На текущем уровне каждая вершина получает метку, являющуюся списком вершин
+    --- её потомков, то есть вершин, смежных с ней и расположенных уровнем ниже
+    (или выше, в зависимости от нумерации уровней). Кроме этого к метке
+    добавляется длина наибольшей цепи от вершины до достижимых из неё листьев
+    по пути сверху вниз;
+  \item
+    Получившиеся кортежи сравниваются с соответствующими кортежами второго
+    дерева. Полученные кортежи на уровне упорядочиваются лексикографически и
+    нумеруются. Если соответствие установить нельзя, то деревья неизоморфны.
+  \item
+    Если соответствие удалось установить, то вершина получает новую метку,
+    равную номеру её кортежа, и переходим дальше на шаг 2.
+\end{enumerate}
+
+Для использования алгоритма Эдмондса для проверки изоморфизма двух свободных
+деревьев необходимо выполнить этот алгоритм один раз, если деревья являются
+центральными, и два раза, если деревья являются бицентральными.
+
+При этом в качестве корня первого дерева выбирается любая из центральных вершин,
+и алгоритм дважды применяется ко второму дереву, у которого в качестве корня
+выбирается каждая из центральных вершин.
+
+Если хотя бы в одном из двух случаев получили совпадение всех кортежей, то
+деревья изоморфны.
+
+Другой подход --- между двумя центральными вершинами добавляется вершина, и
+алгоритм выполняется для такого дерева.
+
+\textbf{TODO:} другие кодировки.
+
+\textbf{Алгоритм WAV (Walk-around valency code)}. Данный алгоритм позволяет
+построить канонический код свободного дерева. На каждом шаге алгоритма есть
+множество $A$ помеченных вершин и множество $B$ вершин без меток. Метки ---
+строки из чисел.
+
+\begin{enumerate} \setcounter{enumi}{-1}
+  \item Множество $A$ состоит из листьев дерева, каждый лист имеет метку 0;
+  \item
+    Составим множество $R$ таких вершин из $B$ (то есть вершин без меток),
+    которые смежны максимум с одной другой вершиной из $B$.
+  \item
+    Для каждой вершины $x \in R$ составляем метку и меток смежных вершин,
+    которые уже принадлежат $A$. Записываем эти метки в лексикографическом
+    порядке и в качестве префикса добавляем количество этих меток (то есть
+    количество смежных вершин из $A$).
+  \item
+    \begin{enumerate}
+      \item
+        Если в $B$ остаётся только одна вершина $x$, то её метка --- код
+        дерева, а алгоритм завершён,
+      \item
+        Если в $B$ ровно два элемента, определим, какая из меток идет первой в
+        лексикографическом порядке. Вставляем эту метку после первого элемента
+        другой метки. Затем увеличиваем на 1 первый элемент получившейся
+        последовательности. В этом случае получается, что мы выбираем одну из
+        центральных вершин нашего бицентрального дерева в качестве корня. И эта
+        метка --- код дерева.
+      \item
+        Иначе мы перемещаем вершины, входящие на этом шаге в $R$, из множества
+        $B$ в $A$. Переходим на шаг 1.
+    \end{enumerate}
+\end{enumerate}
 
 \section{Уровневые коды. Канонические коды. Код Прюфера.}
 
-\dots
+\begin{definition}
+  Канонический код графа --- выбранный по определённым правилам один из кодов
+  изоморфных графов. Уникальная строка, которая не зависит от порядка
+  нумерации вершин.
+\end{definition}
+
+У изоморфных графов одинаковые канонические коды, у неизоморфных --- разные.
+
+\begin{definition}
+  Каноническая нумерация --- это нумерация (перестановка) вершин графа,
+  гарантирующая, что изоморфные графы будут пронумерованы одинаково.
+\end{definition}
+
+\textbf{TODO}: другие коды.
 
 \section{Сеть. Остовное (покрывающее) дерево. Алгоритмы Прима и Краскала.}
 
-\dots
+\begin{definition}
+  Сеть --- связный граф, в котором каждому ребру приписано некоторое число.
+  Это число называется весом, длиной, стоимостью и т.д. в зависимости от
+  способа интерпретации. Обозначается $w(u, v)$. В неориентированном графе
+  $w(u, v) = w(v, u)$.
+\end{definition}
+
+\begin{definition}
+  Граф $G^* = (V^*, \alpha^*)$ называется покрывающим деревом или остовным
+  деревом для связного графа $G = (V, \alpha)$, если $G^*$ --- дерево,
+  $V^* = V,\, \alpha^* \subseteq \alpha$.
+\end{definition}
+
+\begin{definition}
+  Вес остовного дерева --- сумма весов всех рёбер сети, входящих в состав этого
+  дерева.
+\end{definition}
+
+\begin{definition}
+  Покрывающее дерево называется минимальным, если его вес наименьший среди
+  весов всех покрывающих деревьев данной сети.
+\end{definition}
+
+Для поиска минимального остовного дерева хорошо применимы <<жадные алгоритмы>>.
+Их суть состоит в следующем: на очередном шаге выбирается <<безопасное>>
+ребро наименьшего веса (то есть локально-оптимальное решение).
+
+\begin{definition}[Алгоритм Краскала]
+  Минимальное остовное дерево строится следующим образом:
+  \begin{enumerate}
+    \item Все рёбра сети упорядочены в порядке возрастания весов;
+    \item
+      Первое по списку ребро окрашивается в некоторый цвет, а его концы
+      помечаются как принадлежащие одной компоненте (приписывается одинаковая
+      метка);
+    \item
+      Выберем следующее по списку ребро. Возможны следующие случаи:
+      \begin{enumerate}
+        \item
+          Ребро соединяет две вершины, принадлежащие одной компоненте, ребро
+          пропускается;
+        \item
+          Одна из вершин ребра уже имеет метку, а вторая --- нет. Ребро
+          окрашивается, вторая вершина получает ту же метку, что и первая;
+        \item
+          Концы ребра имеют различные метки (то есть принадлежать различным
+          компонентам). Ребро окрашивается, две компоненты объединяются в одну;
+        \item
+          Концы ребра не имеют меток, то есть ещё не попали ни в какую
+          компоненту. Ребро окрашивается, а его концы образуют новую компоненту
+          с новой меткой.
+      \end{enumerate}
+    \item
+      Если все рёбра просмотрены, то алгоритм завершён, и окрашенные рёбра
+      образуют МОД, иначе --- переход к шагу 3.
+  \end{enumerate}
+\end{definition}
+
+\begin{theorem}
+  Описанный алгоритм приводит к построению минимального остовного дерева.
+\end{theorem}
+
+\begin{remark}
+  В алгоритме основная вычислительная сложность заключена на этапе 1, где
+  осуществляется сортировка рёбер $O(m \log m)$. На этапе 3 последовательно
+  просматриваются все рёбра $O(m)$. В общем случае сложность $O(m \log m)$.
+
+  Если веса --- натуральные числа, не превышающие $k$, то для сортировки можно
+  использовать математическую сортировку или сортировку подсчётом $O(m + k)$.
+\end{remark}
+
+\begin{definition}[Алгоритм Прима]
+  Выбор безопасных рёбер (этап 3) отличается от алгоритма Краскала тем, что
+  безопасным считается ребро только из пункта б).
+
+  В алгоритме Прима построение остовного дерева выглядит как увеличивающаяся
+  единственная компонента, а в алгоритме Краскала несколько компонент сливаются
+  в одну.
+\end{definition}
 
 \section{Укладки графов. Укладки на сфере и в пространстве. Планарные графы.
 Планарность деревьев.}
 
-\dots
+\begin{definition}
+  Укладкой графа в пространстве $L$ называется изображение графа, при котором
+  вершинам графа соответствуют точки пространства, рёбрам --- жордановые
+  кривые, при этом рёбра могут пересекаться только, быть может в вершинах.
+\end{definition}
+
+\begin{definition}
+  Укладка графа в пространстве $L = R^2$ (на плоскости) называется плоским
+  изображением графа.
+\end{definition}
+
+\begin{definition}
+  Граф, допускающий укладку на плоскости, называется планарным.
+\end{definition}
+
+\begin{theorem}
+  Всякий граф допускает укладку в $R^3$.
+\end{theorem}
+\begin{proof}
+  Построим в пространстве $R^3$ прямую $l$. Выберем на ней $n$ различных
+  точек по числу вершин заданного графа. Проведём через $l$ $m$ различных
+  плоскостей по числу рёбер. Каждое ребро графа изобразим в виде полуокружности,
+  соединяющей соответствующие точки на прямой $l$ и лежащей в собственной
+  плоскости.
+
+  Очевидно, что рёбра могут пересекаться только в точках, расположенных на
+  прямой $l$, то есть в вершинах графа.
+\end{proof}
+
+\begin{definition}
+  Граф допускает укладку на сфере $\iff$ он планарный (то есть допускает
+  укладку на плоскости).
+\end{definition}
+\begin{proof}
+  Установим проективное отношение для изображений на сфере и на плоскости.
+  \begin{enumerate}
+    \item
+      Плоскость $\to$ сфера.
+
+      Пусть граф изображён в плоскости $\alpha$. Разместим сферу, на которой
+      требуется изобразить граф так, чтобы она касалась $\alpha$ в точке $S$.
+
+      Обозначим диаметрально противоположную для $S$ точку через $N$. Каждой
+      точке $A$ на плоскости $\alpha$ сопоставим точку $A'$ на сфере, которая
+      является пересечением прямой $NA$ со сферой.
+
+      В силу взаимно однозначного соответствия, если исходный граф допускает
+      укладку на плоскости, то он будет допускать укладку на сфере.
+
+    \item
+      Сфера $\to$ плоскость.
+
+      Проекция графа со сферы на плоскость определяется обратным
+      преобразованием.
+
+      То есть каждой точке $A'$ сферы будет соответствовать точка $A$ плоскости
+      $\alpha$, которая является пересечением прямой $NA'$ с плоскостью
+      $\alpha$.
+  \end{enumerate}
+\end{proof}
+
+\begin{theorem}[О планарности деревьев]
+  Всякое дерево является планарным графом.
+\end{theorem}
+\begin{proof}
+  Пусть $T = (V, \alpha)$ --- некоторое дерево. $v_0 \in V$ --- произвольная
+  вершина --- корень. Изобразим дерево поуровнево. Первый уровень --- корневая
+  вершина. Второй --- вершины, смежные с корневой.
+
+  На $i$-ом уровне расположены вершины, которые удалены от корневой на
+  расстояние $i - 1$ (это будут вершины, смежные с вершинами $i - 1$ уровня и не
+  уложенные ранее). Вершины $i$-го уровня укладываются слева направо в порядке
+  следования смежных с ними вершин $i - 1$ уровня и так далее.
+
+  Очевидно, что получим плоское изображение данного дерева.
+\end{proof}
+
+\begin{definition}
+  Радиальная поуровневая укладка дерева --- поуровневая укладка дерева, когда
+  уровни имеют вид концентрических окружностей.
+\end{definition}
 
 \section{Грань. Теорема Эйлера и её обобщения. Триангуляция, максимально плоский
 граф. Следствия из теоремы: если всякая грань k-элементный цикл, число ребер в
 триангуляции, необходимое условие планарности, степень вершины в триангуляции.}
 
-\dots
+Пусть дан граф $G = (V, \alpha)$ в плоском изображении.
+
+\begin{definition}
+  Гранью графа $G$ в плоском изображении называется область плоскости,
+  ограниченная рёбрами графа. Одной из граней является внешняя грань,
+  представляющая собой бесконечную по протяжённости часть плоскости.
+
+  Количество граней в плоском изображении обозначается $r$ (иногда $f$).
+\end{definition}
+
+\begin{theorem}[Формула Эйлера]
+  В плоском изображении связного планарного графа справедливо $n - m + r = 2$,
+  где $n, m, r$ соответственно число вершин, рёбер и граней графа.
+\end{theorem}
+\begin{proof}
+  Пусть дан граф $G = (V, \alpha)$ в плоском изображении. Предположим, что
+  $G$ --- дерево. У дерева $r = 1,\, m = n - 1$. Проверяем:
+  \begin{align*}
+    n - n + 1 + 1 &= 2 \\
+    2 &= 2
+  \end{align*}
+
+  Пусть граф $G$ является связным, но не является деревом. Следовательно, в нём
+  есть хотя бы один цикл. Удалим из любого цикла графа $G$ некоторое ребро.
+
+  Полученный граф обозначим $G_1$. Очевидно, что $G_1$ связный и является
+  плоским. При этом $n_1 = n,\, m_1 = m - 1,\, r_1 = r - 1$. Таким образом, $n_1
+  - m_1 + r_1 = n - m + 1 + r - 1 = n - m + r$.
+
+  Продолжим рассуждения с графом $G_1$, если он содержит цикл. Пусть в
+  результате были получены графы $G_1, G_2, \dots, G_k$, где $G_k$ --- последний
+  граф, полученный по рассматриваемой процедуре, и он не содержит циклов.
+  Следовательно, $G_k$ --- дерево. При этом $n_1 - m_1 + r_1 = n_k - m_k + r_k =
+  n - m + r = 2$.
+\end{proof}
+
+\begin{remark}
+  Для несвязного графа $n - m + r = k + 1$, где $k$ --- количество компонент
+  связности.
+\end{remark}
+
+\begin{corollary}
+  Если в каждом плоском изображении графа всякая грань является $k$-элементным
+  циклом, то $\ds m = \frac{k(n - 2)}{k - 2}$.
+\end{corollary}
+\begin{proof}
+  Каждая грань --- $k$-угольник, количество граней равно $r$. Каждое ребро
+  будет учитываться дважды, как граница двух граней: $rk = 2m$. Отсюда $\ds r =
+  \frac{2m}{k}$. По формуле Эйлера: $2 = n - m + r = n - m + \ds\frac{2m}{k}$.
+  $2k = nk - mk + 2m$, отсюда $m = \ds\frac{k(n - 2)}{k - 2}$.
+\end{proof}
+
+\begin{definition}
+  Плоский граф (конкретное изображение планарного графа на плоскости) называется
+  триангуляцией, если все его грани являются треугольниками.
+\end{definition}
+
+\begin{definition}
+  Граф называется максимально плоским, если к нему нельзя добавить рёбра так,
+  чтобы получившийся граф снова был плоским.
+
+  Очевидно, что граф является плоским $\iff$ он представляет собой триангуляцию.
+\end{definition}
+
+\begin{corollary}
+  Во всякой триангуляции $m = 3n - 6$.
+\end{corollary}
+\begin{proof}
+  В любой триангуляции $3r = 2m$, то есть $r = \frac{2}{3}m$.
+
+  По формуле Эйлера: $2 = n - m + r = n - m + \frac{2}{3}m = n - \frac{1}{3}m$,
+  $6 = 3n - m$.
+\end{proof}
+
+\begin{corollary}[Необходимое условие планарности]
+  Во всяком планарном графе $m \leq 3n - 6$.
+\end{corollary}
+\begin{proof}
+  Пусть граф $G$ --- планарный, и задано его плоское изображение.
+
+  Если одна из его граней не является треугольником, то проведя нужное
+  количество диагоналей, можно получить триангуляцию. В полученной
+  триангуляции выполняется $m = 3n - 6$.
+\end{proof}
+
+\begin{corollary}
+  Во всякой триангуляции существует вершина, степень которой $\leq 5$.
+\end{corollary}
+\begin{proof}
+  В любой триангуляции $m = 3n - 6 \implies 6 = 3n - m$.
+  \begin{align*}
+    6 &= 3n - \frac{1}{2} \sum_{i = 1}^n d(v_i) \\
+    12 &= 6n - \sum_{i = 1}^n d(v_i) = \sum_{i = 1}^n (6 - d(v_i)) \\
+    \sum_{i = 1}^n (6 - d(v_i)) &= 12 > 0
+  \end{align*}
+
+  Существует $i$, что слагаемое $(6 - d(v_i)) > 0$. Отсюда $d(v_i) \leq 5$.
+\end{proof}
 
 \section{Графы типа 1 и типа 2. Стягивание ребра, минор. Критерии планарности
 (Понтрягин-Куратовский, Вагнер). Прямолинейное изображение. Род поверхности, род
 графа, число скрещиваний.}
 
-\dots
+\begin{definition}
+  Назовём подразбиением ребра $\set{u, v}$ граф, который получается из исходного
+  графа удалением ребра $\set{u, v}$, добавлением вершины $w$ и двух рёбер
+  $\set{u, w}$ и $\set{w, v}$.
+\end{definition}
+
+\begin{definition}
+  Говорят, что $G_1$ и $G_2$ гомеоморфны, если они могут быть получены из
+  некоторого графа $G$ c помощью соответствующей последовательности
+  подразбиения рёбер.
+\end{definition}
+
+\begin{definition}
+  Графом типа 1 называются граф, гомеоморфные графу $K_5$.
+\end{definition}
+
+\begin{definition}
+  Графы типа 2 --- графы, гомеоморфные $K_{3,3}$.
+\end{definition}
+
+\begin{theorem}[Критерий планарности графов, Понтрягин-Куратовский]
+  Граф является планарным $\iff$ среди его частей нет графов типа 1 и 2.
+\end{theorem}
+\begin{proof}
+  \textbf{Необходимость.}
+
+  Достаточно доказать, что $K_5$ и $K_{3,3}$ не планарны. Так как очевидно, что
+  подразбиение рёбер не изменяет планарности графа.
+  \begin{enumerate}
+    \item
+      $K_5$. $n = 5,\, m = C_5^2 = 10$. По следствию 3, если бы $K_5$ был
+      планарным, то должно было бы выполняться $m \leq 3n - 6$.
+      \begin{align*}
+        10 &\leq 15 - 6 \\
+        10 &\leq 9
+      \end{align*}
+
+      Получили противоречие.
+
+    \item
+      $K_{3,3}$. $n = 6,\, m = 9$. Если бы граф был планарен, то в его плоском
+      изображении имела бы место формула Эйлера. И тогда $r = 5$. Заметим, что
+      в $K_{3,3}$ отсутствуют трёхэлементные циклы. Следовательно, в плоском
+      изображении каждая грань содержала бы как минимум 4 ребра. Тогда $r =
+      \frac{2m}{k}$. Отсюда $\frac{4 \cdot 5}{2} \leq m \implies 10 \leq 9$.
+
+      Получили противоречие.
+  \end{enumerate}
+\end{proof}
+
+\begin{definition}
+  Стягивание ребра --- это операция, которая удаляет ребро из графа, а до
+  этого связанные ребром вершины сливаются в одну вершину.
+\end{definition}
+
+\begin{definition}
+  Граф $H$ называется минором графа $G$, если $H$ можно получить из $G$
+  удалением и/или стягиванием рёбер графа $G$. Граф $G$ называется стягиваемым к
+  графу $H$.
+\end{definition}
+
+\begin{theorem}[Критерий планарности, Вагнер]
+  Граф является планарным $\iff$ графы $K_5$ и $K_{3,3}$ не являются его
+  минорами.
+\end{theorem}
+
+\begin{definition}
+  Прямолинейным изображением графа называется такое изображение, в котором все
+  рёбра являются отрезками прямых.
+\end{definition}
+
+\begin{theorem}[О прямолинейном изображении планарных графов, Фари]
+  Всякий планарный граф допускает плоское прямолинейное изображение.
+\end{theorem}
+
+\begin{definition}
+  Граф, который нельзя уложить на плоскости, но можно уложить на торе,
+  называются тороидальными.
+\end{definition}
+
+\begin{definition}
+  Род поверхности --- это максимальное число простых замкнутых кривых, не
+  разделяющих эту поверхность. Обозначим через $g$.
+\end{definition}
+
+У тора род поверхности равен 1. Это сфера с одной <<ручкой>> или плоскость с
+одним мостом. Род поверхности равен количеству <<ручек>>.
+
+\begin{definition}
+  Род графа --- минимальный род поверхности, на которой можно уложить этот граф.
+  Обозначается $g(G)$. Формула Эйлера с родом: $n - m + r = 2 - 2g$.
+  \begin{align*}
+    g(K_n) &= \left\lceil \frac{(n - 3)(n - 4)}{12} \right\rceil \\
+    g(K_{n,n}) &= \left\lceil \frac{(n - 2)^2}{4} \right\rceil
+  \end{align*}
+\end{definition}
+
+\begin{definition}
+  Число скрещиваний $cr(G)$ графа $G$ --- наименьшее число пересечений, получаемых
+  при изображении графа на плоскости.
+
+  Очевидно, $cr(G) = 0 \iff$ граф планарный.
+\end{definition}
 
 \section{Эйлеровы графы. Критерий эйлеровости графа. Критерий существования
 эйлерова пути.}
 
-\dots
+Рассмотрим неориентированный граф $G = (V, \alpha)$ с $n$ вершинами и $m$
+рёбрами. Максимальная длина пути в таком графе есть $m$, максимальная длина
+простого пути --- $n$.
+
+\begin{definition}
+  Путь длины $m$ (то есть состоящий из всех рёбер графа) называется эйлеровым
+  путём.
+\end{definition}
+
+\begin{definition}
+  Циклический эйлеров путь называется эйлеровым циклом (эйлеров цикл в общем
+  случае не является циклом, так как может не являться простым путём).
+\end{definition}
+
+\begin{definition}
+  Граф, содержащий эйлеров цикл, называется эйлеровым.
+\end{definition}
+
+\begin{definition}
+  Граф, содержащий эйлеров путь, но не содержащий эйлеров цикл, называется
+  полуэйлеровым.
+\end{definition}
+
+\begin{itemize}
+  \item Число нечётных вершин графа должно быть чётно;
+  \item
+    Если все вершины графа чётные, то можно начертить этот граф без отрыва
+    карандаша от бумаги;
+  \item
+    Если ровно две вершины графа нечётные, то можно начертить этот граф без
+    отрыва карандаша от бумаги, при этом нужно начинать с одной из нечётных
+    вершин и завершить его в другой нечётной вершине;
+  \item
+    Граф с более чем двумя нечётными вершинами невозможно начертить одним
+    росчерком.
+\end{itemize}
+
+\begin{definition}
+  Плоская замкнутая кривая называется уникурсальное, если она может быть
+  нарисована, не отрывая перо от бумаги и никакой её участок не проходится
+  более одного раза.
+
+  Очевидно, что кривая будет уникурсальной $\iff$ она является контуром эйлерова
+  графа.
+\end{definition}
+
+\begin{theorem}[Критерий эйлеровости графа]
+  Связный граф является эйлеровым $\iff$ все его вершины чётные.
+  \label{thm:euler-crit}
+\end{theorem}
+\begin{proof}
+  \textbf{Необходимость.}
+
+  $G = (V, \alpha)$ --- эйлеров граф. Пусть в нём существует эйлеров путь $C$.
+  Пусть $u$ --- начальная и конечная вершина $C$. Отправимся из $u$ по $C$.
+  Пусть $v$ --- некоторая промежуточная вершина по пути $C$.
+
+  Путь $C$ может закончиться только вершиной $u$, следовательно, заходя в $v$ по
+  ребру пути $C$, мы можем выйти из неё по ещё не пройденному пути $C$. Таким
+  образом, в каждой промежуточной вершине $v$ все рёбра разбиваются на пары
+  вход-выход по отношению к пути $C$.
+
+  Вершина $u$ может просматриваться по $C$ много раз. Рёбра, которым она
+  принадлежит, тоже могут быть сгруппированы парами вход-выход, за исключением
+  первого и последнего ребра пути $C$, которое также составляет пару.
+
+  Таким образом, каждая вершина графа $G$ принадлежит чётному числу рёбер,
+  следовательно, является чётной.
+
+  \textbf{Достаточность.}
+
+  $G = (V, \alpha)$ --- связный граф и все вершины чётные. Покажем, что в $G$
+  существует циклический эйлеров путь.
+
+  Выберем произвольную вершину $u$ графа $G$. Отправимся из неё, двигаясь
+  по рёбрам графа. Каждое пройденное ребро будем окрашивать. Так как все
+  вершины чётные, то любая вершина графа $G$ принадлежит чётному числу рёбер.
+  Следовательно, войдя в некоторую вершину $v$, мы имеем возможность выйти из
+  неё по ещё не окрашенному ребру.
+
+  Очевидно, что путь может окончиться только в вершине $u$, когда последнее
+  ребро составит пару первому. Обозначим получившийся путь $C_1$. Если $C_1$
+  содержит все рёбра графа, то он является эйлеровым, и мы закончили построение.
+
+  Предположим, что не все рёбра графа оказались окрашенными. В силу связности
+  графа, не нарушая общности, можно считать, что одно из неокрашенных рёбер
+  имеет своим концом вершину $v$, входящую в $C_1$.
+
+  Продолжаем построение циклического пути из вершины $v$ по неокрашенным рёбрам.
+  Повторяя рассуждения, путь закончится в $v$, обозначим его $C_2$.
+
+  Рассмотрим в графе $G$ новый циклический путь $u C_1 v C_1 u$. Очевидно, что
+  построенный путь является циклическим и содержит все рёбра, включающиеся в
+  $C_1$ и $C_2$. Кроме того, построенный путь содержит, по крайней мере, на 3
+  ребра больше, чем $C_1$.
+
+  Если все рёбра оказались окрашенными, то построение завершено.
+
+  Иначе продолжаем процедуру, которая в силу конечности графа, завершится
+  построением циклического эйлерова пути.
+\end{proof}
+
+\begin{theorem}[Критерий существования эйлерова пути между различными вершинами]
+  Для того, чтобы в связном графе $G$ существует эйлеров путь, соединяющий две
+  различные вершины $u$ и $v$, необходимо и достаточно, чтобы $u$ и $v$ были
+  единственными нечётными вершинами графа $G$.
+\end{theorem}
+\begin{proof}
+  \textbf{Необходимость.}
+
+  Пусть в $G$ существует эйлеров путь, соединяющий две различные вершины $u$ и
+  $v$. Отправимся из $u$ в $v$ по этому пути. Все рёбра в промежуточных вершинах
+  разобьются на пары вход-выход. Без пары останутся только первое и последнее
+  ребро пути.
+
+  \textbf{Достаточность.}
+
+  Пусть $u$ и $v$ --- единственные нечётные вершины в связном графе $G$.
+  Рассмотрим два случая:
+  \begin{enumerate}
+    \item
+      $\set{u, v} \in \alpha$, то есть смежны. Удалим ребро $\set{u, v}$ из $G$,
+      то, что осталось обозначим $G_1$.
+      \begin{enumerate}
+        \item
+          $G_1$ --- связный. В $G_1$ все вершины имеют чётную степень.
+          Следовательно, по теореме \ref{thm:euler-crit} в графе $G_1$
+          существует циклический эйлеров путь $C$. Тогда в графе $G$ можно
+          построить эйлеров путь, начиная от $u$: $u C u v$.
+        \item
+          $G_1$ --- несвязный. Тогда $G_1$ разрывается на две компоненты:
+          $G_{11}$ и $G_{12}$. Обе компоненты по теореме \ref{thm:euler-crit}
+          являются эйлеровыми графами $\implies$ содержат циклические эйлеровы
+          пути $C_1$ и $C_2$. Тогда в графе $G$ строят эйлеров путь: $u C_1 u v
+          C_2 v$.
+      \end{enumerate}
+    \item
+      $u$ и $v$ не смежны. Рассмотрим граф $G_2$, который получается из $G$
+      добавлением ребра $\set{u, v}$. В графе $G_2$ все вершины окажутся
+      чётными, сохранится связность. Следовательно, граф $G_2$ является
+      эйлеровым, в нём существует циклический эйлеров путь $C$.
+
+      Пройдём по $C$ из $v$, выбрав первым ребром ребро $\set{u, v}$. Закончим в
+      $v$. Теперь пройдём этот же путь в обратном порядке, исключив на начальном
+      шаге ребро $\set{u, v}$. Очевидно, что этот путь будет эйлеровым путём в
+      графе $G$, соединяющим вершины $u$ и $v$.
+  \end{enumerate}
+\end{proof}
 
 \section{Гамильтоновы графы. Доказательство с нулевым разглашением гамильтонова
 цикла. Теорема Оре. Теорема Дирака (следствие т. Оре). Достаточное условие Поша.
 Достаточное условие Хватала.}
 
-\dots
+\begin{definition}
+  Цепь длиной $n - 1$ в $n$-вершинном графе называется гамильтоновой цепью.
+\end{definition}
+
+\begin{definition}
+  Цикл длины $n$ в таком графе называется гамильтоновым циклом. Таким образом,
+  гамильтонов цикл --- цикл, проходящий по всем вершинам графа.
+\end{definition}
+
+\begin{definition}
+  Граф, содержащий гамильтонов цикл, называется гамильтоновым.
+\end{definition}
+
+Двудольный граф может быть гамильтоновым только если в его долях равное
+количество вершин (необходимое условие).
+
+\begin{theorem}[Доказательство с нулевым разглашением]
+  Гамильтонов цикл для больших графов. $G$ --- большой граф. Пегги ---
+  доказывающая сторона, знает гамильтонов цикл в $G$. Виктор --- проверяющая
+  сторона. Пегги хочет доказать Виктору, что она знает гамильтонов цикл, при
+  этом:
+  \begin{enumerate}
+    \item Не выдавая при этом ни самого цикла, ни какой-либо информации о нём;
+    \item
+      Проверяющий (Виктор) не сможет на основе полученной информации доказать,
+      что он знает гамильтонов цикл.
+  \end{enumerate}
+
+  Раунд протокола:
+  \begin{enumerate}
+    \item Пегги создаёт граф $H$, изоморфный $G$;
+    \item Пегги передаёт граф $H$ Виктору;
+    \item
+      Виктор выбирает случайный бит $b \in \set{0, 1}$.
+      \begin{enumerate}
+        \item 
+          Если $b = 0$, то Виктор просит Пегги доказать изоморфизм $G$ и $H$, то
+          есть предоставить взаимно однозначное соответствие вершин этих двух
+          графов. Виктор может проверить, действительно ли $G$ и $H$ изоморфны.
+        \item
+          Если $b = 1$, то Виктор просит Пегги указать гамильтонов цикл в $H$.
+      \end{enumerate}
+  \end{enumerate}
+
+  Для задачи изоморфизма графов на данный момент не доказана ни её
+  принадлежность классу $P$, ни её NP-полнота, поэтому считаем, что невозможно
+  из гамильтонова цикла в $H$ вычислить гамильтонов цикл в изоморфном $G$.
+
+  В каждом раунде Виктор выбирает новый случайный бит, который неизвестен
+  Пегги, а Пегги предоставляет новый $H$. Чтобы Пегги могла ответить на оба
+  вопроса, нужно, чтобы $H$ был в самом деле изоморфен $G$, и Пегги должна знать
+  гамильтонов цикл в $H$ (а значит также и в $G$).
+
+  После достаточного числа раундов, Виктор может быть уверен в том, что у Пегги
+  действительно есть знание о гамильтоновом цикле в $G$. Пегги не раскрывает
+  никакой информации о гамильтоновом цикле в $G$. Виктору сложно будет доказать
+  кому-либо ещё, что он сам или Пегги знают гамильтонов цикл в $G$.
+
+  Предположим, что Пегги неизвестен гамильтонов цикл в $G$, но она хочет
+  обмануть Виктора. Тогда Пегги необходим неизоморфный $G$ граф $G'$, в котором
+  она всё-таки знает гамильтонов цикл. В каждом раунде она может передавать
+  Виктору либо $H'$ --- изоморфный $G'$, либо $H$ --- изоморфный $G$.
+
+  Если Виктор попросит доказать изоморфизм графов, и ему был передан $H$, то
+  обман не вскроется. Если Виктор просит показать гамильтонов цикл, и ему был
+  передан $H'$, то обман не вскроется. Вероятность того, что Пегги всё-таки
+  обманет Виктора после $k$ раундов, равна $1/2^k$.
+
+  Боб может предположить, что Виктор и Пегги в сговоре, и в каждом раунде Виктор
+  заранее сообщал Пегги свой выбор случайного бита, чтобы Пегги могла передавать
+  ему H для проверок изоморфизма и H′ для проверок гамильтонова цикла.
+
+  Таким образом, без участия Пегги доказать, что она знает гамильтонов цикл,
+  можно лишь доказав, что во всех раундах протокола выбирались действительно
+  случайные биты.
+
+  Задача, связанная с определением <<имеется ли в заданном графе гамильтонов
+  цикл>>, является NP-полной.
+\end{theorem}
+
+\begin{theorem}[Достаточное условие гамильтоновости, Оре]
+  Если в связном графе с числом вершин $n \geq 3$ для любых двух несмежных
+  вершин $u$ и $v$ выполняется неравенство: $d(u) + d(v) \geq n$, то граф
+  является гамильтоновым.
+\end{theorem}
+\begin{proof}
+  Пусть дан граф $G = (V, \alpha)$, удовлетворяющий условиям теоремы. Покажем,
+  что в нём есть гамильтонов цикл.
+
+  Найдём в графе $G$ цепь наибольшей длины. Обозначим эту наибольшую длину $k$.
+  Цепь $P$: $u_0 u_1 \dots u_k$.
+
+  Предположим, что $u_0$ и $u_k$ не смежны. В противном случае получаем, что
+  $u_0 u_1 \dots u_k u_0$ --- гамильтонов цикл.
+
+  Итак, $u_0$ и $u_k$ не смежны. Изучим свойства цепи $P$.
+  \begin{enumerate}
+    \item
+      Любая вершина графа $G$, смежная с $u_0$ или с $u_k$, входит в состав
+      цепи: иначе мы смогли бы построить цепь длины $(k + 1)$, добавив
+      соответствующую вершину в начало или конец цепи.
+    \item
+      Обозначим $d(u_0) = s$. По первому пункту все $s$ вершин входят в состав
+      цепи $P$. В порядке прохождения цепи $P$ занумеруем вершины, смежные с
+      $u_0$: $u_{i1} u_{i2} \dots u_{is} u_{i1} = u_1$.
+
+      \begin{center}
+        \includegraphics[width=0.6\textwidth]{lec8-ore1}
+      \end{center}
+
+      Обозначим через $A$ множество вершин цепи $P$, которые имеют вид
+      $u_{i_{t - 1}}$, то есть это вершины цепи $P$, предшествующие вершинам,
+      смежным с $u_0$. $|A| = s$. Сама $u_0$ тоже попадает в $A$.
+
+      Если из $P$ выбросить вершины $A$, то есть $|P \backslash A| = (k + 1) -
+      s$. Заметим, что в состав $P \backslash A$ входит вершина $u_k$.
+    \item
+      По условию $d(u_0) + d(u_k) \geq n$. Следовательно, $d(u_k) \geq n - s
+      \geq (k + 1) - s$. $d(u_0) = s$, $(k + 1)$ --- количество вершин в самой
+      большой цепи. Таким образом, количество вершин, смежных с $u_k$, не
+      меньше, чем $(k + 1) - s$. При этом согласно пункту 1 все эти вершины
+      присутствуют в цепи $P$ и очевидно, что среди них нет самой $u_k$.
+    \item
+      Из $u_k$ выходит не меньше, чем $(k + 1) - s$ рёбер. Следовательно, по
+      крайней мере одно ребро другим концом имеет вершину, входящую в состав
+      $A$.
+    \item
+      Обозначим через $u_{i_{t - 1}}$ вершину из $A$, смежную с $u_k$.
+      Рассмотрим подграф графа $G$, порождённый вершинами, входящими в состав
+      цепи $P$. Обозначим его $G^*$. Докажем, что $G^*$ --- гамильтонов.
+
+      \begin{center}
+        \includegraphics[width=0.6\textwidth]{lec8-ore1}
+      \end{center}
+
+      Действительно, гамильтоновым циклом в нём будет $u_0 \to u_{i_t}
+      \overset{P}{\to} u_k \to u_{i_{t - 1}} \overset{P}{\to} u_0$.
+      
+      Если $G^* = G$, то $G$ --- гамильтонов. Иначе существует некоторая вершина
+      $u \not\in G^*$. В силу связности $G$, не нарушая общности, можно считать,
+      что $u$ смежна с $u^*$ в $P$.
+
+      Построим гамильтонов цикл в графе $G^*$. Обозначим его через $C$. В графе
+      $G$ теперь можно построить цепь длины $(k + 1)$: $u u^* C$. Эта цепь
+      содержит все вершины цепи $P$ и вершину $u$, которая входила в состав $P$.
+
+      Таким образом, $(k + 1) + 1 = k + 2$. Это противоречит предположению о
+      максимальности цепи $P$.
+  \end{enumerate}
+\end{proof}
+
+\begin{corollary}[Теорема Дирака]
+  Если в связном графе степень любой вершины $d(u) \geq \frac{n}{2}$, то граф
+  гамильтонов.
+\end{corollary}
+
+\begin{corollary}[Оре]
+  Если в связном графе с числом вершин $n \geq 3$ для любых двух несмежных
+  вершин $u$ и $v$ выполняется неравенство: $d(u) + d(v) \geq n - 1$, то в
+  графе есть гамильтонова цепь.
+\end{corollary}
+
+\begin{theorem}[Достаточное условие Поша]
+  Если граф $G$ с числом вершин $n \geq 3$ и степенной последовательностью
+  $d_1 \leq \dots \leq d_n$ удовлетворяет следующим двум условиям, то он
+  гамильтонов:
+  \begin{enumerate}
+    \item
+      Для всякого $k$, $1 \leq k < (n - 1) / 2$, число вершин со степенями,
+      меньшими или равными $k$, меньше, чем $k$;
+    \item
+      Для нечётного $n$ число вершин со степенями, меньшими или равными
+      $(n - 1) / 2$ не превосходит $(n - 1) / 2$.
+  \end{enumerate}
+\end{theorem}
+
+\begin{theorem}[Достаточное условие Хватала]
+  Если граф $G$ с числом вершин $n \geq 3$ и степенной последовательностью
+  $d_1 \leq \dots \leq d_n$ удовлетворяет следующему условию, то он гамильтонов:
+  для любого $k$ верна импликация
+  \begin{equation*}
+    (d_k \leq k \leq n/2) \implies (d_{n - k} \geq n - k)$
+  \end{equation*}
+\end{theorem}
 
 \section{Замыкание. Критерий и достаточное условие Бонди-Хватала.}
 
-\dots
+\begin{definition}
+  Замыкание $[G]$ $n$-вершинного графа $G$ получается из графа $G$ добавлением
+  рёбер $\set{u, v}$ для всех пар вершин $u$ и $v$, для которых выполняется
+  условие $d(u) + d(v) \geq n$.
+\end{definition}
+
+\begin{theorem}[Критерий гамильтоновости, Бонди-Хватал]
+  Граф $G$ является гамильтоновым $\iff$ его замыкание $[G]$ является
+  гамильтоновым.
+\end{theorem}
 
+\begin{theorem}[Достаточное условие гамильтоновости, Бонди-Хватал]
+  Если замыкание $[G]$ графа $G$ является полным графом, то граф $G$ ---
+  гамильтонов.
+\end{theorem}
 
 
 
 \chapter{Пути в орграфах}
 
+\section{Маршрут в орграфе, путь, контур. Бесконтурный орграф. Связный орграф.}
+
+\begin{definition}
+  Маршрутом в орграфе называется последовательность дуг $(v_1, v_2), (v_2, v_3),
+  \dots, (v_{n - 1}, v_n)$, где $(v_{i - 1}, v_i) \in \alpha)$.
+
+  Маршрут --- последовательность дуг, в которой конец каждой дуги является
+  началом следующей. Говорят, что маршрут проходит через вершины $v_0 v_1
+  \dots v_n$. Этим же способом можно и записывать маршрут. $v_0$ --- начальная
+  вершина, $v_n$ --- конечная.
+\end{definition}
+
+\begin{definition}
+  Маршрут, в котором каждая дуга встречается только один раз, называется путём.
+\end{definition}
+
+\begin{definition}
+  Путь, в котором начальная и конечная вершины совпадают, называется
+  циклическим.
+\end{definition}
+
+\begin{definition}
+  Путь, каждая вершина которого принадлежит не более, чем двум его дугам ---
+  простой.
+\end{definition}
+
+\begin{definition}
+  Простой циклический путь в орграфе называется контуром.
+\end{definition}
+
+\begin{definition}
+  Простой путь, не являющийся контуром, называется ориентированной цепью
+  (орцепью, просто цепью).
+\end{definition}
+
+\begin{definition}
+  Длиной маршрута называется число его дуг. В орграфе, в отличие от
+  неориентированного графа длина цикла и контура может быть меньше трёх.
+\end{definition}
+
+\begin{definition}
+  Контур длины 1 (петля) называется тривиальным контуром.
+\end{definition}
+
+\begin{definition}
+  Орграф, не содержащий нетривиальных контуров, называется бесконтурным.
+\end{definition}
+
+Каждому орграфу можно поставить в соответствие единственный неориентированный
+граф, называемый симметризацией, если каждую дугу, ведущую из одной вершины в
+другую, заменить неориентированным ребром, соединяющим ту же пару вершин.
+
+\begin{definition}
+  $\vec{G}$ называется связным, если его симметризация является связным графом.
+\end{definition}
+
+Если в орграфе $\vec{G}$ $n$ вершин и $m$ дуг, то максимальная длина пути в
+орграфе $\vec{G}$ не больше $m$, а контура --- не больше $n$.
+
+\section{Критерий эйлеровости орграфа. Критерий существования эйлерова пути.}
+
+\begin{definition}
+  Путь длины $m$ в орграфе называется эйлеровым путём.
+\end{definition}
+
+\begin{definition}
+  Связный орграф называется эйлеровым, если в нём существует циклический эйлеров
+  путь.
+\end{definition}
+
+\begin{definition}
+  Контур длины $n$ в орграфе называется гамильтоновым.
+\end{definition}
+
+\begin{definition}
+  Ориентированная цепь длины $(n - 1)$ в орграфе называется гамильтоновой
+  цепью.
+\end{definition}
+
+\begin{definition}
+  Связный орграф называется гамильтоновым, если в нём существует гамильтонов
+  контур.
+\end{definition}
+
+\begin{theorem}[Критерий эйлеровости орграфа]
+  Связный орграф $\vec{G}$ эйлеров $\iff$ $\forall v \in V$ выполняется $d^+(v) =
+  d^-(v)$.
+\end{theorem}
+\begin{proof}
+  \textbf{TODO}: доказательство самостоятельно
+\end{proof}
+
+\begin{theorem}[Критерий существования эйлерова пути]
+  В связном орграфе $\vec{G}$ существует эйлеров путь, соединяющий две различные
+  вершины $u$ и $v$ тогда и только тогда, когда
+  \begin{equation*}
+    \begin{cases}
+      d^+(u) = d^-(u) + 1 \\
+      d^-(v) = d^+(v) + 1 \\
+      d^+(w) = d^-(w), w \neq u, w \neq v
+    \end{cases}
+  \end{equation*}
+\end{theorem}
+\begin{proof}
+  \textbf{TODO}: доказательство самостоятельно
+\end{proof}
+
+Эффективных алгоритмов нахождения гамильтонова контура в орграфе не известно, а
+задача проверки, существует ли в орграфе гамильтонов контур, является NP-полной.
+
+\section{Сеть. Поиск кратчайших путей: алгоритмы Дейкстры, Беллмана-Форда,
+Флойда-Уоршелла.}
+
+\begin{definition}
+  Сетью называется граф, каждому ребру (дуге) которого приписано некоторое
+  число, называемое весом, длиной или стоимостью ребра (дуги). Обозначается
+  $w(u, v)$. $\vec{G} = (V, \alpha),\, w : \alpha \to \mathbb{R}$.
+\end{definition}
+
+\begin{definition}
+  Длиной пути в сети называется сумма весов дуг, входящих в состав этого пути.
+\end{definition}
+
+\begin{definition}
+  Сеть называется корневой, если в ней существует выделенная вершина $v$,
+  называемая корнем, и которой существует путь во все остальные вершины сети.
+\end{definition}
+
+\begin{definition}
+  Путь в сети называется кратчайшим, если его длина является минимальной из всех
+  длин путей, соединяющих эти вершины.
+\end{definition}
+
+По постановке задачи выделяют сети с положительными весами и сети, в которых
+веса могут быть отрицательными.
+
+Существенным является наличие в сети контура отрицательной длины. Понятие
+кратчайшего путь утрачивает смысл для всех вершин, находящихся в контуре
+отрицательной длины, если он достижим из заданной вершины и для тех вершин,
+которые достижимы из вершин этого контура.
+
+Очевидно, что любая часть кратчайшего пути также является кратчайшим путём.
+Рассмотрим кратчайший путь $u_1 \dots u_k$. Если $u_i \dots u_j (i < j)$ ---
+часть этого пути --- не является кратчайшим путём из $u_i$ в $u_j$, то заменив
+эту часть пути на кратчайший путь, мы получили бы путь меньшей длины, что
+противоречило бы тому, что исходный путь был бы кратчайшим.
+
+Таким образом, для задачи нахождения кратчайших путей выполняется свойство
+оптимальности подзадач.
+
+Рассмотрим несколько вариантов задачи.
+\begin{enumerate}
+  \item
+    Дана вершина $u$ и надо найти кратчайшие пути из $u$ во все остальные
+    вершины сети.
+  \item
+    Дана вершина $v$. Требуется найти кратчайшие пути из всех остальных вершин
+    в вершину $v$.
+  \item Даны вершины $u$ и $v$. Требуется найти кратчайший путь из $u$ в $v$.
+  \item Найти кратчайшие пути между всеми парами вершин сети.
+\end{enumerate}
+
+Для каждой вершины $v$ будем хранить оценку длины кратчайшего пути до вершины
+$v$ из заданной. Обозначим $\lambda(v)$. Также будем хранить непосредственного
+предшественника вершины $v$ в этом пути. Обозначим $\pi(v)$.
+
+Во многих алгоритмах решающих задачи поиска кратчайших путей, используется
+процедура релаксации дуги. Релаксация дуги состоит в выборе меньшего из двух
+возможных путей: пути, который уже был построен в вершину $v$, и пути в $v$
+через вершину $u$ по дуге $(u, v)$.
+
+Если $\lambda(u) + w(u, v) < \lambda(v)$, то пересчитываем $\lambda(v)$ и
+$\pi(v)$.
+\begin{align*}
+  \lambda(v) &= \lambda(u) + w(u, v) \\
+  \pi(v) &= u
+\end{align*}
+
+\begin{theorem}[Алгорим Дейкстры]
+  Рассмотрим сеть с положительными весами. Рассмотрим задачу поиска кратчайших
+  путей из одной вершины до всех остальных. $v_0$ --- корень сети.
+  \begin{enumerate}
+    \item
+      Выполняется инициализация весов и предшественников. Множество $U = \set{
+      v_0}$,
+      \begin{align*}
+        &\begin{cases}
+          \lambda(v_0) &= 0 \\
+          \pi(v_0) &= NULL \\
+        \end{cases} \\
+        &\begin{cases}
+          \lambda(v) &= +\infty \\
+          \pi(v) &= NULL \\
+        \end{cases}
+      \end{align*}
+    \item
+      Для всех вершин $V \backslash U$, в которые есть дуга из последней
+      добавленной в $U$ вершины, выполняем релаксацию.
+    \item
+      Выбираем вершину из $V \backslash U$ с минимальным значением $\lambda(v)$.
+      Добавляем её во множество $U$: $U = U \cup \set{v}$. Если множество $U$
+      совпало с множеством $V$, то алгоритм завершён. Иначе повторить пункт 2.
+  \end{enumerate}
+\end{theorem}
+
+\begin{theorem}
+  Описанный алгоритм приводит к построению кратчайших путей из $v_0$ в заданной
+  корневой сети.
+\end{theorem}
+\begin{proof}
+  Требуется доказать, что после окончания работы алгоритма в каждую вершину
+  сети $v \neq v_0$ ведёт единственный путь, составленный из дуг, выбранных на
+  шаге 3 алгоритма. Этот путь является кратчайшим из $v_0$ в $v$, и его длина
+  равна метке вершины $v$, $\lambda(v)$.
+
+  Доказательство индукцией по расстоянию от $v_0$ до $v$.
+  \begin{enumerate}
+    \item
+      Пусть $v_1$ --- некоторая вершина, ближайшая к $v_0$. После инициализации
+      $\lambda(v_0) = 0, \lambda(v_1) = +\infty$. После релаксации дуги $(v_0,
+      v_1)$ получаем $\lambda(v_1) = \lambda(v_0) + w(v_0, v_1) = w(v_0, v_1)$.
+
+      Дуга из $v_0$ в $v_1$ является кратчайшей, тогда вершина $v_1$ будет
+      выбрана на третьем шаге алгоритма, и её метка будет равна длине
+      кратчайшего пути. А предшественник $\pi(v_1) = v_0$.
+    \item
+      Пусть доказанное утверждение справедливо для всех вершин, удалённых от
+      вершины $v_0$ меньше вершины $v$. В момент выбора вершины $v$ её метка
+      будет иметь вид $\lambda(u) + w(u, v)$, где $u$ --- некоторая вершина,
+      которая была выбрана в ходе алгоритма раньше.
+
+      По предположению индукции для вершины $u$ верны все доказанные утверждения.
+      А именно: кратчайший путь из $v_0$ до $u$ состоит из выбранных в ходе
+      алгоритма дуг, а его длина равна метке вершины $u$.
+
+      Обозначим через $p$ путь от $v_0$ до $u$.
+      \begin{center}
+        \includegraphics[width=0.4\textwidth]{lec10-dijkstra1}
+      \end{center}
+
+      Пусть кратчайшим путём из $v_0$ в $v$ является путь $v_0 p^* u^* v$. В
+      силу оптимальности подзадачи путь $v_0 p^* u^*$ является кратчайшим путём
+      из $v_0$ в $u^*$. По предположению индукции путь по дугам, выбранным
+      в алгоритме от $v_0$ до $u^*$, является кратчайшим и имеет длину
+      $\lambda(u^*)$.
+
+      Так как путь $v_0 p^* u^*$ является кратчайшим, то длина этого пути равна
+      $\lambda(u^*)$. Тогда длина кратчайшего пути $v_0 p^* u^* v$ будет равна
+      $\lambda(u^*) + w(u^*, v)$. Так как этот путь кратчайший, то его длина
+      не может быть больше длины $v_0 p u v$. $\lambda(u^*) + w(u^*, v) \leq
+      \lambda(u) + w(u, v)$.
+
+      В ходе алгоритма при выборе вершины $v$ была использована дуга $(u, v)$,
+      где $u = \pi(v)$. Это означает, что эта дуга даёт минимум значения
+      выражения $\lambda(u) + w(u, v)$ по всем вершинам $u$, выбранным ранее
+      вершины $v$.
+
+      В частности, так как дуга $(u^*, v)$ не была использована, то это
+      означает, что
+      \begin{equation*}
+        \lambda(u^*) + w(u^*, v) \geq \lambda(u) + w(u, v)
+      \end{equation*}
+
+      С учётом неравенства, полученного ранее, получаем
+      \begin{equation*}
+        \lambda(u^*) + w(u^*, v) = \lambda(u) + w(u, v)
+      \end{equation*}
+
+      Следовательно, построенный в ходе алгоритма путь является кратчайшим, и
+      его длина равна метке вершины $v$.
+  \end{enumerate}
+\end{proof}
+
+\begin{theorem}[Алгоритм Беллмана-Форда]
+  Пусть в сети допускаются отрицательные веса, но не контуров отрицательной
+  длины, достижимых из выбранной вершины. Очевидно, что кратчайший путь в этом
+  случае будет являться цепью. Если в сети $n$ вершин, то длина цепи $\leq n -
+  1$.
+  
+  Выполним первоначальную инициализацию меток вершина также, как в алгоритме
+  Дейкстры.
+  \begin{align*}
+    &\begin{cases}
+      \lambda(v_0) &= 0 \\
+      \pi(v_0) &= NULL \\
+    \end{cases} \\
+    &\begin{cases}
+      \lambda(v) &= +\infty \\
+      \pi(v) &= NULL \\
+    \end{cases}
+  \end{align*}
+
+  Выполним релаксацию по всем дугам сети. В результате получим оценки для всех
+  кратчайших путей длины 1. Будут пересчитаны метки вершин, достижимых из
+  выбранной вершины $v_0$ по пути длины 1.
+
+  Проведём ещё раз релаксацию по всем дугам сети. Получим оценки кратчайших
+  путей длины не менее 2, и так далее.
+
+  Выполнив $(n - 1)$ релаксацию по всем дугам сети, получим оценки кратчайших
+  путей длины до $(n - 1)$, то есть просто кратчайших путей из $v_0$ до
+  остальных.
+
+  Если в сети отсутствуют контуры отрицательной длины, достижимые из $v_0$, то
+  полученные метки позволяют построить дерево кратчайших путей из вершины $v_0$.
+
+  Если выполнить релаксацию ещё один раз, и при этом хотя бы одна метка будет
+  изменена, то это означает, что в сети есть контур отрицательной длины. Тогда
+  решение некорректно.
+
+  Убедимся, что последняя релаксация действительно позволяет определить
+  наличие контура отрицательной длины. Предположим, что такой контур есть:
+  $v_1, v_2, \dots, v_k, v_1$.
+  \begin{center}
+    \includegraphics[width=0.5\textwidth]{lec11-bellman1}
+  \end{center}
+
+  Так как контур достижим из вершины $v_0$, то после выполнения $(n - 1)$
+  итерации релаксации по всем дугам сети, все вершины контура получат некоторую
+  метку, являющуюся оценкой кратчайшего пути. И это значение будет отлично от
+  $\infty$.
+
+  Предположим, что после выполнения $n$-ой последней итерации релаксации по
+  всем дугам сети значения меток не изменились. В том числе в релаксациях
+  участвовали и дуги, входящие в состав контура.
+
+  Раз значения меток не изменились, то это означает, что имеют место следующие
+  неравенства:
+  \begin{align*}
+    (v_1, v_2) &: \lambda(v_2) \leq \lambda(v_1) + w(v_1, v_2) \\
+               &\dots \\
+    (v_k, v_1) &: \lambda(v_1) \leq \lambda(v_k) + w(v_k, v_1) \\
+  \end{align*}
+
+  Просуммируем все неравенства
+  \begin{equation*}
+    0 \leq w(v_1, v_2) + \dots + w(v_k, v_1)
+  \end{equation*}
+
+  А по условию этот контур отрицательной длины. Таким образом, алгоритм
+  Беллмана-Форда действительно позволяет найти кратчайшие пути в сети с
+  отрицательным весом и определить наличие контура отрицательной длины,
+  достижимого из выбранной вершины.
+
+  Эффективность алгоритма Беллмана-Форда --- $O(nm)$, где $m$ --- количество
+  дуг.
+\end{theorem}
+
+\begin{theorem}[Алгоритм Флойда-Уоршелла]
+  Алгоритм позволяет строить кратчайшие пути между всеми парами вершин сети за
+  время $O(n^3)$. Алгоритм является динамическим.
+
+  Обозначим через $d_{ij}^{(k)}$ кратчайший путь из вершины $i$ в вершину $j$,
+  среди внутренних вершин которого нет вершины с номером $> k$.
+
+  Очевидно, что
+  \begin{equation*}
+    d_{ij}^{(0)} = \begin{cases}
+      w(v_i, v_j), &(v_i, v_j) \in \alpha \\
+      \infty, &(v_i, v_j) \not\in \alpha
+    \end{cases}
+  \end{equation*}
+
+  $d_{ij}^{(n)}$ будет совпадать с длиной кратчайшего пути из $i$ в $j$.
+  $d_{ij}^{(n)} = d_{ij}$.
+
+  Пусть известны значения $d_{ij}^{(k)}$. Надо определить $d_{ij}^{(k + 1)}$.
+  Заметим, что кратчайший путь из $i$ в $j$ через вершины с номерами $\leq k + 1$
+  может содержать $(k + 1)$-ю вершину или не содержать её.
+
+  Если в пути нет вершины с номером $(k + 1)$, то $d_{ij}^{(k + 1)} =
+  d_{ij}^{(k)}$. Если вершина $(k + 1)$ есть в пути, то часть этого пути от
+  вершины $i$ до $(k + 1)$ и от $(k + 1)$ до $j$ также является кратчайшим
+  путём, но не содержит вершину $(k + 1)$ в качестве внутренней вершины.
+  \begin{equation*}
+    d_{ij}^{(k + 1)} = d_{i(k + 1)}^{(k)} + d_{(k + 1)j}^{(k)}
+  \end{equation*}
+
+  \begin{center}
+    \includegraphics[width=0.5\textwidth]{lec11-floyd1}
+  \end{center}
+
+  Таким образом, выбрав минимальное из указанных значений, можно рассчитать все
+  значения $d_{ij}^{(k + 1)}$ по предыдущим значениям. Выполнив итерации по
+  $k = 1, \dots, n$, будет получена матрица кратчайших путей между всеми
+  парами вершин.
+
+  Для построения самих путей необходимо использовать дополнительную матрицу
+  предшественников, которая будет пересчитываться следующим образом:
+
+  Если
+  \begin{equation*}
+    d_{ij}^{(k)} > d_{i(k + 1)}^{(k)} + d_{(k + 1)j}^{(k)}
+  \end{equation*}
+  то
+  \begin{equation*}
+    \pi_{ij}^{(k + 1)} = \pi_{(k + 1)j}^{(k)}
+  \end{equation*}
+  иначе
+  \begin{equation*}
+    \pi_{ij}^{(k + 1)} = \pi_{ij}^{(k)}
+  \end{equation*}
+\end{theorem}
+
+\section{Достижимость. Теорема о существовании маршрута длины k. Матрица
+достижимости.}
+
+\begin{definition}
+  Говорят, что в орграфе $\vec{G}$ вершина $v$ достижима из вершины $u$, если
+  существует путь из $u$ в $v$.
+
+  По определению считаем, что каждая вершина достижима из самой себя вне
+  зависимости от существования в ней петли.
+\end{definition}
+
+Пусть $A$ --- матрица смежности орграфа $\vec{G}$.
+
+\begin{theorem}
+  Элемент $a_{ij}^{(k)}$ матрицы $A^k$ отличен от 0 $\iff$ в орграфе существует
+  маршрут длины $k$ из вершины $v_i$ в $v_j$.
+  \label{thm:route-k-length}
+\end{theorem}
+\begin{proof}
+  ММИ по $k$.
+  \begin{enumerate}
+    \item
+      $k = 1$. $A^1 = A$. $a_{ij} = 1 \iff$ существует дуга $(v_i, v_j)$. Эту
+      дугу можно рассматривать как маршрут длины 1.
+    \item
+      Предположим, что утверждение справедливо для $k = l$. Докажем истинность
+      для $k = l + 1$.
+      \begin{align*}
+        a_{ij}^{(l + 1)} = 1 \iff 1 = \sum_{s = 1}^n a_{is}^{(l)} a_{sj} \iff
+        (\exists s_0) (a_{is_0}^{(l)} a_{s_0 j} = 1) \iff (\exists s_0)
+        (a_{is_0}^{(l)} = 1 \land a_{s_0 j} = 1).
+      \end{align*}
+
+      Это означает с учётом предположения индукции, что существует маршрут длины
+      $l$ из $v_i$ в $v_{s_0}$. И есть дуга $(v_{s_0}, v_j)$. Следовательно,
+      существует маршрут длины $(l + 1)$.
+  \end{enumerate}
+\end{proof}
+
+Обозначим через $E$ тождественную булеву матрицу (на главной диагонали стоят 1,
+в остальных местах --- 0).
+
+\begin{corollary}
+  Вершина $v_j$ достижима из $v_i$ в $n$-вершинном графе $\vec{G}$ $\iff$ в
+  матрице $D = E + \sum_{i = 1}^{n - 1} A^i$ элемент $d_{ij} = 1$.
+\end{corollary}
+\begin{proof}
+  \textbf{Необходимость.}
+
+  Пусть $v_j$ достижима из $v_i$. Тогда существует путь из $v_i$ в $v_j$, а
+  следовательно, существует и простой путь (если $v_i \neq v_j$, то это будет
+  цепь). Так как длина цепи не превышает $(n - 1)$, то существует путь из
+  $v_i$ в $v_j$, длина которого не превышает $(n - 1)$.
+
+  Таким образом, по теореме \ref{thm:route-k-length} это означает, что для
+  некоторого значения $k$ выполняется $a_{ij}^{(k)},\, k \leq n - 1$. Таким
+  образом, если $v_i \neq v_j$, то элемент матрицы $d_{ij} = 1$, потому что
+  существует путь. А если $v_i = v_j$, то $d_{ij} = 1$ за счёт $E$.
+
+  \textbf{Достаточность.}
+
+  Пусть $d_{ij} = 1 = \ds\sum_{k = 1}^{n - 1} a_{ij}^{(k)} + e_{ij}$.
+
+  $i \neq j : \exists k: a_{ij}^{(k)} = 1$. Следовательно, существует маршрут
+  длины $k$ из $v_i$ в $v_j$, то есть $v_j$ достижима из $v_i$.
+\end{proof}
+
+\begin{definition}
+  Матрицу $D$ называют матрицей достижимости орграфа $\vec{G}$, а
+  соответствующее ей отношение $\delta \subseteq V \times V$ называется
+  отношением достижимости. Таким образом, если $(v_i, v_j) \in \delta \iff$
+  $v_j$ достижима из $v_i$.
+\end{definition}
+
+\section{Отношение взаимной достижимости. Сильные компоненты. Ориентация графа,
+приводящая к сильно связному орграфу.}
+
+\begin{definition}
+  Симметричная часть отношения достижимости, то есть отношение $\varepsilon
+  = \delta \cap \delta^{-1}$, называется отношением взаимной достижимости в
+  орграфе. По определению $(v_i, v_j) \in \varepsilon \implies (v_i, v_j) \in
+  \delta \land (v_i, v_j) \in \delta^{-1} \iff (v_i, v_j) \in \delta \land (v_j,
+  v_i) \in \delta$.
+
+  Очевидно, что отношение $\varepsilon$ является отношением эквивалентности:
+  рефлексивность следует из определения достижимости, симметричность и
+  транзитивность очевидны.
+\end{definition}
+
+\begin{definition}
+  Классы эквивалентности отношения $\varepsilon$ называются сильными
+  компонентами или слоями орграфа.
+\end{definition}
+
+\begin{definition}
+  Неодноэлементные сильные компоненты также называются максимальными сильно
+  связными подграфами данного графа.
+\end{definition}
+
+\begin{definition}
+  Если отношение $\varepsilon$ универсально ($\varepsilon = V \times V$), то
+  есть любые две вершины орграфа взаимно достижимы, то такой орграф называется
+  сильно связным или просто сильным.
+\end{definition}
+
+\begin{theorem}[Ориентация графа, приводящая к сильно связному графу]
+  Связный граф допускает ориентацию рёбер, превращающую его в сильно
+  связный орграф $\iff$ каждое его ребро входит в состав некоторого цикла.
+\end{theorem}
+\begin{proof}
+  \textbf{Необходимость.}
+
+  Пусть граф $G = (V, \alpha)$ допускает ориентацию рёбер, превращающую его в
+  сильно связный орграф $\vec{G} = (V, \alpha)$.
+
+  Пусть ребро $\set{u, v}$ не входит ни в какой цикл графа $G$. Тогда это ребро
+  является единственным путём связывающим $u$ и $v$ (оно будет являться мостом).
+
+  Какую бы ориентацию мы ни придали ребру $\set{u, v}$ в орграфе $\vec{G}$
+  вершины $u$ и $v$ не будут взаимно достижимы.
+
+  \textbf{Достаточность.}
+
+  Пусть в $G$ каждое ребро принадлежит некоторому циклу. Выберем произвольный
+  цикл: $v_1, v_2, \dots, v_k, v_1$.
+
+  Ориентируем входящие в его состав рёбра в порядке прохождения цикла:
+  \begin{align*}
+    \set{v_1, v_2} &\to (v_1, v_2) \\
+                   &\dots \\
+    \set{v_k, v_1} &\to (v_k, v_1)
+  \end{align*}
+
+  Если выбранный цикл содержал все вершины графа (то есть был гамильтоновым),
+  то произвольно ориентировав оставшиеся рёбра графа, получим сильно связный
+  орграф. Взаимная достижимость будет осуществляться за счёт построенного
+  гамильтонового контура.
+
+  Пусть исходный цикл содержал не все вершины графа $G$. Обозначим построенный
+  цикл через $C$. В силу связности графа $G$ любая его вершина соединена
+  некоторым путём с любой другое вершиной.
+
+  Пусть $v$ --- вершина графа $G$, не входящая в состав цикла $C$. Не нарушая
+  общности можно считать, что она смежна с некоторой вершиной $v_i$ из цикла
+  $C$. По условию ребро $\set{v, v_i}$ входит в состав некоторого цикла $C^*$.
+
+  Двигаемся от вершины $v_i$ к вершине $v$ и далее по циклу $C^*$, ориентирую
+  рёбра в порядке движения, пропуская рёбра, которые были ориентированы ранее.
+
+  В результате получим некоторый новый контур, который содержит все вершины
+  цикла $C$ и вершину $v$. Продолжая процесс в силу конечности графа получим
+  циклический путь, проходящий через все вершины графа $G$.
+
+  Произвольным образом ориентирую остальные рёбра получаем сильно связный
+  орграф.
+\end{proof}
+
 \section{Источники и стоки. Фактор-граф. Конденсация и ее свойства.
 Бесконтурность конденсации.}
 % Лекция 12
@@ -1074,7 +2764,7 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл�
   \label{def:condensation}
 \end{definition}
 
-% TODO: свойства конденсации
+\textbf{TODO}: свойства конденсации
 
 \begin{theorem}[Бесконтурность конденсации]
   Конденсация всякого орграфа является бесконтурным графом.
@@ -1102,6 +2792,909 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл�
   \emph{Это противоречие}.
 \end{proof}
 
+\section{Источники и стоки в бесконтурных графах. База орграфа и теорема о базе.
+Следствие теоремы.}
+
+\begin{theorem}[Об истоках и стоках в бесконтурных графах]
+  Пусть $\vec{G} = (V, \alpha)$ --- бесконтурный граф, $v$ --- произвольная
+  вершина. Тогда из $v$ достижим некоторый сток, а $v$ достижима из некоторого
+  источника.
+  \label{thm:in-out-contour-free}
+\end{theorem}
+\begin{proof}
+  От противного.
+
+  Рассмотрим первый случай. Пусть $v$ не является ни источником, ни стоком.
+  Существует по крайней мере одна дуга, исходящая из вершины $v$, и одна
+  входящая в отличную от $v$ вершину. Получаем трёхэлементную подцепь,
+  включаемую в некоторую максимальную цепь в орграфе $\vec{G}$. Пусть это
+  будет цепь $u_1 \to u_2 \to \dots \to v \to \dots \to u_{k - 1} \to u_k$.
+
+  Утверждается, что $u_1$ является источником в $\vec{G}$, а $u_k$ --- стоком.
+
+  Предположим, что $u_1$ не является источником. Тогда в $u_1$ приходит дуга
+  из некоторой вершины $w \neq u_1$. Если $w$ не входит в состав построенной
+  цепи, то длина на 1 больше, чем построенная ранее максимальная цепь, а это
+  противоречит максимальности.
+
+  Если $w$ совпадает с некой вершиной построенной цепи, то получим в $\vec{G}$
+  нетривиальный контур $(w u_1 u_2 \dots u_i)$. А это противоречит условию
+  $\implies u_1$ --- источник, и из него достижима $v$.
+
+  Аналогично, если $u_k$ --- не сток, то из неё должна быть дуга в некоторую
+  вершину $u$. Если вершина $u$ не входит в состав цепи, то получим новую цепь
+  длины большей, чем максимальная.
+
+  А если $u$ входит в состав цепи, то получим нетривиальный контур.
+
+  В обоих случаях получаем противоречие. Следовательно, $u_k$ --- сток, и он
+  достигает я из вершины $v$.
+
+  Аналогично рассмотрим случаи, когда вершина $v$ является источником или стоком
+  (заметим, что по определению любая вершина достижима из самой себя).
+\end{proof}
+
+\begin{definition}
+  Базой орграфа $\vec{G} = (V, \alpha)$ называется подмножество $V^* \subseteq
+  V$, если выполняются два условия:
+  \begin{enumerate}
+    \item
+      $\delta(V^*) = V$. Срез $\delta$ по $V^* = V$. Любая вершина орграфа
+      достижима из некоторой вершины базы.
+    \item
+      $\delta \cap V^* \times V^* = \Delta_{V^*}$. Никакая вершина базы не
+      достижима из другой вершины базы.
+  \end{enumerate}
+\end{definition}
+
+\begin{theorem}[О базе орграфа]
+  Каждая база орграфа состоит из взятых по одному представителей из источников
+  конденсации орграфа.
+\end{theorem}
+\begin{proof}
+  \textbf{Необходимость.}
+
+  Пусть $V^*$ --- база орграфа $\vec{G} = (V, \alpha)$. Его конденсация:
+  $\vec{G}/\varepsilon$.
+
+  Если из источника $\varepsilon(u)$ конденсации $V^*$ не выбрано ни одного
+  представителя, то вершины $\vec{G}$, входящие в состав $\varepsilon(u)$ не
+  будут достижимы ни из какой вершины базы, что противоречит определению. Таким
+  образом, в состав базы входят представители из каждого источника конденсации.
+
+  Пусть в $V^*$ попали два представителя одного источника конденсации $u_1 \neq
+  u_2$. Так как $\varepsilon(u)$ является сильно связным графом, то $u_1$ и
+  $u_2$ взаимно достижимы и, следовательно, одновременно не могут входить в
+  базу. Таким образом, все представители источников конденсации входят в базу по
+  одному из каждого источника.
+
+  Пусть в базу входит некоторая вершина $v$, не содержащаяся ни в каком
+  источнике конденсации. Тогда $\varepsilon(v)$ не будет являться источником в
+  конденсации. По теореме \ref{thm:in-out-in-contour-free} достижима из
+  некоторого источника $\varepsilon(u)$ конденсации. По установленному ранее в
+  базе есть представитель из этого источника. Следовательно, $v$ достижима из
+  него.
+
+  Таким образом, вершины, не входящие в состав источников конденсации, не могут
+  входить в базу.
+
+  \textbf{Достаточность.}
+
+  Пусть $V^* \subseteq V$ состоит из взятых по одному представителей из
+  источников конденсации. Покажем, что $V^*$ --- база. Надо показать, что
+  выполнены два условия:
+  \begin{enumerate}
+    \item
+      По теореме \ref{thm:in-out-contour-free}, любая вершина $\varepsilon(v)$
+      конденсации достижима из подходящего источника $\varepsilon(u)$
+      конденсации графа.
+
+      Тогда в $\vec{G}$ вершина $v$ будет достижима из вошедшего в $V^*$
+      источника $\varepsilon(u)$. Таким образом, любая вершина орграфа достижима
+      из подходящей вершины $V^*$.
+    \item
+      Так как вершины из $V^*$ входят в разные источники конденсации, то ни одна
+      из них не может быть достигнута из другой в орграфе $\vec{G}$. Таким
+      образом, $V^*$ --- база в орграфе $\vec{G}$.
+  \end{enumerate}
+\end{proof}
+
+\begin{corollary}
+  Любые две базы орграфа имеют одинаковое количество элементов.
+\end{corollary}
+\begin{proof}
+  Количество элементов в базе равно числу источников конденсации.
+\end{proof}
+
+\section{Теорема о взаимной достижимости вершин и матрице достижимости.}
+
+\begin{theorem}
+  Две вершины орграфа $v_i$ и $v_j$ взаимно достижимы в $\vec{G}$ $\iff$ в
+  матрице достижимости $D$ этого орграфа строки, соответствующие $v_i$ и $v_j$
+  равны между собой.
+\end{theorem}
+\begin{proof}
+  \textbf{Необходимость.}
+
+  Пусть $v_i$ и $v_j$ взаимно достижимы в $\vec{G}$. Тогда любая вершина $v_k$
+  будет достижима из $v_i$ $\iff$ она будет достижима из $v_j$, и наоборот.
+  Таким образом, если $d_{ik} = 1 \iff d_{jk} = 1$.
+
+  \textbf{Достаточность.}
+
+  Пусть в матрице достижимости $D$ совпадают строки, соответствующие вершинам
+  $v_i$ и $v_j$. По определению вершина достижима из самой себя. Тогда $d_{ii} =
+  1 \land d_{jj} = 1$. Так как строки равны, то $\implies \begin{cases}
+    d_{ji} = 1 \\
+    d_{ij} = 1
+  \end{cases}$.
+
+  Таким образом, $v_i$ и $v_j$ взаимно достижимы.
+\end{proof}
+
+Из доказанной теоремы следует простая процедура выделения максимальных сильно
+связных подграфов. Процедура состоит в последовательном просмотре строк матрицы
+достижимости $D$ и выписывании тех вершин, у которых строки равны.
+
+Завершив эту процедуру, мы вычёркиваем одноэлементные классы, то есть
+тривиальные компоненты связности. Оставшиеся классы являются максимальными
+сильно связными подграфами.
+
+Заметим, что можно сразу определить редукцию матрицы смежности орграфа.
+Очевидно, что ни источники, ни стоки не входят ни в какой максимальный сильно
+связный подграф. Поэтому соответствующие им строки и столбцы матрицы смежности
+можно исключить.
+
+В получившемся графе снова могут быть источники и стоки. Их также можно будет
+исключить. Редукция повторяется, пока остаются источники и стоки.
+
+\section{Проверяющий тест. Теорема о минимальных проверяющих тестах.}
+
+Пусть орграф $\vec{G} = (V, \alpha)$ является функциональной моделью системы
+$\Sigma$, допускающей один отказ. Предположим, что у нас есть возможность
+проверить работоспособность любой вершины системы, то есть вершины орграфа
+$\vec{G}$.
+
+Проверка может иметь два исходи:
+\begin{itemize}
+  \item 0, если реакция элемента допустим (элемент исправен);
+  \item 1, если недопустима.
+\end{itemize}
+
+Пусть $\Sigma$ такова, что реакция 1 наследуется всеми элементами, достижимыми
+из неисправной в смысле орграфа $\vec{G}$.
+
+\begin{definition}
+  Проверяющим тестом называется некоторая совокупность проверок элементов
+  системы, позволяющих выяснить существует ли в системе отказ без его
+  локализации.
+\end{definition}
+
+Очевидно, что для любой системы существует проверяющий тест. Например,
+проверка всех элементов.
+
+\begin{definition}
+  Проверяющий тест называется минимальным, если он содержит минимально возможное
+  число проверок.
+\end{definition}
+
+\begin{theorem}[О минимальных проверяющих тестах]
+  Проверяющий тест для системы $\Sigma$ будет минимальным $\iff$ он состоит из
+  проверок элементов, которые соответствуют вершинам орграфа $\vec{G}(\Sigma)$,
+  взятыми по одной из каждого стока конденсации $\vec{G}(\Sigma)/\varepsilon$.
+\end{theorem}
+\begin{proof}
+  Пусть система $\Sigma$ обладает упомянутыми свойствами. В частности, если
+  вершина $v$ неисправна, то сигнал неисправности будет поступать из всех
+  вершин, достижимых из $v$. В бесконтурном графе из любой вершины достижим
+  некоторый сток (теорема \ref{thm:in-out-countour-free}).
+
+  Тогда при отказе любой вершины сигнал неисправности будет поступать из всех
+  стоков конденсации, достижимых из $\varepsilon(v)$.
+
+  С другой стороны, никакой сток конденсации не достижим ни из какого другого.
+  Таким образом, минимальный проверяющий тест состоит из взятых по одному
+  представителю стоков конденсации.
+\end{proof}
+
+\begin{remark}
+  Если рассмотреть граф $\vec{G}^{-1}$, то минимальным проверяющим тестом будет
+  любая база орграфа $\vec{G}^{-1}$.
+\end{remark}
+
+\section{Бесконтурные графы. Отношение достижимости в бесконтурном графе.}
+
+\begin{theorem}[Отношение достижимости в бесконтурном графе]
+  Орграф $\vec{G} = (V, \alpha)$ будет бесконтурным графом $\iff$ его отношение
+  достижимости $\delta$ является отношением порядка на множестве его вершин $V$.
+\end{theorem}
+\begin{proof}
+  Порядком называется рефлексивное, транзитивное и антисимметричное отношение.
+  Очевидно, что отношение достижимости в любом орграфе является транзитивным.
+
+  Оно будет являться отношением порядка, если для него будет выполняться свойство
+  антисимметричности ($\delta \cap \delta^{-1} = \Delta_V$).
+
+  По определению, симметричная часть отношения достижимости, то есть $\delta
+  \cap \delta^{-1} = \varepsilon$, является отношением взаимной достижимости,
+  таким образом, утверждение теоремы означает, что критерием бесконтурности
+  графа является тривиальность его отношения достижимости.
+
+  \textbf{Необходимость.}
+
+  Пусть $\vec{G}$ --- бесконтурный граф, а его отношение взаимной достижимости
+  отлично от тождественного $\varepsilon \neq \Delta_V \implies$ существуют
+  две вершины, достижимые друг из друга, то есть существует путь $P_1$ из
+  $u$ в $v$, $P_2$ --- из $v$ в $u$. Какими бы ни были $P_1$ и $P_2$, всегда
+  можно выделить контур, состоящий из дуг, входящих в эти пути. Таким образом,
+  получим, что граф $\vec{G}$ содержит контур, что противоречит тому, что он
+  бесконтурный.
+
+  \textbf{Достаточность.}
+
+  Пусть отношение взаимной достижимости $\varepsilon$ тожественно $(\varepsilon
+  = \Delta_V)$. Предположим, что $\vec{G}$ не является бесконтурным и пусть
+  $C$ --- некоторый его нетривиальный контур. Выберем на контуре $C$ две
+  различных вершины из $u$ b $v$.
+
+  Очевидно, что $v$ достижима из $u$, а $u$ достижима из $v$, по частям контура
+  $C$. Получили противоречие с тривиальностью $\varepsilon$.
+\end{proof}
+
+\section{Правильная нумерация. Теорема о правильных нумерациях. Следствия
+(неориентированные граф, диграф, база бесконтурного графа).}
+
+\begin{definition}
+  Пусть $\vec{G}$ --- бесконтурный граф $\implies$ $(V, \alpha)$ будет являться
+  конечным упорядоченным множеством. Очевидно, что источниками $\vec{G}$ будут
+  в точности минимальные элементы упорядоченного множества $(V, \alpha)$, а
+  стоками --- максимальные элементы.
+
+  Нумерация вершин $\vec{G}$ называется правильной, если из существования дуги
+  $(v_i, v_j) \implies i \leq j$, то есть номер начальной вершины дуги не
+  превосходит номера конца дуги.
+\end{definition}
+
+\begin{theorem}[О правильных нумерациях]
+  $\vec{G}$ допускает правильную нумерацию $\iff$ $\vec{G}$ бесконтурный.
+  \label{thm:correct-numbering}
+\end{theorem}
+\begin{proof}
+  \textbf{Необходимость.}
+
+  Пусть $\vec{G} = (V, \alpha)$ --- бесконтурный. Тогда $(V, \alpha)$ является
+  упорядоченным множеством. Построим диаграмму упорядоченного множества $(V,
+  \alpha)$. Проведём нумерацию вершин $\vec{G}$, двигаясь по уровням снизу
+  вверх, слева направо.
+
+  Если есть дуга $(v_i, v_j) \in \alpha$, то в силу упорядоченности $V$ будет
+  $v_i \leq v_j$, тогда на диаграмме упорядоченного множества $v_j$ имеет
+  большую высоту, чем $v_i$. В силу выбранной нумерации $i \leq j$.
+
+  \textbf{Достаточность.}
+
+  Пусть орграф $\vec{G}$ допускает правильную нумерацию и пусть он не является
+  бесконтурным $\implies$ в нём есть нетривиальный контур $v_{i_1}, v_{i_2},
+  \dots, v_{i_k}, v_{i_1},\, k > 1 \implies$ так как нумерация правильная, то
+  имеем $i_1 < i_2 < \dots < i_k < i_1$, что невозможно.
+\end{proof}
+
+\begin{corollary}
+  В любом графе можно ввести ориентацию рёбер так, чтобы он стал бесконтурным
+  орграфом.
+\end{corollary}
+\begin{proof}
+  Пусть $G = (V, \alpha)$ --- произвольный неориентированный граф. Выберем
+  произвольную нумерацию его вершин. Пусть $\set{v_i, v_j}$ --- некоторое
+  ребро $G$. Ориентируем его следующим образом:
+  \begin{equation*}
+    \begin{cases}
+      \set{v_i, v_j}, &i < j \\
+      \set{v_j, v_i}, &i > j
+    \end{cases}
+  \end{equation*}
+
+  Произведя таким образом ориентацию всех рёбер, мы получим правильную нумерацию
+  в построенном орграфе $\vec{G}$, и по теореме \ref{thm:correct-numbering} он
+  будет бесконтурным графом.
+\end{proof}
+
+\begin{corollary}
+  В любом направленном графе можно переориентировать некоторые дуги так, что
+  в результате получится бесконтурный граф.
+\end{corollary}
+\begin{proof}
+  Полностью аналогично предыдущему следствию.
+\end{proof}
+
+Так как в бесконтурном графе отношение взаимной достижимости $\varepsilon$
+является тождественным, то конденсация бесконтурного графа изоморфна самому
+графу $(\vec{G}/\varepsilon \cong \vec{G})$.
+
+\begin{corollary}
+  Каждый бесконтурный граф имеет единственную базу, которая состоит из всех его
+  источников.
+\end{corollary}
+
+Для построения правильной нумерации в бесконтурном графе можно воспользоваться
+следующим алгоритмом. Пусть $v \in V,\, \vec{G} = (V, \alpha)$. $v$ ---
+произвольная, $\vec{G}$ --- бесконтурный. Обозначим $A(v) = \set{u \in V :
+(u, v) \in \alpha}$. Множество $P$ --- множество занумерованных вершин.
+Изначально оно равно $\emptyset$.
+
+Пока множество $P$ отлично от множества $V$, выбираем такую вершину $v$, для
+которой $A(v) = \emptyset$. Присваиваем вершине $v$ очередной номер и добавляем
+в множество $P$. Удаляем вершину $v$ из всех множеств $A(u)$, куда она входит
+(для тех вершин, в которые ведёт дуга из $v$).
+
+\begin{definition}
+  Рангом вершины $v$ в бесконтурном графе $\vec{G} = (V, \alpha)$ называется
+  её высота в упорядоченном множестве $(V, \alpha)$.
+\end{definition}
+
+\begin{definition}
+  Ранжированным изображением бесконтурного графа называется орграф, получающийся
+  из диаграммы упорядоченного множества $(V, \alpha)$ ориентацией всех рёбер
+  снизу вверх и добавлением тех дуг, которые не были изображены на диаграмме.
+\end{definition}
+
+\section{Матрица смежности бесконтурного графа. Расконтуривание. Оптимальное
+расконтуривание. Теорема о минимальном расконтуривании.}
+
+\begin{theorem}[О матрице смежности бесконтурного графа]
+  Орграф $\vec{G} = (V, \alpha)$ является бесконтурным $\iff$ при некоторой
+  нумерации вершин его матрица смежности $A$ будет верхней треугольной матрицей,
+  то есть ниже главной диагонали стоят нули.
+  \label{thm:contour-free-matrix}
+\end{theorem}
+\begin{proof}
+  \textbf{Необходимость.}
+
+  Пусть $\vec{G}$ --- бесконтурный граф. Тогда по теореме
+  \ref{thm:correct-numbering} существует правильная нумерация его вершин.
+
+  Запишем матрицу смежности $\vec{G}$ в этой нумерации. Получим, что некоторый
+  элемент матрицы смежности $a_{ij} = 1 \iff (v_i, v_j) \in \alpha$. В силу
+  правильности нумерации $i \leq j$. То есть элемент $a_{ij}$ лежит не ниже
+  главной диагонали $\implies$ ниже главной диагонали нет единиц.
+
+  \textbf{Достаточность.}
+
+  Пусть при некоторой нумерации вершин $\vec{G}$ матрица смежности оказалась
+  верхней треугольной матрицей. Легко видеть, что эта нумерация будет
+  правильной. Рассмотрим $(v_i, v_j) \in \alpha$ --- произвольную $\iff a_{ij} =
+  1,\, i \leq j$.
+\end{proof}
+
+\begin{definition}
+  Расконтуривание $\vec{G} = (V, \alpha)$ --- такое множество его дуг $\alpha^*
+  \subseteq \alpha$, после удаления которых орграф становится бесконтурным. То
+  есть $\vec{G}^* = (V, \alpha \backslash \alpha^*)$ --- бесконтурный.
+\end{definition}
+
+\begin{definition}
+  Расконтуривание называется минимальным, если никакая его собственная часть не
+  является расконтуриванием.
+\end{definition}
+
+\begin{definition}
+  Расконтуривание называется оптимальным, если оно содержит наименьшее
+  возможное среди всех расконтуриваний данного орграфа число дуг.
+\end{definition}
+
+Один из способов расконтуривания основан на теореме
+\ref{thm:contour-free-matrix}.
+
+Если в матрице смежности, составленной при некоторой нумерации вершин,
+ниже главной диагонали окажется некоторое количество единиц, то удалив
+соответствующие дуги, получим орграф с правильной нумерацией вершин, и,
+следовательно, удалённые дуги образуют расконтуривание.
+
+Очевидно, что наибольший интерес представляют минимальные и оптимальные
+расконтуривания. Для поиска оптимального расконтуривания можно производить
+различные нумерации вершин орграфа и среди них выбрать такие, что в матрице
+смежности будет стоять минимальное количество единиц.
+
+Существует способ избежать полного перебора нумераций.
+
+\begin{theorem}[О минимальном расконтуривании]
+  Минимальное расконтуривание не нарушает связности орграфа.
+\end{theorem}
+\begin{proof}
+  $\vec{G} = (V, \alpha)$ --- орграф, не являющийся бесконтурным. Пусть он
+  связный (то есть его симметризация является связным графом).
+
+  Пусть $\alpha^*$ --- минимальное расконтуривание. Будем удалять из $\vec{G}$
+  дуги, входящие в состав $\alpha^*$ по одной.
+
+  Пусть $(v_i, v_j) \in \alpha^*$ --- первая дуга в процессе удаления, после
+  изъятия которой граф окажется не связным. Это означает, что в симметризации
+  графа вершины $v_i$ и $v_j$ окажутся в разных компонентах связности.
+
+  Следовательно, перед удалением дуги $(v_i, v_j)$ вершины $v_i$ и $v_j$ уже
+  не принадлежали никакому контуру.
+
+  Удаление дуги $(v_i, v_j)$ не размыкает никакого контура $\implies$ исключив
+  эту дугу из расконтуривания, мы получим новое расконтуривание, которое
+  содержит на одну дугу меньше, чем $\alpha^*$. Это противоречит минимальности
+  $\alpha^*$.
+\end{proof}
+
+Рассмотрим отношение $\sigma$ на множестве вершин орграфа $(V \times V)$. $(u,
+v) \in \sigma \iff s(u) = s(v)$. $\sigma$ --- отношение, в котором состоят
+вершины, если из них достижимы одни и те же стоки. Очевидно, что $\sigma$
+является отношением эквивалентности: рефлексивно, симметрично и транзитивно.
+
+Эквивалентность $\sigma$ может быть построена по матрице достижимости $D$
+следующим образом.
+
+Сначала в матрице достижимости определяются строки, соответствующие
+стокам: в таких строках единицы стоят только на главной диагонали. Далее
+из матрицы вычёркиваются столбцы, кроме столбца вершин, являющихся стоками.
+
+Получим прямоугольную матрицу вершин, совпадающие строки которой состоят в
+отношении $\sigma$.
+
+\begin{theorem}[О бесконтурном фактор-графе $\vec{G}/\sigma$]
+  Фактор-граф $\vec{G}/\sigma$ любого бесконтурного графа $\vec{G}$ также
+  является бесконтурным.
+\end{theorem}
+\begin{proof}
+  От противного. Пусть $\vec{G}$ --- бесконтурный граф, а в $\vec{G}/\sigma$
+  существует нетривиальный контур.
+  \begin{equation*}
+    \sigma(u_1) \to \sigma(u_2) \to \dots \to \sigma(u_k) \to \sigma(u_1),\,
+    k > 1
+  \end{equation*}
+
+  Так как существует дуга $(\sigma(u_1), \sigma(u_2)) \in \vec{G}/\sigma$, то
+  существуют представители соответствующих классов $u_1' \in \sigma(u_1),
+  u_2' \in \sigma(u_2), (u_1', u_2') \in \alpha$.
+
+  Но тогда всякий сток, достижимый из вершины $u_2'$ достижим и из вершины
+  $u_1'$. Поэтому $s(u_1') \supseteq s(u_2')$.
+
+  Так как $u_1'$ и $u_2'$ принадлежат разным классам отношения $\sigma$, то
+  $s(u_1') \neq s(u_2')$. Таким образом, $s(u_1') \supset s(u_2')$.
+
+  Продолжая рассуждения для остальных дуг контура и учитывая, что множество $s$
+  для всех вершин из одного класса равно, получаем:
+  \begin{equation*}
+    \underline{s(u_1')} \supset s(u_2') \supset \dots \supset s(u_k') \supset
+    \underline{s(u_1')}
+  \end{equation*}
+
+  Получаем, что не существует нетривиального контура в фактор-графе.
+\end{proof}
+
+\section{Проверяющий тест. Теорема о минимальном проверяющем тесте.}
+
+\begin{theorem}[О минимальных проверяющих тестах в системах с тождественным
+отношением $\sigma$]
+  Если бесконтурный граф $\vec{G}$ имеет тождественное отношение $\sigma$, то
+  минимальный проверяющий тест для системы, представленной графом $\vec{G}$,
+  также будет и локализующим (то есть он позволяет указать отказавшую вершину).
+\end{theorem}
+\begin{proof}
+  Пусть функциональная система $\Sigma$ такова, что $\vec{G}(\Sigma)$ является
+  бесконтурным, а $\sigma = \Delta$.
+
+  Это означает, что две вершины различны $u \neq v \iff s(u) \neq s(v)$. Так
+  как $\vec{G}(\Sigma)$ бесконтурный, то его конденсация с ним совпадает
+  $\vec{G} \cong \vec{G}/\varepsilon$.
+
+  Таким образом, минимальный проверяющий тест будет состоять из проверок всех
+  стоков системы. Пусть в результате проверки сигнал о неисправности поступил
+  из стоков $u_1, \dots, u_k$. В силу тождественности отношения $\sigma$
+  существует единственная вершина $v$, из которой достижимы эти стоки. По
+  условию сигнал о неисправности в системах такого вида наследуется, поэтому
+  результат тестирования может означать только одно --- вершина $v$ неисправна.
+\end{proof}
+
+\section{Полный бесконтурный граф. Теорема о полных бесконтурных графах.
+Характеризация входящих и выходящих деревьев.}
+
+\begin{definition}
+  Полный бесконтурный граф --- это такой рефлексивный бесконтурный граф, в
+  котором добавление любой дуги приводит к появлению нетривиального контура
+  (рефлексивный означает, что в каждой вершине есть петля).
+\end{definition}
+
+\begin{theorem}[О полных бесконтурный графах]
+  $\forall n \in \mathbb{N}$ существует единственный с точностью до изоморфизма
+  полный бесконтурный $n$-вершинный граф.
+\end{theorem}
+\begin{proof}
+  Пусть $\vec{G} = (V, \alpha)$ --- полный бесконтурный граф. По теореме
+  \ref{thm:correct-numbering} он имеет правильную нумерацию вершин.
+  $V = \set{v_1, \dots, v_n}$. $(v_i, v_j) \in \alpha \implies i \leq j$.
+
+  Пусть $\vec{H} = (U, \beta)$ --- другой полный бесконтурный граф с $n$
+  вершинами. Он также имеет правильную нумерацию.
+
+  Построим биекцию $\varphi : V \to U$ следующим образом: $\varphi(v_i) = u_i$.
+  Очевидно, что $\varphi$ --- биекция. При этом в силу полноты бесконтурных
+  графов $\vec{G}$ и $\vec{H}$ получаем:
+  \begin{equation*}
+    (v_i, v_j) \in \alpha \implies i \leq j \iff (u_i, u_j) \in \beta
+  \end{equation*}
+
+  Таким образом, $\varphi$ --- изоморфизм.
+\end{proof}
+
+Пусть $\vec{G} = (V, \alpha)$ --- полный бесконтурный граф. Тогда при правильной
+нумерации его вершин матрица смежности будет верхней треугольной матрицей. Любая
+Степень этой матрицы будет совпадать с ней самой $\implies D = A$.
+
+Так как $\vec{G}$ --- бесконтурный, то отношение достижимости $\delta$ является
+порядком. $(V, \delta)$ --- упорядоченное множество. Так как $D = A \implies
+\alpha = \delta \implies (V, \alpha)$ --- тоже упорядоченное множество.
+
+Отношение смежности транзитивно, то есть из любой цепи $u_1 \to u_2 \to \dots
+\to u_k,\, k > 0 \implies \exists (u_1, u_k) \in \alpha$.
+
+Таким образом, диаграмма упорядоченного множества $(V, \alpha)$ представляет
+собой цепь, в которой высота элемента равна количеству входящих в него дуг:
+$h(v) = |\alpha^{-1}(v)|$.
+
+Другое название полных бесконтурных графов --- транзитивные турниры.
+
+Другим важным классом бесконтурных графов являются ориентированные деревья.
+
+\begin{definition}
+  Диграф $\vec{T}$ называется выходящим деревом, если он удовлетворяет следующим
+  двум условиям:
+  \begin{enumerate}
+    \item Симметризация $T$ --- дерево,
+    \item
+      Существует корень, то есть вершина, из которой достижимы все остальные
+      вершины.
+  \end{enumerate}
+\end{definition}
+
+\begin{theorem}[Характеризация выходящих деревьев]
+  Антирефлексивный связный орграф $\vec{T}$ является выходящим деревом $\iff$ в
+  нём существует единственная вершина $v_0$ с нулевой степенью захода $(d^-(v_0)
+  = 0)$, а все остальные вершины $d^-(v) = 1, \forall v \neq v_0$.
+\end{theorem}
+\begin{proof}
+  \textbf{Необходимость.}
+
+  Пусть антирефлексивный связный орграф $\vec{T}$ является выходящим деревом.
+  По определению в нём есть корень $v_0$, из которого достижимы все остальные
+  вершины.
+
+  Пусть $d^-(v_0) > 0 \implies \exists v \neq v_0 : (v, v_0) \in \alpha$. Тогда
+  $v$ достижима из $v_0$, и $v_0$ достижима из $v$. Они взаимно достижимы
+  $\implies$ в $\vec{T}$ существует нетривиальный контур, а в его симметризации
+  --- цикл, что по определению невозможно $\implies d^-(v_0) = 0$.
+
+  Рассмотрим произвольную $v \neq v_0$. Так как вершина $v$ достижима из корня
+  $v_0$, то существует цепь $v_0 \to v_1 \to \dots \to v_k \to v$. $d^-(v) \geq
+  1$. Пусть $d^-(v) \geq 2$.
+
+  Тогда найдутся две вершины $v_1$ и $v_2$ : $(v_1, v) \in \alpha, (v_2, v) \in
+  \alpha$. Так как $v_1$ и $v_2$ достижимы из $v_0$, то получаем, что существуют
+  два различных пути из $v_0$ в $v$.
+
+  Тогда в симметризации найдутся две различных цепи между $v_0$ и $v$, что
+  невозможно. Таким образом, $d^-(v) = 1, v \neq v_0$.
+
+  \textbf{Достаточность.}
+
+  Пусть в связном антирефлексивном орграфе $\vec{T}$ существует единственная
+  вершина $v_0$, ($d^-(v_0) = 0$), а у всех остальных вершин $d^-(v) = 1$.
+
+  Так как $\vec{T}$ связный, то и его симметризация $T$ --- связный граф. То
+  есть между вершиной $v_0$ и произвольной вершиной $v$ существует связывающая
+  их цепь $P$.
+
+  Пронумеруем вершины этой цепи в порядке прохождения от $v_0$ к $v$:
+  $v_0 v_1 v_2 \dots v_k v$.
+
+  Возвращаемся к орграфу $\vec{T}$. Так как $d^-(v_0) = 0$, то ребро $\set{v_0,
+  v_1}$ из $T$ в орграфе $\vec{T}$ может быть ориентированно только так: $(v_0,
+  v_1)$.
+
+  Так как $d^-(v_1) = 1$ и есть дуга $(v_0, v_1)$, то ребро $\set{v_1, v_2}$
+  может быть ориентированно только $(v_1, v_2)$.
+
+  Продолжая рассуждения, получим, что все рёбра цепи $P$ в орграфе $\vec{T}$
+  ориентированы от $v_0$ к $v$. Таким образом, в $\vec{T}$ существует
+  ориентация цепи из $v_0$ в $v$. То есть $v_0$ --- корень $\vec{T}$.
+
+  Покажем, что симметризация $T$ --- дерево. Достаточно показать, что из $v_0$
+  в $v$ существует единственная цепь. Предположим, что это не так и из вершины
+  $v_0$ в произвольную $v \neq v_0$ кроме $P$ существует ещё и цепь $P^*: v_0,
+  u_1, u_2, \dots, u_l, v$. Аналогично получим из $P^*$ ориентированную цепь в
+  орграфе $\vec{T}$.
+
+  Пусть $v_s$ --- последняя вершина в порядке прохождения цепи $P$ от её конца,
+  которая также есть и в $P^*$. Тогда в $v_s$ входит две дуги, $d^-(v_s) \geq
+  2$, что невозможно $\implies$ $T$ --- дерево, $\vec{T}$ --- выходящее дерево.
+\end{proof}
+
+\begin{definition}
+  Если $\vec{T}$ --- выходящее дерево, то обратив его дуги получим
+  $\vec{T}^{-1}$ --- входящее дерево (симметризация входящего дерево будет
+  являться деревом, из любой вершины достижима $v_0$).
+\end{definition}
+
+\begin{theorem}[Характеризация входящих деревьев]
+  Антирефлексивный связный орграф $\vec{T}$ является входящим деревом $\iff$ в
+  нём существует единственная вершина $v_0$ ($d^+(v_0) = 0$), а все остальные
+  вершины $d^+(v) = 1, v \neq v_0$.
+\end{theorem}
+
+Во входящих деревьях вершина $v_0$ также называется корнем.
+
+\section{Турниры. Теорема о лидере. Теорема о гамильтоновой цепи.}
+
+\begin{definition}
+  Турнир --- полный направленный граф, то есть такой граф, в котором между
+  любыми двумя вершинами существует единственная дуга.
+\end{definition}
+
+\begin{enumerate}
+  \item Полный бесконтурный граф является турниром (транзитивным);
+  \item
+    Пусть проводится круговой турнир в игре без ничьих (каждая команда играет с
+    каждой один раз). Сопоставив командам вершины, исходящую дугу, направление
+    которой ставится от победителя к проигравшему, получим турнир (без петель).
+
+    Иногда определение турнира даётся следующим образом: турнир --- полный
+    направленный граф без петель.
+  \item
+    Пусть $K_n$ --- полный неориентированный граф. Ориентируем произвольным
+    образом каждое ребро $K_n$. Получим турнир без петель. Таким образом, можно
+    получить все турниры с заданным числом вершин. $K_n: m = \frac{n(n - 1}{2})$
+    (всего $2^m$, оставить неизоморфные).
+\end{enumerate}
+
+Заметим, что любой максимальный подграф турнира также является турниром. С
+учётом этого можно предложить динамический алгоритм построения турнира с
+заданным числом вершин.
+
+Рассмотрим $(n - 1)$-вершинный турнир $T_{n - 1}$. Добавим к нему одну вершину
+и соединим её $(n - 1)$ рёбрами с вершинами $T_{n - 1}$. Для получения всех
+турниров с числом вершин $n$, для которых $T_{n - 1}$ --- максимальный подграф
+потребуется перебрать $2^{n - 1}$ вариантов ориентации добавленных рёбер.
+
+\begin{theorem}[О лидере]
+  Пусть $v_0$ --- одна из вершин турнира, имеющая максимальную степень исхода
+  (лидер). Тогда расстояние от $v_0$ до любой другой вершины равно 1 или 2.
+\end{theorem}
+\begin{proof}
+  Пусть $v_0$ --- лидер. То есть $d^+(v_0) \geq d^+(v), \forall v \in V$.
+
+  Доказательство методом от противного.
+
+  Пусть в турнире $T$ существует вершина $v$, расстояние от $v_0$ до неё
+  $d(v_0, v) > 2$. Имеем дугу $(v, v_0)$. Кроме этого не существует пути длины
+  2 из $v_0$ к $v$.
+
+  Пусть $u$ --- произвольная вершина турнира, в которую идёт дуга из $v_0$. Если
+  бы существовала дуга $(u, v) \in \alpha$, то получили бы путь длины 2 из $v_0$
+  в $v$. $(v, u) \in \alpha$. Таким образом, если из вершины $v_0$ идёт дуга в
+  некоторую вершину $u$, то и из $v$ в $u$ тоже идёт дуга. Кроме того, из $v$
+  идёт дуга в вершину $v_0$.
+
+  Тогда получаем, что степень исходов вершины $d^+(v) > d^+(v_0)$, что
+  противоречит определению лидера.
+\end{proof}
+
+\begin{theorem}[О гамильтоновой цепи]
+  В любом турнире с числом вершин $n \geq 2$ существует гамильтонова цепь.
+\end{theorem}
+\begin{proof}
+  ММИ по числу вершин.
+
+  Предположим, что теорема справедлива для всех турниров с числом вершин $k$.
+  Рассмотрим $(k + 1)$-вершинный турнир $\vec{T}$. $v_1 v_2 \dots v_k
+  v_{k + 1}$.
+
+  Удалим из $\vec{T}$ вершину $v_{k + 1}$ со всеми её дугами. Максимальный
+  подграф $\vec{T} - v_{k + 1}$ является турниром и имеет $k$ вершин $\implies$
+  в нём существует гамильтонова цепь.
+
+  Не нарушая общности, будем считать, что нумерация вершин соответствует их
+  порядку в прохождении цепи. $v_1 \to \dots \to v_{k - 1} \to v_k$ в
+  подграфе $\vec{T} - v_{k + 1}$. Вернёмся к турниру $\vec{T}$. Рассмотрим
+  три возможных случая:
+  \begin{enumerate}
+    \item
+      $(v_{k + 1}, v_1) \in \alpha)$. $v_{k + 1}, v_1, \dots, v_k$ ---
+      гамильтонова цепь.
+      \begin{center}
+        \includegraphics[width=0.3\textwidth]{lec14-hamilton1}
+      \end{center}
+    \item
+      $(v_k, v_{k + 1}) \in \alpha)$. Очевидно, $v_1, \dots, v_k, v_{k + 1}$
+      --- гамильтонова цепь.
+      \begin{center}
+        \includegraphics[width=0.3\textwidth]{lec14-hamilton2}
+      \end{center}
+    \item
+      $(v_{k + 1}, v_1) \not\in \alpha$ и $(v_k, v_{k + 1}) \not\in \alpha$. В
+      силу полноты $(v_1, v_{k + 1}) \in \alpha, (v_{k + 1}, v_k) \in \alpha$.
+      \begin{center}
+        \includegraphics[width=0.3\textwidth]{lec14-hamilton3}
+      \end{center}
+
+      Последовательно просматриваем вершины от $v_1$ до $v_k$ в поиске первой
+      вершины $v_i : (v_{k + 1}, v_i) \in \alpha$. Тогда получаем гамильтонову
+      цепь $v_1, \dots, v_{i - 1}, v_{k + 1}, v_i, \dots v_k$.
+      \begin{center}
+        \includegraphics[width=0.3\textwidth]{lec14-hamilton4}
+      \end{center}
+  \end{enumerate}
+\end{proof}
+
+\section{Сильный турнир. Теорема о контурах сильно связных турниров. Следствие
+(гамильтоновы турниры).}
+
+\begin{definition}
+  Турнир $T$ называется сильным, если он является сильно связным орграфом, то
+  есть любые две вершины в нём взаимно достижимы.
+\end{definition}
+
+\begin{theorem}[О контурах сильно связных турниров]
+  В любом сильном турнире с числом вершин $n \geq 3$ каково бы ни было
+  натуральное число $k \leq n \quad (k \geq 3)$ через любую вершину проходит
+  некоторый контур длины $k$.
+\end{theorem}
+\begin{proof}
+  Пусть $\vec{T}$ --- сильный турнир, $v_1$ --- произвольная вершина. В сильных
+  турнирах нет источников и стоков, поэтому существует по крайней мере одна
+  дуга входящая и одна выходящая в/из $v_1$.
+
+  Пусть $(v_1, v_2) \in \alpha$. Продолжим путь от $(v_1, v_2)$. $v_1 v_2 v_3
+  \dots v_l v_1$, так как турнир сильный. Так как $(v_1, v_2) \in \alpha,
+  (v_l, v_1) \in \alpha$, то пусть $v_i$ --- первая вершина среди вершин $v_2
+  \dots v_l$, в которой $(v_i, v_1) \in \alpha$.
+
+  Таким образом мы имеем контур длины 3, проходящий через $v_1$: $v_1, v_{i -
+  1}, v_i$.
+  \begin{center}
+    \includegraphics[width=0.3\textwidth]{lec14-strong1}
+  \end{center}
+
+  Таким образом, в любом сильном турнире с числом вершин $n \geq 3$ через
+  любую вершину проходит контур длины 3.
+
+  ММИ. Пусть в сильном турнире существует контур длины $k \geq 3$, проходящий
+  через произвольную вершину $v_1$. Докажем, что в этом случае через неё
+  проходит контур длины $(k + 1)$.
+
+  Два случая:
+  \begin{enumerate}
+    \item
+      В $\vec{T}$ существует вершина $v$ не принадлежащая контуру: $(v_i, v) \in
+      \alpha, (v, v_j) \in \alpha$. Не нарушая общности будем считать, что $i <
+      j$. Повторяя рассуждения, найдём между $v_i$ и $v_j$ вершину $v_s$ первую,
+      в которой дуга $(v, v_s) \in \alpha$. Получаем контур длины $(k + 1)$:
+      $v_1, \dots, v_{s - 1}, v, v_s, \dots, v_k, v_1$.
+      \begin{center}
+        \includegraphics[width=0.3\textwidth]{lec14-strong2}
+      \end{center}
+    \item
+      Предположим, что ни одной такой вершины $v$, как в случае 1, в $\vec{T}$
+      нет. То есть для произвольной вершины $v$ дуги идут либо во все вершины
+      контура, либо от вершин контура к $v$.
+
+      Будем говорить о вершинах I-го и II-го типов. Соберём эти вершины в
+      подмножества.
+      \begin{center}
+        \includegraphics[width=0.5\textwidth]{lec14-strong3}
+      \end{center}
+
+      Легко заметить, что множества вершин I и II типов не пусты. В самом деле,
+      если бы $V_I = \emptyset$, то из вершин II типа мы не смогли бы попасть в
+      вершины контура, а это противоречит тому, что турнир сильный. Аналогично,
+      если $V_{II} = \emptyset$.
+
+      Утверждается, что существуют $u_1 \in V_I$ и $u_0 \in V_{II}$ такие, что
+      $(u_0, u_1) \in \alpha$. Действительно, если бы таких не было, то было бы
+      невозможно попасть из вершин II в I. Тогда в турнире $\vec{T}$ строим
+      контур длины $(k + 1)$: $u_0, u_1, v_1, v_2, \dots, v_{k - 1}, u_0$.
+
+      Таким образом, мы построили контур длины $(k + 1)$.
+      \begin{center}
+        \includegraphics[width=0.5\textwidth]{lec14-strong3}
+      \end{center}
+  \end{enumerate}
+\end{proof}
+
+\begin{corollary}
+  Турнир является гамильтоновым $\iff$ он сильно связный, то есть только сильные
+  турниры являются гамильтоновыми.
+\end{corollary}
+
+\section{Теорема о МРP турнира. Теорема о МВP транзитивного турнира.}
+
+Рассмотренные ранее понятия вершинного и рёберного расширения сохраняют свой
+смысл и для орграфов.
+
+\begin{theorem}[МРР турнира]
+  Любой $n$-вершинный турнир $\vec{T_n}$ (с петлями или без) имеет единственное
+  с точностью до изоморфизма минимальное рёберное 1-расширение $\vec{K_n}$.
+  При $k > 1$ турниры не имеют минимальных рёберных расширений.
+\end{theorem}
+\begin{proof}
+  Убедимся, что $\vec{K_n}$ является рёберным 1-расширением $\vec{T_n}$.
+  Удалим из орграфа $\vec{K_n}$ произвольную дугу $(v_1, v_2)$.
+
+  Тогда в получившемся орграфе между вершинами $v_1$ и $v_2$ останется
+  единственная дуга $(v_2, v_1)$.
+
+  Выберем в турнире $\vec{T_n}$ две произвольные вершины $u_1$ и $u_2$:
+  $(u_2, u_1) \in \alpha$.
+
+  Очевидно, что биекция $u_1, u_2, \dots u_n \to v_1, v_2, \dots v_n$ является
+  вложением.
+
+  Пусть $n$-вершинный орграф $\vec{G}$, отличный от полного, является
+  минимальным рёберным 1-расширением $\vec{T_n}$.
+
+  Тогда в $\vec{G}$ можно найти $(u_1, u_2) \not\in \alpha$. Тогда $(\vec{G} -
+  (u_2, u_1))$ $u_1$ и $u_2$ не соединены дугой ни в каком направлении.
+
+  Очевидно, что $\vec{T_n}$ не может вкладываться в получившийся орграф.
+
+  Рассмотрим $k > 1$. Выбрав две произвольные вершины, между которыми есть
+  пара встречных дуг, рассмотрим граф, получающийся после их удаления и
+  удаления произвольных $(k - 2)$ других дуг.
+
+  В этом графе будет пара вершин, между которыми не будет дуг. Очевидно, что
+  турнир в такой граф вкладываться не может.
+\end{proof}
+
+\begin{theorem}[О минимальном вершинном $k$-расширении транзитивного турнира]
+  Транзитивный турнир $\vec{T_n}$ при $n > 2$ имеет единственное минимальное
+  вершинное $k$-расширение при $\forall k \in \mathbb{N}$, которое является
+  $\vec{T_{n + k}}$.
+\end{theorem}
+\begin{proof}
+  Убедимся, что $\vec{T_{n + k}}$ является $k$-расширением для $\vec{T_n}$.
+  Удаление $k$ вершин из $\vec{T_{n + k}}$ приведёт к удалению соответствующих
+  строк и столбцов из матрицы смежности. Очевидно, что в результате мы получим
+  матрицу смежности турнира $\vec{T_n}$.
+
+  \textbf{Докажем минимальность.}
+
+  Пусть существует минимальное вершинное $k$-расширение турнира $\vec{T_n}$ c
+  меньшим числом дуг, чем $\vec{T_{n + k}}(\vec{G}^*)$. $\vec{G}^*$ не является
+  турниром, так как число дуг меньше $\implies$ в $\vec{G}^*$ существует как
+  минимум две вершины $v_1$ и $v_2$, между которыми нет дуг.
+
+  Рассмотрим граф, получающийся из $\vec{G}^*$ удалением любых $k$ вершин,
+  кроме $v_1$ и $v_2$. Очевидно, что в получившийся граф нельзя вложить
+  $\vec{T_n}$.
+
+  \textbf{Докажем единственность.}
+
+  Предположим, что существует ещё одно МВ-kР $\vec{T_n}$, отличное от
+  $\vec{T_{n + k}}$. Обозначим его $\vec{G}^*$.
+
+  По рассмотренному ранее $\vec{G}^*$ будет турниром, но нетранзитивным
+  $\implies$ в нём существует как минимум один нетривиальный контур.
+
+  Рассмотрим граф, получающийся из $\vec{G}^*$ удалением $k$ вершин, не
+  входящих в этот контур. Любой подграф турнира тоже турнир, а в получившемся
+  графе есть нетривиальный контур $\implies$ этот турнир не изоморфен
+  транзитивному.
+\end{proof}
+
+\begin{remark}
+  При $n = 2$, $\vec{T_2}$ имеет два неизоморфных МВ-1Р. При $k > 1$, любой
+  $\vec{T_{k + 2}}$ является МВ-kР турнира $\vec{T_2}$.
+\end{remark}
+
+\begin{remark}
+  Минимальное вершинное $k$-расширение транзитивного $\vec{T_n}$ является и его
+  точным вершинным $k$-расширением.
+\end{remark}
+
 \section{Раскраски графов. Критерий двудольности. Теорема о 5 красках}
 
 \begin{definition} \label{def:coloring}