path: root/graphs-exam/graphs-exam.tex

\documentclass[a4paper,oneside,12pt]{extbook}

\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}
\usepackage[
  left=2cm,right=2cm,
  top=2.5cm,bottom=2.5cm
]{geometry}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{braket} % \set
\usepackage{hyperref}
\usepackage{graphicx}
\graphicspath{ {./images/} }

\renewcommand{\emptyset}{\varnothing}
\renewcommand{\qedsymbol}{$\blacksquare$}
\newcommand{\link}{\hyperref}
\newcommand{\ds}{\displaystyle}

\input{style.tex}

\title{Теория графов}
\date{\the\year}

\begin{document}

\maketitle

\tableofcontents

\chapter*{Введение}

\section{Декартово произведение. Бинарные отношения. Пустое и универсальное
отношения. Операции над отношениями: пересечение, объединение, дополнение,
обращение, умножение.}

\begin{definition}
  Пусть $A$, $B$ --- два непустых множества. Декартовым произведением $A$ и $B$
  называется множество $A \times B = \set{(a, b) : a \in A,\, b \in B}$
  \label{def:decart-cross}
\end{definition}

\begin{definition}
  Бинарным отношением между множествами A и B называется всякое подмножество
  $A \times B$. $\rho \subseteq A \times B$.
  \label{def:bin-rel}
\end{definition}

\begin{definition}
  Пустое отношение --- это отношение, не содержащее ни одной пары. Обозначение:
  $\emptyset$.
  \label{def:empty-set}
\end{definition}

\begin{definition}
  Универсальное отношение содержит все возможные упорядоченные пары.
  $\forall \rho: \emptyset \subseteq \rho \subseteq A \times B$.
  \label{def:universal-set}
\end{definition}

\begin{definition}[Операции над отношениями]
  Пусть $\rho, \sigma \subseteq A \times B$.
  \begin{enumerate}
    \item
      Пересечение: $\rho \cap \sigma = \set{(a, b) \in A \times B : (a, b) \in
      \rho \land (a, b) \in \sigma}$
    \item
      Объединение: $\rho \cap \sigma = \set{(a, b) \in A \times B : (a, b) \in
      \rho \lor (a, b) \in \sigma}$
    \item
      Дополнение: $\overline{\rho} = \set{(a, b) \in A \times B : (a, b) \not\in
      \rho}$
    \item
      Обращение: $\rho^{-1} \subseteq B \times A,\, \rho^{-1} = \set{(b, a) \in
      B \times A : (a, b) \in \rho}$
    \item
      Умножение. Пусть $\rho \subseteq A \times B,\, \sigma \subseteq B \times
      C$. Тогда $\rho \circ \sigma \subseteq A \times C,\, \rho \circ \sigma =
      \set{(a, c) \in A \times C : (\exists b \in B) (a, b) \in \rho \land (b,
      c) \in \sigma}$.
  \end{enumerate}
  \label{def:rel-op}
\end{definition}


\section{Операции над матрицами: пересечение, сложение, дополнение,
транспонирование, умножение. Связь между операциями над матрицами и
отношениями.}

\begin{definition}[Операции над матрицами]
  $M(m, n)$ --- множество всех двоичных булевых матриц размерности $m \times n$.
  Пусть $M, N \in M(m, n)$.

  \begin{enumerate}
    \item Пересечение: $M \land N : (M \land N)_{ij} = M_{ij} \cdot N_{ij}$
    \item Сложение: $M + N : (M + N)_{ij} = M_{ij} + N_{ij}$
    \item Дополнение: $M' : (M')_{ij} = (M_{ij})'$
    \item Транспонирование: $M^T \in M(n, m),\, (M^T)_{ij} = M_{ji}$
    \item
      Умножение $M \in M(m, n),\, N \in M(n, p)$: $MN \in M(m, p),\,
      (MN)_{ik} = \sum_{j = 1}^n M_{ij} N_{jk}$
  \end{enumerate}
  \label{def:mat-op}
\end{definition}

\begin{theorem}[Связь между операциями над отношениями и их матрицами]
  Пусть $\rho, \sigma \in A \times B (|A| = m, |B| = n)$. Тогда
  \begin{enumerate}
    \item $M(\rho \cap \sigma) = M(\rho) \land M(\sigma)$
    \item $M(\rho \cup \sigma) = M(\rho) + M(\sigma)$
    \item $M(\overline\rho) = (M(\rho))'$
    \item $M(\rho^{-1}) = (M(\rho))^T$
    \item
      $\rho \subseteq A \times B,\, \sigma \subseteq B \times C : M(\rho \circ
      \sigma) = M(\rho) M(\sigma)$
  \end{enumerate}
  \label{def:mat-rel-op}
\end{theorem}


\section{Срез отношения через элемент и через множество. Тождественное
отношение. Классификация отношений: рефлексивность, антирефлексивность,
симметричность, антисимметричность. Отношение эквивалентности, отношение
порядка.}

\begin{definition}
  Срезом отношения $\rho \subseteq A \times B$ через элемент $a \in A$
  называется множество $\rho(a) = \set{b \in B : (a, b) \in \rho} \subseteq B$.
  \label{def:slice-elem}
\end{definition}

\begin{definition}
  Срезом отношения $\rho \subseteq A \times B$ через подмножество $X \subseteq
  A$ называется множество $\rho(a) = \ds\bigcup_{a \in X} \rho(a) \subseteq B$.
  \label{def:slice-set}
\end{definition}

\begin{definition}
  Отношения между элементами одного и того же множества называются отношениями
  на множестве $A$. $\rho \subseteq A \times A$.
  \label{def:self-rel}
\end{definition}

\begin{definition}
  Тождественное отношение на множестве $A$ обозначается $\Delta \subseteq A
  \times A$.
  \begin{align*}
    (x, y) \in \Delta &\iff x = y \\
    M(\Delta) = E&,\, E = \begin{cases}
      0, &i \neq j \\
      1, &i = j
    \end{cases}
  \end{align*}
  \label{def:identity-rel}
\end{definition}

