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}

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

\input{style.tex}

\begin{document}

\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}
  Полный двудольный граф вида называется звездным графом или звездой.
  \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}
  Метод канонических представителей:
  \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) =
  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{Отказоустойчивые реализации. Вершинные и реберные расширения.
Минимальные, неприводимые, тривиальные, точные расширения.}

\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$.
\end{lemma}

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

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

\begin{lemma}
  \textbf{TODO:} ЧТО??

  $G = (V, \alpha)$, $d > 0$ --- минимальная из степеней вершин.

  $G^* = (V^*, \alpha^*)$ и в $G^*$ $d(v) < d + k$.
\end{lemma}

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

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

\begin{lemma}
  \textbf{TODO:} ЧТО?? №2

  $G = (V, \alpha)$, $d > 0$ --- максимальная из степеней вершин.

  $G^* = (V^*, \alpha^*)$ и в $G^*$ менее чем $m + k$ вершин имеют степень $\geq
  d$.
\end{lemma}

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

\begin{lemma}
  $G = (V, \alpha)$, $d > 0$ --- максимальная из степеней вершин.

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

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

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

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

\begin{theorem}[О МВ-1В цепи, Хейз]
  Единственным с точностью до изоморфизма МВ-1Р цепи $P_n$ является цикл
  $C_{n + 1}$.
\end{theorem}
\begin{proof}
  По лемме ??? для любого МВ-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}

\textbf{TODO:} Лекция 3, страница 67 --- Лекция 5

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

\dots

\section{Связь точных расширений и симметричности.}

\dots



\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}

\section{Теорема о связности двух нечетных вершин. Достаточное условие
связности.}

\dots

\section{Точки сочленения, мосты.}

\dots

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

\dots

\section{Изоморфизм деревьев: алгоритм Эдмондса, алгоритм WAV. Кодирование
деревьев.}

\dots

\section{Уровневые коды. Канонические коды. Код Прюфера.}

\dots

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

\dots

\section{Укладки графов. Укладки на сфере и в пространстве. Планарные графы.
Планарность деревьев.}

\dots

\section{Грань. Теорема Эйлера и её обобщения. Триангуляция, максимально плоский
граф. Следствия из теоремы: если всякая грань k-элементный цикл, число ребер в
триангуляции, необходимое условие планарности, степень вершины в триангуляции.}

\dots

\section{Графы типа 1 и типа 2. Стягивание ребра, минор. Критерии планарности
(Понтрягин-Куратовский, Вагнер). Прямолинейное изображение. Род поверхности, род
графа, число скрещиваний.}

\dots

\section{Эйлеровы графы. Критерий эйлеровости графа. Критерий существования
эйлерова пути.}

\dots

\section{Гамильтоновы графы. Доказательство с нулевым разглашением гамильтонова
цикла. Теорема Оре. Теорема Дирака (следствие т. Оре). Достаточное условие Поша.
Достаточное условие Хватала.}

\dots

\section{Замыкание. Критерий и достаточное условие Бонди-Хватала.}

\dots




\chapter{Пути в орграфах}

\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}

% 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{Раскраски графов. Критерий двудольности. Теорема о 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}