First version of report

1 files changed, 447 insertions, 5 deletions

diff --git a/report/coursework.tex b/report/coursework.tex
index 38b6854..ab86834 100644
--- a/report/coursework.tex
+++ b/report/coursework.tex
@@ -5,15 +5,457 @@
 \author{Гущина Андрея Юрьевича} % Фамилия, имя, отчество в родительном падеже
 
 \begin{document}
-\include{titlepage.tex}
+\input{titlepage.tex}
 \tableofcontents
 
 \intro
 
+Введение
 
-% \bibliographystyle{gost780uv}
-% \inputencoding{cp1251}
-% \bibliography{sources}
-% \inputencoding{utf8}
+
+\section{Основные определения}
+
+Рассмотрим основные определения, которые понадобятся при изучении достаточных
+условий гамильтоновости графов. Данные определения даются по работам
+\cite{Bogomolov_1997} и \cite{harary_1973}.
+
+\begin{definition}
+  Неориентированным графом (или просто графом) называется пара $G = (V,
+  \alpha)$, где $V$ "--- конечное непустое множество (\textit{вершины} графа), а
+  $\alpha \subseteq V \times V$ "--- симметричное и антирефлексивное отношение
+  на множестве вершин $V$. Пара $(u, v) \in \alpha$ называется дугой графа с
+  началом $u$ и концом $v$.
+\end{definition}
+
+\begin{definition}
+  Граф называется полным, если любые две его вершины соединены ребром, т. е.
+  если $\alpha = (V \times V) = \Delta$.
+\end{definition}
+
+\begin{definition}
+  Маршрутом в графе называется последовательность дуг $(v_0, v_1), (v_1, v_2),
+  \dots, (v_{n - 1}, v_n)$, в которой $(v_{i - 1}, v_i) \in \alpha ~ (\forall ~
+  1 \leq i \leq n)$. Циклический маршрут "--- это маршрут, в котором начальная и
+  конечная вершины совпадают. Маршрут, в котором никакая дуга не встречается
+  более одного раза, называется путём. Путь, каждая вершина которого принадлежит
+  не более, чем двум его дугам, по определению является простым. Простой
+  циклический путь называют контуром, а простой путь, не являющийся контуром
+  "--- бесконтурным путём или цепью.
+\end{definition}
+
+\begin{definition}
+  Бесконтурный путь длины $n - 1$ в графе $G$ называется гамильтоновой цепью, а
+  контур длины $n$ "--- гамильтоновым контуром. Граф, в котором существует
+  гамильтонов контур, по определению, является гамильтоновым.
+\end{definition}
+
+\begin{definition}
+  Вершины $u$ и $v$ графа $G$ называются связанными, если в $G$ существует
+  проходящий через них путь. Классы эквивалентности отношения связности
+  называются компонентами связности (или просто компонентами) графа.
+\end{definition}
+
+\begin{definition}
+  Частью графа называется граф $G^* = (V^*, \alpha^*)$, где $V^* \subseteq V$ и
+  $\alpha^* \subseteq (V^* \times V^*) \cap \alpha$.
+\end{definition}
+
+\begin{definition}
+  Подграф графа $G$ "--- это такая его часть $G^* = (V^*, \alpha^*)$, которая
+  содержит все дуги графа $G$, соединяющие попавшие в данную часть вершины, т.
+  е. $\alpha^* = (V^* \times V^*) \cap \alpha$.
+\end{definition}
+
+
+\section{Основные достаточные условия гамильтоновости графов}
+
+\begin{theorem}[Дирак, \cite{dirac1952some}]
+  \label{thm:dirac}
+  Если в графе $G$ с числом вершин $n \geq 3$ степень любой вершины $d(u) \geq n
+  / 2$, то граф $G$ "--- гамильтонов.
+\end{theorem}
+
+\begin{minted}{rust}
+fn dirac_theorem(g: &Graph) -> bool {
+    for vertex in 0..g.size {
+        if (g.degree(vertex) as f64) < g.size as f64 / 2.0 {
+            return false;
+        }
+    }
+    return true;
+}
+\end{minted}
+
+Вычислительная сложность данного алгоритма "--- $O(n + m)$.
+
+\begin{theorem}[Оре, \cite{ore1960note}]
+  \label{thm:ore}
+  Если в графе $G$ с числом вершин $n \geq 3$ для любых двух несмежных вершин
+  $u$ и $v$ выполняется неравенство $d(u) + d(v) \geq n$, то граф $G$ "---
+  гамильтонов.
+\end{theorem}
+
+\begin{minted}{rust}
+fn ore_theorem(g: &Graph) -> bool {
+    for v1 in 0..g.size {
+        for v2 in 0..g.size {
+            if v1 == v2 || g.matrix[v1][v2] != 0 {
+                continue;
+            }
+            let d1 = g.degree(v1);
+            let d2 = g.degree(v2);
+            if d1 + d2 < g.size {
+                return false;
+            }
+        }
+    }
+    return true;
+}
+\end{minted}
+
+\begin{theorem}[Поша, \cite{posa1963circuits}]
+  \label{thm:posa}
+  Если граф $G$ с числом вершин $n \geq 3$ и степенной последовательностью $d_1
+  \leq \dots \leq d_n$ удовлетворяет следующим двум условиям, то он гамильтонов:
+  \begin{enumerate}
+    \item 
+      для всякого $k: ~ 1 \leq k < \frac{n - 1}{2}$ число вершин со степенями
+      меньшими или равными $k$ меньше, чем $k$;
+    \item
+      для нечётного $n$ число вершин со степенями меньшими или равными $\frac{n
+      - 1}{2}$ не превосходит ${n - 1}{2}$.
+  \end{enumerate}
+\end{theorem}
+
+\begin{minted}{rust}
+fn posa_theorem(g: &Graph) -> bool {
+    let mut degrees = Vec::new();
+    for v in 0..g.size {
+        degrees.push(g.degree(v));
+    }
+
+    let end = if g.size % 2 == 0 {
+        g.size / 2
+    } else {
+        (g.size - 1) / 2
+    };
+
+    for k in 1..end {
+        let mut cnt = 0;
+        for d in &degrees {
+            if *d <= k {
+                cnt += 1;
+            }
+        }
+        if cnt >= k {
+            return false;
+        }
+    }
+    if g.size % 2 != 0 {
+        let mut cnt = 0;
+        for d in &degrees {
+            if *d <= end {
+                cnt += 1;
+            }
+        }
+        if cnt > end {
+            return false;
+        }
+    }
+    return true;
+}
+\end{minted}
+
+
+\begin{definition}
+  Замыкание $[G]$ $n$"=вершинного графа $G$ получается из графа $G$ добавлением
+  рёбер $\{ u, v \}$ для всех пар вершин $u$ и $v$, для которых выполняется
+  условие $d(u) + d(v) \geq n$.
+\end{definition}
+
+Можно заметить, что такое алгоритм построения такого замыкания имеет сложность
+$O(n^4)$. Немного изменённая версия этого алгоритма используется при построении
+гамильтонова цикла на основе нижеследующих теорем.
+
+\begin{theorem}[Бонди"=Хватал, \cite{bondy1976method}]
+  \label{thm:bondy-chvatal-1}
+  Граф $G$ является гамильтоновым тогда и только тогда, когда его замыкание
+  $[G]$ является гамильтоновым.
+\end{theorem}
+
+\begin{theorem}[Бонди"=Хватал, \cite{bondy1976method}]
+  \label{thm:bondy-chvatal-2}
+  Если замыкание $[G]$ графа $G$ является полным графом, то граф $G$ "---
+  гамильтонов.
+\end{theorem}
+
+\begin{minted}{rust}
+fn get_closure_traced(&self, trace_steps: bool) -> Graph {
+    let mut step = if trace_steps { 2 } else { 1 };
+
+    let mut closure = self.clone();
+    for _ in 0..(closure.size * closure.size) {
+        let mut changed = false;
+        for row in 0..closure.size {
+            for col in 0..closure.size {
+                if row == col || closure.matrix[row][col] != 0 {
+                    continue;
+                }
+                let sum = closure.degree(row) + closure.degree(col);
+                if sum >= closure.size {
+                    closure.matrix[row][col] = step;
+                    if trace_steps {
+                        step += 1;
+                    }
+                    changed = true;
+                }
+            }
+        }
+        if !changed {
+            break;
+        }
+    }
+    return closure;
+}
+\end{minted}
+
+\subsection{Алгоритм нахождения гамильтонова цикла на основе условия Бонди"=Хватала}
+
+В том случае, если некоторый граф $G = (V, \alpha)$ отвечает теореме
+\ref{thm:bondy-chvatal-2}, то к нему можно применить алгоритм нахождения
+гамильтонова цикла со сложностью $O(n^3)$.
+
+Пусть $A = (a_{ij})$ "--- матрица смежности графа $G$. Построим матрицу
+смежности замыкания $C_k(G)$ по следующему алгоритму:
+\begin{enumerate}
+  \item Установить $(\forall i) ~ D_i = \sum a_{ij}$. Установить $M = 2$.
+  \item 
+    Находится некоторая пара $(i, j)$, где $i \neq j, a_{ij} = 0 \land D_i + D_j
+    \geq k$. Если такая пара не может быть найдена, то остановить алгоритм.
+  \item
+    Заменить $a_{ij}$ и $a_{ji}$ на число $M$. Заменить $D_i$ на $D_i + 1$ и 
+    $D_j$ на $D_j + 1$. Заменить $M$ на $M + 1$. Перейти на шаг 2.
+\end{enumerate}
+
+Обозначим множество вершин графа как $V(G)$, а множество рёбер как $E(G)$.
+
+При завершении алгоритма получаем матрицу смежности $A = (a_{ij})$, в которой
+$a_{ij} = 1 \iff ij \in E(G)$ и $a_{ij} = 0 \iff ij \not\in E(C_k(G))$. Далее,
+возьмём некоторый гамильтонов цикл $C: ~ u_1 u_2 \dots u_n u_1$ в замыкании
+$C_k(G)$. Так как по условию теоремы, это замыкание полное, то можно взять любой
+набор вершин графа. Обозначим $m$ равным максимальному значению $a_{ij}$ среди
+всех рёбер цикла $C$. Если $m > 1$, то ребро с таким значением уникально. Если
+$m = 1$, то цикл $C$ является искомым гамильтоновым циклом в графе $G$. Пусть
+ребро у которого $a_{ij} = m$ "--- это $u_1 u_n$. Тогда построить новый цикл
+$C'$ такой, что максимальное значение $a_{ij}$ среди его рёбер меньше, чем $m$.
+Найдём вершину $u_s$ такую, что $0 < a_{u_1 u_{s + 1}} < m$ и $0 < a_{u_n u_s} <
+m$ за $O(n)$ шагов. Тогда, цикл $C'$:
+\begin{equation*}
+  u_1 u_{s + 1} u_{s + 2} \dots u_n u_s u_{s - 1} \dots u_1
+\end{equation*}
+
+Данную процедуру необходимо повторять до тех пор, пока не будет найден
+гамильтонов цикл не будет найден. Так как $(\forall i, j) ~ a_{ij} \leq C_n^2$,
+первоначальный цикл $C$ в замыкании $C_n(G)$ будет преобразован в гамильтонов
+цикл в графе $G$ не более, чем за $O(n^3)$ шагов.
+
+
+\section{Достаточные условия гамильтоновости графов, основанные на жёсткости}
+
+Впервые понятие жёсткости было введено Вацлавом Хваталом в 1973 году.
+Впоследствии на основе данного понятия было доказано большое количество новых
+достаточных условий гамильтоновости графов. Например, в 2006 году было проведено
+обширное исследование таких условий с результатами от разных авторов
+\cite{bauer2006toughness}. Далее приведены две теоремы, основанные на понятии
+жёсткости, а также необходимые для этих теорем определения.
+
+\begin{definition}
+  $\omega(G)$ "--- количество компонент связности в графе $G$. 
+\end{definition}
+
+Для вычисления количества компонент графа можно использовать алгоритм поиска в
+глубину со сложностью $O(n + m)$.
+
+\begin{minted}{rust}
+fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) {
+    visited[*vertex] = 1;
+    for i in 0..self.size {
+        if visited[i] == 0 && self.matrix[*vertex][i] != 0 {
+            self.dfs(&i, visited);
+        }
+    }
+}
+
+fn count_components_partial(&self, included_vertices: &Vec<i32>) -> usize {
+    let mut visited = vec![0; self.size];
+    for i in 0..included_vertices.len() {
+        if included_vertices[i] == 0 {
+            visited[i] = 1;
+        }
+    }
+    let mut count = 0;
+    while visited.iter().sum::<usize>() != visited.len() {
+        let mut next = 0;
+        for i in 0..self.size {
+            if visited[i] == 0 {
+                next = i;
+                break;
+            }
+        }
+        self.dfs(&next, &mut visited);
+        count += 1;
+    }
+    return count;
+}
+\end{minted}
+
+\begin{definition}
+  Граф является $t$"=жёстким, если $(\forall ~ S \subseteq V(G) ~ : ~ \omega(G -
+  S) > 1) ~ |S| \geq t \cdot \omega(G - S)$.
+\end{definition}
+
+\begin{minted}{rust}
+fn check_toughness(&self, t: f64) -> bool {
+    for cutset in self.cutsets() {
+        let components_count = cutset.graph.count_components_partial(&cutset.vertices) as f64;
+        let cut_cardinality = (self.size - cutset.cardinality) as f64;
+        if components_count > 1.0 && cut_cardinality < t * components_count {
+            return false;
+        }
+    }
+    return true;
+}
+\end{minted}
+
+Можно заметить, что проверка графа на $t$"=жёсткость имеет сложность $O(2^n)$,
+что делает данные условия крайне неэффективными для проверки.
+
+\begin{definition}
+  Жёсткость $\tau(G)$ "--- максимальное значение $t$, для которого граф $G$
+  является $t$"=жёстким.
+\end{definition}
+
+Так как число $\tau$ является вещественным, и при этом монотонной и скачковой,
+его можно найти с помощью алгоритма бинарного поиска, имеющего сложность $O(\log
+(n))$. Вкупе с проверкой графа на $t$"=жёсткость, сложность нахождения жёсткости
+имеет сложность $O(2^n \cdot \log (n))$
+
+\begin{definition}
+  $\delta(G)$ "--- минимальная степень в графе $G$.
+\end{definition}
+
+\begin{definition}
+  Множество вершин называется независимым, если никакие две из них не смежны
+  \cite{harary_1973}. Обозначим мощность максимального множества независимых
+  вершин графа $G$ как $\alpha(G)$.
+\end{definition}
+
+\begin{theorem}[Бигалке"=Юнг, \cite{bigalke1979hamiltonsche}]
+  \label{thm:bigalke}
+  Если для 1"=жёсткого графа $G$ с числом вершин $n \geq 3$ выполняется
+  неравенство $\delta \geq \max \{ n / 3, \alpha - 1 \}$, то граф $G$ "---
+  гамильтонов.
+\end{theorem}
+
+\begin{theorem}[Бауэр, \cite{bauer1995long}]
+  \label{thm:bauer}
+  Если для $t$"=жёсткого графа $G$ с числом вершин $n \geq 3$ выполняется
+  неравенство $\delta \geq n / (t + 1) - 1$, то граф $G$ "--- гамильтонов.
+\end{theorem}
+
+
+\section{Вычислительный эксперимент}
+
+Для произведения вычислительного эксперимента была использована программа
+\verb|geng| из пакета \verb|nauty| \cite{mckay2014practical} для генерации
+графов в формате \verb|graph6| \cite{graph6}.
+
+В первую очередь необходимо посчитать количество графов с разным количеством
+вершин, отвечающих соответствующим достаточным условиям гамильтоновости. Для
+выполнения данной задачи была написана программа на языке программирования Rust,
+которая указана в Приложении \ref{app:rust}.
+
+\begin{table}[H]
+  \small    
+  \centering
+  \caption{Количество графов, отвечающих рассмотренным теоремам}
+  \begin{tabular}{|c|c|c|c|c|c|c|c|}
+    \hline
+    $n$ & Всего     & Дирак  & Оре    & Поша    & Бонди"=Хватал & Бигалке"=Юнг & Бауэр   \\ \hline
+    3   & 4         & 1      & 1      & 1       & 1             & 1            & 1       \\ \hline
+    4   & 11        & 3      & 3      & 3       & 3             & 3            & 3       \\ \hline
+    5   & 34        & 3      & 5      & 6       & 7             & 8            & 10      \\ \hline
+    6   & 156       & 19     & 21     & 31      & 45            & 48           & 19      \\ \hline
+    7   & 1044      & 29     & 68     & 190     & 352           & 145          & 145     \\ \hline
+    8   & 12346     & 424    & 503    & 2484    & 5540          & 2553         & 2047    \\ \hline
+    9   & 274668    & 1165   & 4942   & 53492   & 157016        & 83481        & 59395   \\ \hline
+    10  & 12005168  & 108376 & 128361 & 2683649 & 8298805       & 1249871      & 1245462 \\ \hline
+  \end{tabular}
+  \label{tbl:stats}
+\end{table}
+
+По результатам вычислений, указанных в таблице \ref{tbl:stats}, можно заметить,
+что Теоремы \ref{thm:bigalke} и \ref{thm:bauer} по эффективности сравнимы с
+теоремой \ref{thm:posa}, поэтому проведём более подробное сравнение графов,
+отвечающих данным условиям.
+
+Для этого была написана программа на языке программирования Python, считывающая
+вывод программы подсчёта количества графов (которая также выводит сами графы,
+отвечающие заданным условиям). Данная программа приведена в Приложении
+\ref{app:python}.
+
+С помощью этой программы можно проверить пересечения и разности разных
+комбинаций множеств графов Поша, графов Бауэра и графов Бигалке"=Юнга (рис.
+\ref{fig:checker-py}).
+
+\begin{figure}[ht]
+  \centering
+  \includegraphics[width=0.7\textwidth]{python_runner.png}
+  \caption{Пример вывода программы checker.py}
+  \label{fig:checker-py}
+\end{figure}
+
+Выполнив данную программу для графов размером до 8 вершин удалось установить
+несколько фактов об отношениях данных условий гамильтоновости:
+\begin{itemize}
+  \item 
+    Для графов размеров 3, 4, 5 графы Поша являются подмножеством как графов
+    Бауэра, так и графов Бигалке"=Юнга. При этом, графы Поша дополнительно
+    являются подмножеством графов Бигалке"=Юнга, но не Бауэра это связанно с
+    тем, что при 6 вершинах графов Бауэра меньше, чем графов Поша. В данном
+    случае, наоборот, Графы Бауэра являются подмножеством графов Поша;
+  \item
+    Пересечения множеств графов Поша \& графов Бауэра совпадают с
+    пересечениями графов Поша \& графов Бигалке"=Юнга вплоть до
+    графов с 8 вершинами, кроме случая с 6 вершинами;
+  \item
+    Графы Бигалке"=Юнга с 7 вершинами совпадают с графами Бауэра с 7
+    вершинами;
+\end{itemize}
+
+Наиболее эффективным условием (по проценту определяемых графов), всё ещё
+остаётся условие Бонди"=Хватала. Хотя теоремы Бауэра и Бигалке"=Юнга на
+небольшом количестве вершин сравнимы с условием Поша, уже на 10 вершинах они
+значительно уступают данному условию.
+
+
+\conclusion 
+
+Заключение
+
+\bibliographystyle{gost780uv}
+\inputencoding{cp1251}
+\bibliography{sources}
+\inputencoding{utf8}
+
+\appendix
+
+\section{Исходный код программы подсчёта графов на языке Rust}
+\label{app:rust}
+\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{rust}{../src/main.rs}
+
+\section{Исходный код программы сравнения множеств графов на языке Python}
+\label{app:python}
+\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{rust}{../checker.py}
 
 \end{document}
\ No newline at end of file