\begin{definition}[Классификация отношений]
  \begin{enumerate}
    \item
      Отношение $\rho \subseteq A \times A$ называется рефлексивным $(\forall x
      \in A) ((x, x) \in \rho)$. В матрице отношения элементы главной диагонали
      равны 1.
    \item
      Отношение $\rho \subseteq A \times A$ называется рефлексивным $(\forall
      x \in A) ((x, x) \not\in \rho)$. В матрице отношения элементы главной
      диагонали равны 0.
    \item
      Отношение $\rho \subseteq A \times A$ симметрично $\iff (\forall x, y
      \in A) ((x, y) \in \rho \implies (y, x) \in \rho)$. Матрица отношения
      симметрична относительно главной диагонали.
    \item
      Отношение $\rho \subseteq A \times A$ антисимметрично $\iff (\forall x,
      y \in A) ((x, y) \in \rho \land (y, x) \in \rho) \implies (x = y)$. В
      матрице отношения элементы, симметричные единицам относительно главной
      диагонали, равны нулю (исключение --- сама главная диагональ).
    \item
      Отношение $\rho \subseteq A \times A$ транзитивно $\iff (\forall x, y, z
      \in A) ((x, y) \in \rho \land (y, z) \in \rho \implies (x, z) \in \rho)$.
  \end{enumerate}
  \label{def:rel-classification}
\end{definition}

\begin{definition}
  Отношением эквивалентности на $A$ называется отношение $\varepsilon \subseteq
  A \times A$, которое одновременно рефлексивно, симметрично и транзитивно.
  \label{def:equivalence}
\end{definition}

\begin{definition}
  Отношение $\omega \subseteq A \times A$ называется отношением порядка, если
  оно рефлексивно, антисимметрично и транзитивно.
  \label{def:order}
\end{definition}


\chapter{Основные алгебраические конструкции для графов}


\section{Типы графов: ориентированные графы, неориентированные графы, диграфы,
полные графы, вполне несвязные графы. Симметризация.}

\begin{definition}
  Орграфом $\vec{G} = (V, \alpha)$, где $V$ --- конечное непустое множество, а
  $\alpha \subseteq V \times V$. Элементы множества $V$ называются вершинами, а
  элементы множества $\alpha$ --- дугами. $V$ --- множество вершин, $\alpha$
  --- отношение смежности.
  \label{def:orgraph}
\end{definition}

$(u, v) \in \alpha$ --- значит из $u$ в $v$ есть дуга. Если $u = v$, то есть
$(u, u) \in \alpha$, то дуга называется петлёй. Говорят, что дуга $(u, v)$
инцидентна вершинам $u$ и $v$, то есть своим концам.

