Добавлена вторая глава

1 files changed, 781 insertions, 17 deletions

diff --git a/graphs-exam/graphs-exam.tex b/graphs-exam/graphs-exam.tex
index ab75c2a..338b357 100644
--- a/graphs-exam/graphs-exam.tex
+++ b/graphs-exam/graphs-exam.tex
@@ -193,70 +193,745 @@
 \section{Типы графов: ориентированные графы, неориентированные графы, диграфы,
 полные графы, вполне несвязные графы. Симметризация.}
 
-\dots
+\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{Степени вершин. Спецификация.}
 
-\dots
+\begin{definition}
+  Степенью исхода вершины $v$ называется число $d^+$, равное количеству дуг в
+  $\vec{G}$, имеющих $v$ своим началом. $d^+(v) = |\alpha(v)|$.
+  \label{def:out-degree}
+\end{definition}
 
-\section{Двудольные графы. Звезды.}
+\begin{definition}
+  Степенью захода вершины $v$ называется число $d^-$, равное количеству дуг в
+  $\vec{G}$, имеющих $v$ своим концом. $d^-(v) = |\alpha^{-1}(v)|$.
+  \label{def:in-degree}
+\end{definition}
 
-\dots
+\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-мерный тор.}
 
-\dots
+\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{Теорема Эйлера о степенях вершин. Однородные графы.}
 
-\dots
+Пусть $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{Степенное множество. Теорема о степенном множестве.}
 
-\dots
+\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. Критерий графичности Эрдеша-Галлаи.}
 
-\dots
+\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{Переключения ребер. Функциональные и контрфункциональные графы.}
 
-\dots
+\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{Изоморфизм и вложение. Немое изображение, абстрактные графы. Униграфы.}
 
-\dots
+\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{Автоморфизм. Подобные вершины, подобные ребра. Тождественные
 (ассиметричные графы). Симметричные графы.}
 
-\dots
+\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{Часть графа и подграф. Максимальный подграф. Колода.}
 
-\dots
+\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{Реконструируемость графов. Гипотезы Келли-Улама и Харари.}
 
-\dots
+\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{Инварианты. Примеры полных инвариантов.}
 
-\dots
+\begin{definition}
+  Инвариантом графа называется один или более параметров графа, которые являются
+  одинаковыми для всех изоморфных графов.
+  \label{def:invariant}
+\end{definition}
+
+\begin{definition}
+  Инвариант называется полным, если он различен для всех неизоморфных графов.
+\end{definition}
+
+\textbf{TODO:} Добавить примеры полных инвариантов.
 
 \section{Отказоустойчивые реализации. Вершинные и реберные расширения.
 Минимальные, неприводимые, тривиальные, точные расширения.}
 
-\dots
+\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"=расширения цепей. Точные расширения. Минимальные вершинные
 1-расширения циклов.}
 
-\dots
+\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-расширения цепей и циклов.}
@@ -271,6 +946,95 @@ layoff. Критерий графичности Эрдеша-Галлаи.}
 
 \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{Пути в орграфах}