\begin{definition}
  Говорят, что $\vec{G} = (U, \alpha)$ изоморфен $\vec{H} = (V, \beta)$, если
  существует биекция $\varphi : U \to V$, которая сохраняет отношение смежности:
  $(\forall u_1, u_2 \in U) ((u_1, u_2) \in \alpha \iff (\varphi(u_1),
  \varphi(u_2)) \in \beta$.
  \label{def:isomorphism}
\end{definition}

\begin{definition}
  Граф $G = (V, \alpha)$ называется неориентированным (или просто графом), если
  отношение смежности $\alpha$ антирефлексивно и симметрично. Нет петель, дуги
  встречаются парами. $(u, v), (v, u)$ --- ребро, обозначается $\set{u, v}$.
  \label{def:graph}
\end{definition}

\begin{definition}
  Каждому орграфу $\vec{G} = (V, \alpha)$ естественным образом можно сопоставить
  неориентированный граф, который называется его симметризацией. Это граф $(V,
  (\alpha \cup \alpha^{-1}) \backslash \Delta)$, то есть дуги заменяются рёбрами
  и исключаются петли.
  \label{def:symmetrization}
\end{definition}

\begin{definition}
  Орграф $\vec{G} = (V, \alpha)$ называется направленным графом или диграфом,
  если его отношение смежности антисимметрично (то есть в диграфе нет встречных
  дуг, за исключением быть может петель).
  \label{def:digraph}
\end{definition}

\begin{definition}
  Орграф $\vec{G} = (V, \alpha)$ называется полным, если его отношение смежности
  универсально, то есть $\alpha = V \times V$. Если число вершин орграфа равно
  $n$, то полный орграф обозначают $\vec{K_n}$.
  \label{def:full-orgraph}
\end{definition}

\begin{definition}
  Неориентированный граф называется полным, если его отношение смежности $\alpha$
  имеет вид $(V \times V) \backslash \Delta$. Обозначается $K_n$.
  \label{def:full-graph}
\end{definition}

\begin{definition}
  Орграф $\vec{G} = (V, \alpha)$ называется вполне несвязным (нуль-графом), если
  его отношение смежности пусто. Обозначается $0_n$.
  \label{def:null-graph}
  \label{def:fully-disconnected}
\end{definition}

Очевидно, что для каждого $n$ существует единственный граф $K_n$, $\vec{K_n}$,
$0_n$.

\begin{definition}
  Диграф $\vec{G}$ называется полным, если в каждой вершине имеется петля и
  между двумя различными вершинами существует единственная дуга. Полный диграф
  называется турниром.
  \label{def:full-digraph}
  \label{def:tournament}
\end{definition}

\section{Степени вершин. Спецификация.}

\begin{definition}
  Степенью исхода вершины $v$ называется число $d^+$, равное количеству дуг в
  $\vec{G}$, имеющих $v$ своим началом. $d^+(v) = |\alpha(v)|$.
  \label{def:out-degree}
\end{definition}

\begin{definition}
  Степенью захода вершины $v$ называется число $d^-$, равное количеству дуг в
  $\vec{G}$, имеющих $v$ своим концом. $d^-(v) = |\alpha^{-1}(v)|$.
  \label{def:in-degree}
\end{definition}

\begin{definition}
  Спецификацией орграфа называется вектор вида $\left(v_1^{(d_1^+, d_1^-)},
  \dots, v_n^{(d_n^+, d_n^-)}\right)$, где $d_i^+ = d^+(v_i)$, $d_i^- =
  d^-(v_i)$.
  \label{def:specification}
\end{definition}

Для неориентированного графа степени исхода и захода равны. $d(v)$ называется
просто степенью вершины. $d(v)$ --- количество рёбер, которым принадлежит
вершина $v$.

\section{Двудольные графы. Звёзды.}

\begin{definition}
  Граф называется двудольным, если его множество вершин может быть разбито на
  два подмножества $V_1$ и $V_2$. $V = V_1 \cup V_2$, $V_1 \cap V_2 = \emptyset$
  и для любого ребра $\set{u, v}$ (или дуги $(u, v)$) $u$ и $v$ принадлежат
  различным множествам.
  \label{def:bipartite}
\end{definition}

\begin{definition}
  Двудольный граф, который содержит все возможные рёбра, отвечающие этому
  условию, называется полным двудольным графом. И обозначается $K_{m,n}$, где
  $n$ и $m$ --- количество вершин $n = |V_1|$, $m = |V_2|$.
  \label{def:full-bipartite}
\end{definition}

\begin{definition}
  Полный двудольный граф вида $K_{1,n}$ называется звездным графом или звездой.
  \label{def:star}
\end{definition}

\section{Операции над графами: дополнение, объединение, соединение, декартово
произведение, тензорное произведение, сильное произведение. n-мерная решетка,
n-мерный тор.}

\begin{definition}[Операции над графами]
  Пусть $G = (V, \alpha)$ --- некоторый неориентированный граф.
  \begin{enumerate}
    \item
      Дополнение: $G = (V, \alpha) \to G' = (V, \overline\alpha \backslash
      \Delta)$
    \item
      Объединение: $G_1 = (V_1, \alpha_1)$, $G_2 = (V_2, \alpha_2)$, $G_1 \cup
      G_2 = G = (V_1 \cup V_2, \alpha_1 \cup \alpha_2)$.
    \item
      Соединение: $G_1 = (V_1, \alpha_1)$ и $G_2 = (V_2, \alpha_2)$, $V_1 \cap
      V_2 = \emptyset$, $G_1 + G_2 = (V_1 \cup V_2, \alpha_1 \cup \alpha_2 \cup
      (V_1 \times V_2) \cup (V_2 \times V_1)$.
    \item
      Декартовым или прямым произведением двух графов $G_1 = (U, \alpha_1)$ и
      $G_2 = (V, \alpha_2)$ называется граф $G_1 \cdot G_2$ с множеством вершин
      $U \times V$, в котором вершины $(u_1, v_1)$ и $(u_2, v_2)$ смежны тогда и
      только тогда, когда либо $u_1 = u_2$, а $v_1$ смежна с $v_2$, либо $v_1 =
      v_2$, а $u_1$ смежна с $u_2$.
    \item
      Тензорным произведением двух графов $G_1 = (U, \alpha_1)$ и $G_2 = (V,
      \alpha_2)$ называется граф $G_1 \times G_2$ с множеством вершин $U \times
      V$, в котором различные вершины $(u_1, v_1)$ и $(u_2, v_2)$ смежны
      тогда и только тогда, когда смежны $u_1$ и $u_2$ и $v_1$ с $v_2$:
      $(u_1, u_2) \in \alpha_1 \land (v_1, v_2) \in \alpha_2$.
    \item
      Сильным произведением двух графов $G_1 = (U, \alpha_1)$ и $G_2 = (V,
      \alpha_2)$ называется граф $G_1 \times G_2$ с множеством вершин $U \times
      V$, в котором различные вершины $(u_1, v_1)$ и $(u_2, v_2)$ смежны тогда
      и только тогда, когда выполняется одно из трёх условий:
      \begin{enumerate}
        \item
          смежны $u_1$ с $u_2$ и $v_1$ с $v_2$ : $(u_1, u_2) \in \alpha_1
          \land (v_1, v_2) \in \alpha_2$ (как в тензорном);
        \item
          $u_1 = u_2$, а $v_1$ смежна с $v_2$: $(v_1, v_2) \in \alpha_2$
          (как в декартовом);
        \item
          $v_1 = v_2$, а $u_1$ смежна с $u_2$: $(u_1, u_2) \in \alpha_1$
          (как в декартовом);
      \end{enumerate}

      Сильное произведение является объединением тензорного и декартова
      произведений.
  \end{enumerate}
\end{definition}

\begin{definition}
  $n$-мерной решёткой называется граф, являющийся декартовым произведением $n$
  цепей.
  \label{def:mesh-graph}
\end{definition}

\begin{definition}
  $n$-мерным тором называется граф, являющийся декартовым произведением $n$
  циклов.
  \label{def:torus-graph}
\end{definition}

\section{Теорема Эйлера о степенях вершин. Однородные графы.}

Пусть $G = (V, \alpha)$ --- неориентированный граф. Вершина $v \in V$ называется
чётное или нечётное в зависимости от чётности её степени.

\begin{theorem}[Эйлера, о степенях вершин]
  Пусть $G = (V, \alpha)$ --- неориентированный граф с $n$ вершинами и $m$
  рёбрами. Тогда справедливы следующие три утверждения:
  \begin{enumerate}
    \item $\ds\sum_{i = 1}^n d(v_i) = 2m$;
    \item Количество нечётных вершин чётно;
    \item Сущестует по крайней мере две вершины с одинаковой степенью.
  \end{enumerate}
  \label{thm:euler}
\end{theorem}
\begin{proof}
  \begin{enumerate}
    \item
      $\set{u, v}$ --- ребро в $G$. Это ребро один раз будет учитываться в
      $d(u)$ и один раз в $d(v)$, таким образом, в сумме степеней вершин каждое
      ребро будет учитываться дважды;
    \item
      $\ds 2m = \sum_{i = 1}^n d(v_i) = \sum d(v_i)_\text{чёт} + \sum
      d(v_i)_\text{нечёт}$

      Так как $2m$ --- чётное, то сумма чётных степеней и нечётных степеней
      также должна быть чётной. Такое может быть только если сумма нечётных
      степеней --- чётное число, то есть нечётных вершин чётное число.
    \item
      Вершина $v$ называется изолированной, если её степень равна 0, то есть она
      не смежна ни с одной другой вершиной. Вершина $u$ называется полной, если
      она смежна со всеми вершинами.

      Таким образом, степень произвольной вершины в графе $0 \leq d(v) \leq n -
      1$. Заметим, что одновременно в графе не может быть полной и изолированной
      вершин.
  \end{enumerate}
\end{proof}

\begin{definition}
  Однородные (регулярные) графы --- это графы, у которых степени всех вершин
  одинаковые. Обозначаются через $R_{n,p}$, где $p$ --- порядок, $n$ --- число
  вершин.
  \label{def:regular-graph}
\end{definition}

\section{Степенное множество. Теорема о степенном множестве.}

\begin{definition}
  Степенным множеством графа называется множество чисел, являющихся степенями
  его вершин.
  \label{def:degree-set}
\end{definition}

\begin{theorem}[О стененном множестве, Капур, Полимени, Уолл]
  Для любого множества натуральных чисел $A = \set{d_1, \dots, d_k}$ ($d_1 < d_2
  < \dots < d_k$ для удобства) существует граф с $(d_k + 1)$ вершинами, для
  которых $A$ является степенным множеством.
  \label{thm:degree-set}
\end{theorem}
\begin{proof}
  Доказательство по ММИ.
  \begin{enumerate}
    \item
      $k = 1, A = \set{d}$. Граф $K_{d + 1}$. В полном $(d + 1)$ вершинном графе
      каждая вершина соединена с остальными, таким образом число вершин $d + 1$,
      их степень --- $d$.
    \item
      $k = 2, A = \set{d_1, d_2}, d_1 < d_2$. Рассмотрим граф $G = K_{d_1} +
      0_{d_2 - d_1 + 1}$. $d(u) = (d_1 - 1) + (d_2 - d_1 + 1) = d_2$, $d(v) =
      d_1$. Количество вершин: $d_2 - d_1 + 1 + d_1 = d_2 + 1$.
    \item
      Пусть верно для $k$. Докажем для $k + 1$.
      \begin{align*}
        A &= \set{d_1, \dots, d_k, d_{k + 1}} \quad d_1 < \dots < d_k < d_{k + 1} \\
        A^* &= \set{d_2 - d_1, \dots, d_k - d_1} \implies |A^*| = k - 1
      \end{align*}

      Существует граф $G_0$ с $d_k - d_1 + 1$ вершинами, для которого $A^*$ ---
      степенное множество
      \begin{equation*}
        G = K_{d_1} + (0_{d_{k + 1} - d_k} \cup G_0)
      \end{equation*}

      Количество вершин в $G$: $d_1 + (d_{k + 1} - d_k) + (d_k - d_1 + 1) =
      d_{k + 1} + 1$.

      \begin{align*}
        d(u) &= (d_1 - 1) + (d_{k + 1} - d_k) + (d_k - d_1 + 1) = d_{k + 1} \\
        d(v) &= d_1 \\
        d(w) &= d_{G_0}(w) + d_1
      \end{align*}

      Степени вершин в $G_0$ --- это $d_2 - d_1, \dots, d_k - d_1$.
  \end{enumerate}
\end{proof}

\section{Вектор степеней. Критерии графичности вектора Гавела-Хакими. Процедура
layoff. Критерий графичности Эрдеша-Галлаи.}

\begin{definition}
  Вектор степеней графа --- вектор, составленный из степеней вершин графа $G$ в
  порядке невозрастания
  \label{def:degree-vector}
\end{definition}

\begin{definition}
  Говорят, что граф является реализацией своего вектора степеней или степенного
  множества.
\end{definition}

\begin{definition}
  Если вектор является вектором степеней некоторого графа, то говорят, что он
  графический.
\end{definition}

Очевидно, что для графичности вектора необходимо, чтобы выполнялась теорема
Эйлера. Если в векторе $n$ элементов, то для графичности необходимо, чтобы
значения элементов были от $0$ до $n - 1$.

Однако это условия не являются достаточными. Существуют эффективные критерии
графичности заданного вектора.

\begin{theorem}[Критерий графичности вектора]
  Пусть вектор $d = (d_1, \dots, d_n)$, $d_1 \geq d_2 \geq \dots \geq d_n$.
  Производный вектор $d^i$ получается из $d$ удалением элемента $d_i$ и
  уменьшением на единицу первых $d_i$ компонент в получившемся после удаления
  векторе.

  Если $d^i$ при каком-либо $i = \overline{1, n}$ является графическим, то и
  $d$ является графическим.

  Если $d$ является графическим, то существует производный вектор $d^i$ также
  является графическим.
  \label{thm:graphic-crit-vec}
\end{theorem}

\begin{corollary}
  Процедура layoff (layout):
  \begin{enumerate}
    \item
      Берутся $n$ точек, которым присваиваются метки $d_1, \dots, d_n$. В
      качестве ведущей выбирается вершина с наибольшим значением метки $d =
      d_1$.
    \item
      Ведущая вершина соединяется ребром с $d$ вершинами, имеющими максимальное
      значение меток (исключая саму ведущую).
    \item
      Ведущая вершина получает значение метки 0, а вершина, с которой она была
      соединена, получает предудыщее значение минус 1. Если все вершины имеют
      метку 0, то алгоритм завершён.
    \item
      Выбирается новая ведущая вершина с максимальным значением метки и
      переходим на шаг 2.
  \end{enumerate}
  \label{cor:layoff}
\end{corollary}

\begin{theorem}[Критерий графичности, Эрдёш, Галлаи]
  Пусть дан вектор $d = (d_1, \dots, d_n)$, $d_1 \geq \dots \geq d_n$. Он
  графичен $\iff \for k = \overline{1, n}$ выполняется $\ds\sum_{i = 1}^k
  d_i \leq k(k - 1) + \sum_{i = k + 1}^n \min\set{k, d_i}$.
  \label{thm:graphic-crit}
  \label{thm:erdes-gallai}
\end{theorem}

\section{Переключения ребер. Функциональные и контрфункциональные графы.}

\begin{definition}
  Пусть $\set{a, b}$ и $\set{c, d}$ --- два ребра графа $G$. Переключением
  этих рёбер в графе $G$ называется $G^* = G - \set{a, b} - \set{c, d} +
  \set{a, d} + \set{b, c}$.
  \label{def:switch}
\end{definition}

\begin{theorem}
  С помощью соответствующей цепочки переключений рёбер можно осуществить переход
  от любой реализации вектора степеней к любой другой его реализации.
\end{theorem}

\begin{definition}
  Орграф $\vec{G} = (V, \alpha)$ называется функциональным, если степень исхода
  любой его вершины равна 1, и контрфункциональным, если степень захода каждой
  вершины равна 1.
  \label{def:functional}
  \label{def:contrafunctional}
\end{definition}

Пусть на конечном множестве $V$ задана некоторая функция $f : V \to V$ со
значениями в этом множестве. Сопоставим этой функции орграф, рассматривая
функцию как отношение: если $f(u) = v$ --- это значит $(u, v) \in \alpha$.

Очевидно, что полученный орграф будет функциональным. Верно и обратное: любому
функциональному орграфу можно сопоставить функцию в указанном смысле.

\section{Изоморфизм и вложение. Немое изображение, абстрактные графы. Униграфы.}

\begin{definition}
  Если вектор степеней имеет единственную реализацию, то говорят, что вектор
  степеней определяет униграф. Заметим, что все графы с числом вершин меньше
  пяти являются униграфами.
  \label{def:unigraph}
\end{definition}

\begin{definition}
  Минимальным по числу вершин и рёбер неуниграфом является граф реализации
  вектора степеней $(2, 2, 2, 1, 1)$.
\end{definition}

\begin{definition}
  $\vec{G} = (U, \alpha),\, \vec{H} = (V, \beta)$. Говорят, что $\vec{G}$
  изоморфен $\vec{H}$, если существует биекция $\varphi : U \to V$, которая
  сохраняет отношение смежности: $(\forall u_1, u_2 \in U) ((u_1, u_2) \in
  \alpha \iff (\varphi(u_1), \varphi(u_2)) \in \beta)$.
  \label{def:isomorph}
\end{definition}

\begin{definition}
  $\vec{G} = (U, \alpha),\, \vec{H} = (V, \beta)$. Говорят, что $\vec{G}$
  вкладывается в $\vec{H}$, если существует инъекция $\varphi : U \to V$, для
  которой выполняется: $(\forall u_1, u_2 \in U) ((u_1, u_2) \in \alpha \implies
  (\varphi(u_1), \varphi(u_2)) \in \beta)$.
  \label{def:enclosure}
\end{definition}

\begin{definition}
  Немым изображением графа называют его изображение, в котором опущены имена
  меток.
\end{definition}

Очевидно, что два графа изоморфны $\iff$ они допускают одинаковое немое
изображение.

Очевидно, что отношение изоморфизма является отношением эквивалентности. Классы
этого отношения называются абстрактными графами.

\begin{definition}
  Метод канонических представителей:
  \begin{enumerate}
    \item Определить способ кодирования объектов;
    \item Среди всех кодов изоморфных объектов выбирается канонический код;
    \item
      Порождаются все возможные уникальные структуры вместе с их кодами,
      содержащие всех канонических представителей;
    \item
      Порождённая структура принимается, если её код канонический, в противном
      случае --- исключается.
  \end{enumerate}
\end{definition}

\section{Автоморфизм. Подобные вершины, подобные ребра. Тождественные
(ассиметричные графы). Симметричные графы.}

\begin{definition}
  Изоморфизм графа на себя называется автоморфизмом. Очевидно, что любой граф
  имеет как минимум один автоморфизм --- тождественное отображение.
  \label{def:automorphism}
\end{definition}

\begin{definition}
  Графы, которые имеют только этот автоморфизм, называются асимметричными или
  тождественными. Минимальный по числу вершин --- $0_1$, затем от 6 вершин.
  \label{def:asymm-graph}
  \label{def:identity-graph}
\end{definition}

\begin{definition}
  Вершины $u$ и $v$ называются подобными, если существует автоморфизм $\varphi :
  \varphi(u) = v$.
\end{definition}

\begin{definition}
  Граф, все вершины которого подобны, называется вершинно-симметричным
  (вершинно-транзитивным).
\end{definition}

\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_1)
  = u_2, \varphi(v_1) = v_2$, или $\varphi(u_1) = v_2, \varphi(v_2) = v_1$.
\end{definition}

\begin{definition}
  Граф, у которого все рёбра подобны, называется рёберно-симметрическим (или
  рёберно-транзитивным).
\end{definition}

\begin{definition}
  Граф, являющийся вершинно-симметрическим и рёберно-симметрическим, называется
  симметричным. А граф, обладающий только одним видом симметричности ---
  полусимметричным.
  \label{def:symm-graph}
\end{definition}

$K_{m, n}$ --- всегда рёберно-симметрический, если $m \neq n$. $K_{m, m}$ ---
симметричный.

\section{Часть графа и подграф. Максимальный подграф. Колода.}

\begin{definition}
  Пусть $\vec{G} = (V, \alpha)$. $\vec{G}^* = V^*, \alpha^*) : V^* \subseteq V,
  \alpha^* \subseteq \alpha \cap (V^* \times V^*)$ --- часть графа. То есть
  часть графа состоит из некоторых его вершин и некоторых соединяющих их дуг
  (рёбер).
  \label{def:graph-part}
\end{definition}

\begin{definition}
  Пусть $\vec{G} = (V, \alpha)$. $\vec{G}^* = V^*, \alpha^*) : V^* \subseteq V,
  \alpha^* = \alpha \cap (V^* \times V^*)$ --- подграф. То есть подграф состоит
  из некоторых вершин графа и всех дуг (рёбер), соединяющих эти вершины в графе.
  \label{def:subgraph}
\end{definition}

\begin{definition}
  Максимальным подграфом орграфа $\vec{G} = (V, \alpha)$ называется орграф,
  получающийся удалением одной вершины и всех связанных с ней дуг.
  \label{def:max-subgraph}
\end{definition}

\begin{definition}
  $P(\vec{G})$ (колода графа) --- список максимальных подграфов.
  \label{def:pack}
\end{definition}

\section{Реконструируемость графов. Гипотезы Келли-Улама и Харари.}

\begin{definition}
  Граф $G$ называется реконструкцией графа $H$, если его колода совпадает с
  колодой графа $H : P(G) = P(H)$.
\end{definition}

\begin{definition}
  Говорят, что граф $G = (V, \alpha)$ называется реконструируемым, если он
  изоморфен всякой своей реконструкции.
\end{definition}

\begin{definition}[Гипотеза Келли-Улама]
  Гипотеза вершинной реконструируемости --- все неориентированные графы с числом
  вершин больше двух являются вершинно-реконструируемыми.

  Известно, что гипотеза справедлива для многих классов графов: несвязные
  графы, деревья, двудольные графы и некоторые другие.

  Для ориентированных графов существует бесконечные семейства пар
  нереконструируемых орграфов.
  \label{def:kelly-ulam-conjecture}
\end{definition}

\begin{definition}[Гипотеза Харари]
  Гипотеза рёберное реконструируемости --- всякий неориентированный граф с
  числом рёбер больше трёх является рёберно-реконструируемым.
  \label{def:harari-conjecture}
\end{definition}

\section{Инварианты. Примеры полных инвариантов.}

\begin{definition}
  Инвариантом графа называется один или более параметров графа, которые являются
  одинаковыми для всех изоморфных графов.
  \label{def:invariant}
\end{definition}

\begin{definition}
  Инвариант называется полным, если он различен для всех неизоморфных графов.
\end{definition}

\textbf{TODO:} Добавить примеры полных инвариантов.

\section{Отказоустойчивые реализации. Вершинные и реберные расширения.
Минимальные, неприводимые, тривиальные, точные расширения.}

Пусть граф является функциональной моделью некоторой технической системы.
Вершины графа соответствуют элементам, а рёбра --- связям. Элементы могут
иметь различные типы, и в этом случае вершинам приписывают метки.

Система, представленная орграфом $\vec{G_1}$, моделируется системой,
представленной графом $\vec{G_2}$, если $\vec{G_1}$ вкладывается в $\vec{G_2}$
с сохранением типов элементов (вершина одного типа переходит в вершину того же
типа).

\begin{definition}
  Под отказом элемента системы будем понимать удаление из графа системы
  соответствующей вершины и всех её рёбер или дуг.
  \label{def:fault-vert}
\end{definition}

\begin{definition}
  Под отказом связи между элементами будем понимать удаление из графа системы
  соответствующего связи ребра или дуги.
  \label{def:fault-edge}
\end{definition}

\begin{definition}
  Говорят, что система $\Sigma^*$ $k$-отказоустойчиво моделирует систему
  $\Sigma$, если граф $G(\Sigma)$ вкладывается в любой граф, получающийся из
  графа $G(\Sigma^*)$ удалением любых $k$ вершин и всех связанных с ними
  рёбер (вершинная отказоустойчивость).

  Система $\Sigma^*$ --- $k$-отказоустойчивая реализация системы $\Sigma$.
\end{definition}

Если рассматривать вместо отказов вершин отказы рёбер, то будет определение
рёберной отказоустойчивости. Если рассматривать отказы элементов (вершин или
рёбер), то будет комбинированная отказоустойчивость.

Отказоустойчивость – это способность системы противостоять ошибке и продолжать
работу в присутствии этой ошибки. Два уровня – полная отказоустойчивость и
амортизация отказов.

\begin{definition}
  Система $\Sigma^*$ называется оптимальной $k$-отказоустойчивой реализацией
  (вершинной) системы $\Sigma$, если выполняются следующие условия:
  \begin{enumerate}
    \item Система $\Sigma^*$ является $k$-ОУР (вершинной) системы $\Sigma$;
    \item Система $\Sigma^*$ имеет минимально возможное число вершин;
    \item
      Из всех систем, удовлетворяющих условиям 1 и 2 система $\Sigma^*$ имеет
      минимально возможное число рёбер.
  \end{enumerate}
  \label{def:optimal-impl}
\end{definition}

\begin{definition}
  Граф $G^*$ является вершинным (рёберным) $k$-расширением графа $G$, если граф
  $G$ вкладывается в любой граф, получающийся из $G^*$ удалением любых $k$
  вершин и связанных с ними рёбер (просто рёбер).
\end{definition}

\begin{definition}
  Граф $G^*$ называется $k$-неприводимым расширением (вершинным или рёберным)
  графа $G$, есть $G^*$ является $k$-расширением, а никакая его часть
  (собственная) не является $k$-расширением графа $G$.
\end{definition}

\begin{definition}
  Граф $G^*$ называется тривиальным расширением графа $G$, если $G^* = G + K_k$,
  то есть тривиальное $k$-расширение получается из графа добавлением $k$
  вершин и связи их между собой и всеми вершинами графа $G$.

  Очевидно, что тривиальное расширение является и вершинным, и рёберным
  $k$-расширением графа.
\end{definition}

\begin{definition}
  Граф $G^* = (V^*, \alpha^*)$ называется минимальным вершинным $k$-расширением
  графа $G = (V, \alpha)$, если выполняются три условия:
  \begin{enumerate}
    \item $G^*$ является вершинным $k$-расширением графа $G$;
    \item $G^*$ имеет на $k$ вершин больше, чем $G$: $|V^*| = |V| + k$;
    \item
      Среди всех графов, удовлетворяющих условиям 1 и 2, $G^*$ имеет минимально
      возможное число рёбер.
  \end{enumerate}

  Очевидно, что любой граф имеет минимальное вершинное $k$-расширение.
\end{definition}

\begin{definition}
  Граф $G^* = (V^*, \alpha^*)$ называется минимальным рёберным $k$-расширением
  графа $G = (V, \alpha)$, если выполняются три условия:
  \begin{enumerate}
    \item $G^*$ является рёберным $k$-расширением графа $G$;
    \item $G^*$ имеет столько же вершин, сколько и $G$: $|V^*| = |V|$;
    \item
      Среди всех графов, удовлетворяющих условиям 1 и 2, $G^*$ имеет минимально
      возможное число рёбер.
  \end{enumerate}

  Не всякий граф имеет минимальное рёберное $k$-расширение.
\end{definition}

\section{Минимальные вершинные расширения, основные свойства. Леммы. Минимальные
вершинные 1"=расширения цепей. Точные расширения. Минимальные вершинные
1-расширения циклов.}

\begin{lemma}
  Если в графе $G$ минимальная из степеней вершин $d > 0$, то МВ-kР не содержит
  вершин степени меньше $d + k$.
  \label{lem:mv-kr-less}
\end{lemma}
\begin{proof}
  $G = (V, \alpha)$, $d > 0$ --- минимальная из степеней вершин.

  $G^* = (V^*, \alpha^*)$ и в $G^*$ $d(v) < d + k$.
  
  Рассмотрим граф, получающийся из $G^*$ удалением $k$ вершин, смежных с $v$.
  (Если $d(v) < k$, то удаление всех вершин, смежных с $v$, и $k - d(v)$
  произвольных вершин, отличных от $v$).

  В получившемся графе степень вершины $v < d$. Очевидно, что $G$ нельзя будет
  вложить в получившийся граф, это противоречит предположению $\implies
  d(v) < d + k$.
\end{proof}

\begin{lemma}
  Если в графе $G$ максимальная из степеней вершин есть $d$, и таких вершин
  $m$, то МВ-kР содержит не менее, чем $(m + k)$ вершин степени не ниже $d$.
\end{lemma}
\begin{proof}
  $G = (V, \alpha)$, $d > 0$ --- максимальная из степеней вершин.

  $G^* = (V^*, \alpha^*)$ и в $G^*$ менее чем $m + k$ вершин имеют степень $\geq
  d$.
  Рассмотрим граф, получающийся из $G^*$ удалением $k$ вершин наибольшей степени.
  В получившемся графе меньше, чем $m$ вершин будут иметь степень не меньшую
  $d$. И, очевидно, что граф $G$ нельзя будет вложить в получившийся граф.
\end{proof}

\begin{lemma}
  Если в графе $G$ максимальная из степеней вершин есть $d$, то МВ-kР содержит
  не менее, чем $kd$ дополнительных рёбер.
\end{lemma}
\begin{proof}
  $G = (V, \alpha)$, $d > 0$ --- максимальная из степеней вершин.

  В $G^*$ по крайней мере на $k$ вершин степени $\geq d$ больше, чем в графе
  $G$.

  Рассмотрим граф, получающийся удалением $k$ вершин максимальной степени.
  Исходный граф по условию вкладывается в получившийся граф, а сам граф
  отличается от МВ-kР не менее, чем на $dk$ рёбер.
\end{proof}

\begin{definition}
  Граф $G = (V, \alpha)$ называется $n$-вершинной цепью и обозначается $P_n$,
  если его вершины $V = \set{v_1, \dots, v_n}$ могут быть занумерованы таким
  способом, чтобы $\alpha$ имело вид:
  \begin{equation*}
    \alpha = \set{\set{v_i, v_{i + 1}}, i = \overline{1, n - 1}}
  \end{equation*}
\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В цепи, Хейз]
  Единственным с точностью до изоморфизма МВ-1Р цепи $P_n$ является цикл
  $C_{n + 1}$.
\end{theorem}
\begin{proof}
  По лемме \ref{lem:mv-kr-less} для любого МВ-1Р цепи не может содержать вершин
  степени меньше двух. Очевидно, что $C_{n + 1}$ является В-1Р цепи $P_n$.

  С другой стороны, цикл $C_{n + 1}$ имеет все вершины степени 2, то есть имеет
  минимально возможное число рёбер $\implies C_{n + 1}$ --- МВ-1Р цепи $P_n$.

  Докажем, что других не существует.

  Предположим, $G^* = (V^*, \alpha^*)$ также является МВ-1Р цепи $P_n$. Тогда
  $G^*$ также будет отличаться от цепи $P_n$ на два дополнительных ребра, причём
  степени всех вершин должны быть равны двум. Очевидно, что добавить в этом
  случае два ребра можно единственно возможным способом, то есть $G^* \cong
  C_{n + 1}$.
\end{proof}

\begin{definition}
  Точным вершинным $k$-расширением графа $G = (V, \alpha)$ называется граф
  $G^* = (V^*, \alpha^*)$: любой граф, получающийся из $G^*$ удалением
  произвольных $k$ вершин вместе с рёбрами, изоморфен $G$.

  Цикл $C_{n + 1}$ является ТВ-1Р цепи $P_n$.
\end{definition}

\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-расширения цепей и циклов.}

\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{Связь точных расширений и симметричности.}

\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{Основные типы неориентированных графов}

\section{Пути в графе. Цепи и циклы в графе. Эксцентриситет, радиус и диаметр.
Центр и окраина. Связность.}

\begin{definition}
  Путём называется последовательность рёбер, в которой каждые два соседних ребра
  имеют общую вершину, и никакое ребро не встречается более одного раза. При этом
  считается, что оба конца каждого ребра, кроме первого и последнего, являются
  концами соседних с ним рёбер.
  \label{def:path}
\end{definition}

\begin{definition}
  Путь называется циклическим, если его первая и последняя вершины совпадают.
  \label{def:cyclic-path}
\end{definition}

\begin{definition}
  Путь, любая вершина которого принадлежит не более, чем двум его рёбрам,
  называется простым.
  \label{def:simple-path}
\end{definition}

\begin{definition}
  Простой циклический путь называется циклом. Простой путь, не являющийся
  циклом, называется цепью.
  \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{Теорема о связности двух нечетных вершин. Достаточное условие
связности.}

\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{Точки сочленения, мосты.}

\begin{definition}
  Вершина, удаление которой приводит к увеличению числа компонент связности,
  называется точкой сочленения. А ребро с таким свойством называется мостом.
\end{definition}

\section{Деревья. Лист и корень. Характеристическая теорема о деревьях. Теорема
о центре дерева.}

\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. Кодирование
деревьев.}

\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{Уровневые коды. Канонические коды. Код Прюфера.}

\begin{definition}
  Канонический код графа --- выбранный по определённым правилам один из кодов
  изоморфных графов. Уникальная строка, которая не зависит от порядка
  нумерации вершин.
\end{definition}

У изоморфных графов одинаковые канонические коды, у неизоморфных --- разные.

\begin{definition}
  Каноническая нумерация --- это нумерация (перестановка) вершин графа,
  гарантирующая, что изоморфные графы будут пронумерованы одинаково.
\end{definition}

\textbf{TODO}: другие коды.

\section{Сеть. Остовное (покрывающее) дерево. Алгоритмы Прима и Краскала.}

\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{Укладки графов. Укладки на сфере и в пространстве. Планарные графы.
Планарность деревьев.}

\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-элементный цикл, число ребер в
триангуляции, необходимое условие планарности, степень вершины в триангуляции.}

Пусть дан граф $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. Стягивание ребра, минор. Критерии планарности
(Понтрягин-Куратовский, Вагнер). Прямолинейное изображение. Род поверхности, род
графа, число скрещиваний.}

\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{Эйлеровы графы. Критерий эйлеровости графа. Критерий существования
эйлерова пути.}

Рассмотрим неориентированный граф $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{Гамильтоновы графы. Доказательство с нулевым разглашением гамильтонова
цикла. Теорема Оре. Теорема Дирака (следствие т. Оре). Достаточное условие Поша.
Достаточное условие Хватала.}

\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{Замыкание. Критерий и достаточное условие Бонди-Хватала.}

\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

\begin{definition}
  Источником в орграфе называется такая его вершина, которая не достижима ни из
  какой другой его вершины.
  \label{def:source}
\end{definition}

\begin{definition}
  Стоком в орграфе называется вершина, из которой не достижима никакая другая
  вершина орграфа.
  \label{def:sink}
\end{definition}

\begin{definition}
  Пусть $\vec{G} = (V, \alpha)$ --- некоторый орграф, а $\theta \subseteq V
  \times V$ --- отношение эквивалентности на множестве его вершин.

  Фактор-графом орграфа $\vec{G}$ по эквивалентности $\theta$ называется орграф
  $\vec{G}/\theta$, вершинами которого являются классы эквивалентности отношения
  $\theta$, при этом из вершины $\theta(u)$ проведена дуга в $\theta(v)$, если
  существуют вершины $u' \in \theta(u), v' \in \theta(v) : (u', v') \in \alpha$.
  \label{def:factor}
\end{definition}

\begin{definition}
  Конденсация орграфа $\vec{G} = (V, \alpha)$ --- это фактор-граф
  $\vec{G}/\varepsilon$ (по отношению взаимной достижимости).

  Так как классами отношения $\varepsilon$ являются сильные компоненты орграфа,
  то они и будут вершинами конденсации.
  \label{def:condensation}
\end{definition}

\textbf{TODO}: свойства конденсации

\begin{theorem}[Бесконтурность конденсации]
  Конденсация всякого орграфа является бесконтурным графом.
  \label{thm:acyclic-condensation}
\end{theorem}
\begin{proof}
  Предположим, что это не так. Пусть $\vec{G} = (V, \alpha)$ и в
  $\vec{G}/\varepsilon$ существует нетривиальный контур. $\varepsilon(u_1) \to
  \varepsilon(u_2) \to \dots \to \varepsilon(u_k),\, k > 1$.

  В любом классе отношения $\varepsilon$ орграфа $\vec{G}$ все вершины
  взаимно достижимы. $\varepsilon(u_1) \to \varepsilon(u_2) \to \dots \to
  \varepsilon(u_k) \to \varepsilon(u_1)$.

  По определению конденсации в $\vec{G}$ существуют вершины $u_1' \in
  \varepsilon(u_1),\, u_2' \in \varepsilon(u_2) : (u_1', u_2') \in \alpha$ в
  орграфе $\vec{G}$. Вершина $u_2$ достижима из $u_1$.

  Аналогично, $u_3$ достижима из $u_2$ и так далее. $u_k$ достижима из $u_{k -
  1}$, $u_1$ достижима из $u_k$.

  В силу транзитивности получаем, что вершина $u_1$ достижима из $u_2$ и
  наоборот. То есть $u_1$ и $u_2$ взаимно достижимы. По определению
  конденсации $u_1$ и $u_2$ должны принадлежать одному классу $\varepsilon$.
  \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}
  Рассмотрим граф $G = (V, \alpha)$. Каждой его вершине припишем некоторый цвет
  так, чтобы смежные вершины имели разные цвета. Обозначим цвета числами $1,
  \dots, p$. Тогда раскраску графа можно рассматривать как функцию $f : V \to
  \set{1, p}$ если $\set{v_i, v_j} \in \alpha \implies f(v_i) \neq f(v_j)$.
  При этом говорят, что граф $G$ допускает раскраску в $p$ цветов или является
  $p$-раскрашиваемым.
\end{definition}

\begin{definition} \label{def:chroma-num}
  Минимальное значение $p$, при котором граф является $p$-раскрашиваемым,
  называется его хроматическим числом и обозначается $\chi(G)$. Аналогичным
  образом можно рассматривать раскраску ребер. Соответствующий хроматическому
  числу параметр в этом случае называется хроматическим индексом.
\end{definition}

Интерес представляет описание графов с заданным хроматическим числом. Например,
$\chi(G) = 1$ --- вполне несвязные $O_n$. Графы с $\chi(G) = 2$ --- это
двудольные графы, отличные от вполне несвязных.

\begin{theorem}[Кёнига, Критерий двудольности]
  Граф является двудольным $\iff$ он не содержит циклов нечётной длины.
  \label{thm:konig} \label{thm:crit-bipart}
\end{theorem}

\begin{theorem}[О 5 красках, Хивуд]
  Всякий планарный граф допускает раскраску в 5 цветов, то есть $\chi(G) \leq
  5$.
  \label{thm:5-colors}
\end{theorem}
\begin{proof}
  Очевидно, что $\forall G = (V, \alpha),\, n \leq 5$, допускает раскраску
  в 5 цветов.

  Доказательство по ММИ. Пусть $n$-вершинный планарный граф с $n > 5$
  допускает раскраску в 5 цветов. Покажем, что граф $H$ с $(n + 1)$ вершинами
  тоже допускает раскраску в 5 цветов.

  В силу планарности $H$ в нём существует вершина $v$ со степенью меньше или
  равной 5. Рассмотрим два случая:
  \begin{enumerate}
    \item
      $d(v) < 5$. Тогда $H - \set{v}$ --- по предположению 5-раскрашиваемый.
      Возвращаясь к графу $H$, остальные раскрашиваем как $H - \set{v}$, а
      вершину $v$ в цвет, отличный от цвета смежных вершин.
    \item
      $d(v) = 5$. $v_1, \dots, v_5$ не могут быть все попарно смежными (иначе
      будет $K_5$). То есть как минимум одна пара этих вершин, несмежных между
      собой. Пусть это $v_1$ и $v_2$. Рассмотрим граф, получающийся из $H$
      объединением $v_1$ и $v_2$ (\link[def:factor]{фактор-граф} по отношению
      $\theta$, где $\set{v_1, v_2}$). По предположению этот граф допускает
      раскраску пятью цветами. Возвращаясь к $H$, оставляем раскраску, а $v_1$ и
      $v_2$ раскрашиваем в цвет $\set{v_1, v_2}$.
  \end{enumerate}
\end{proof}

\end{document}