feat: changes in report

1 files changed, 38 insertions, 21 deletions

diff --git a/report/coursework.tex b/report/coursework.tex
index c48e219..98a9f87 100644
--- a/report/coursework.tex
+++ b/report/coursework.tex
@@ -1,7 +1,8 @@
 \documentclass[spec, och, coursework-kb]{SCWorks}
 \usepackage{preamble}
 
-\title{Сравнение различных достаточных условий гамильтоновости графов}
+\title{Жёсткость и запрещённые подграфы в достаточных условиях гамильтоновости
+графов}
 \author{Гущина Андрея Юрьевича} % Фамилия, имя, отчество в родительном падеже
 
 \begin{document}
@@ -32,8 +33,9 @@ NP"=полной задачей, крайне неэффективной для
 условие Дирака и позволяющие определить большее количество гамильтоновых графов.
 
 В данной работе рассмотрены теоремы, основанные на понятии \textit{жёсткости},
-введённом Вацлавом Хваталом в 1973 году, а также их сравнение с указанными выше
-достаточными условиями гамильтоновости графов. 
+введённом Вацлавом Хваталом в 1973 году и теоремы, основанные на широко
+используемой концепции \emph{запрещённых подграфов}, а также сравнение данных
+теорем с указанными выше достаточными условиями гамильтоновости графов.
 
 
 \section{Основные определения}
@@ -60,10 +62,10 @@ NP"=полной задачей, крайне неэффективной для
 
 \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)$. Если начальная и конечная вершины совпадают, то путь
-  называется циклическим. Путь, каждая вершина которого принадлежит не более чем
-  двум его рёбрам, считается простым. Если начальная вершина простого пути
+  $\dots$, $(v_{n - 1}, v_n)$, в которой $(v_{i - 1}, v_i) \in \alpha ~ (\forall
+  ~ 1 \leq i \leq n)$. Если начальная и конечная вершины совпадают, то путь
+  называется циклическим. Путь, каждая вершина которого принадлежит не более
+  чем двум его рёбрам, считается простым. Если начальная вершина простого пути
   совпадает с конечной, путь называют циклом, в противном случае – цепью.
 \end{definition}
 
@@ -201,7 +203,7 @@ fn posa_theorem(g: &Graph) -> bool {
   условие $d(u) + d(v) \geq n$.
 \end{definition}
 
-Можно заметить, что такой алгоритм построения такого замыкания имеет сложность
+Можно заметить, что алгоритм построения такого замыкания имеет сложность
 $O(n^4)$. Немного изменённая версия этого алгоритма используется при построении
 гамильтонова цикла на основе нижеследующих теорем.
 
@@ -282,10 +284,10 @@ m$ за $O(n)$ шагов. Тогда, цикл $C'$:
   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)$ шагов.
+Данную процедуру необходимо повторять до тех пор, пока гамильтонов цикл не будет
+найден. Так как $(\forall i, j) ~ a_{ij} \leq C_n^2$, первоначальный цикл $C$ в
+замыкании $C_n(G)$ будет преобразован в гамильтонов цикл в графе $G$ не более,
+чем за $O(n^3)$ шагов.
 
 
 \section{Достаточные условия, основанные на жёсткости}
@@ -397,7 +399,7 @@ fn check_toughness(&self, t: f64) -> bool {
 В первую очередь необходимо посчитать количество графов с разным количеством
 вершин, отвечающих соответствующим достаточным условиям гамильтоновости. Для
 выполнения данной задачи была написана программа на языке программирования Rust,
-которая указана в Приложении \ref{app:rust}.
+которая указана в Приложениях \ref{app:rust1} -- \ref{app:rust6}.
 
 \subsection{Условия, основанные на жёсткости}
 
@@ -485,7 +487,7 @@ fn check_toughness(&self, t: f64) -> bool {
 
 Абсолютные значения количества определяемых графов не представляют особой
 ценности, так как условие Бонди"=Хватала определило значительно большее
-количество графов. Более полезными будут данные о разности графов, определяемых
+количество графов. Более полезными будут данные о разности множеств графов, определяемых
 указанными теоремами с графами, определяемыми эталонной теоремой Бонди"=Хватала.
 
 В колонках таблицы \ref{tbl:forbidden-diff} указан размер множества графов,
@@ -557,11 +559,26 @@ $|T_{BH} - (T_{BH} \cap T)|$, где $T_{BH}$ "--- множество графо
 вариантов построения гамильтонова цикла в графе, который также является
 NP"=полной задачей.
 
-Теорема Поша, с которой производилось сравнение Теорем \ref{thm:bigalke} и
+Теорема Поша, с которой производилось сравнение теорем \ref{thm:bigalke} и
 \ref{thm:bauer} является более подходящей для такой задачи, так как
 способна определять гамильтоновость более 25\% графов, при этом имея
 значительно более эффективную сложность $O(n + m)$.
 
+Теоремы, основанные на запрещённых подграфах при этом позволяют определить
+ещё меньшее количество графов по сравнению с другими рассмотренными теоремами.
+Но при этом они позволяют определять некоторые из графов, которые не способна
+определить теорема Бонди"=Хватала, которая является самой эффективной из
+рассмотренных.
+
+Данные теоремы в основном представляют теоретический интерес, так как
+рассматривают совершенно иной способ определения гамильтоновости для
+произвольных графов. Хотя они являются достаточно неэффективными в смысле
+вычислительной сложности, они всё же имеют полиномиальную сложность и поэтому
+в некоторых случаях их можно использовать для проверки на гамильтоновость тех
+графов, которые не способна определить теорема Бонди"=Хватала. Например,
+такие теоремы позволяют распознать гамильтоновы графы с небольшим количеством
+рёбер вокруг цикла.
+
 
 \bibliographystyle{gost780uv}
 \inputencoding{cp1251}
@@ -571,27 +588,27 @@ NP"=полной задачей.
 \appendix
 
 \section{Исходный код программы подсчёта графов на языке Rust, файл main.rs}
-\label{app:rust}
+\label{app:rust1}
 \inputminted{rust}{../graph-checker/src/main.rs}
 
 \section{Исходный код программы подсчёта графов на языке Rust, файл graph.rs}
-\label{app:rust}
+\label{app:rust2}
 \inputminted{rust}{../graph-checker/src/graph.rs}
 
 \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/basic.rs}
-\label{app:rust}
+\label{app:rust3}
 \inputminted{rust}{../graph-checker/src/theorems/basic.rs}
 
 \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/forbidden.rs}
-\label{app:rust}
+\label{app:rust4}
 \inputminted{rust}{../graph-checker/src/theorems/forbidden.rs}
 
 \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/toughness.rs}
-\label{app:rust}
+\label{app:rust5}
 \inputminted{rust}{../graph-checker/src/theorems/toughness.rs}
 
 \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/mod.rs}
-\label{app:rust}
+\label{app:rust6}
 \inputminted{rust}{../graph-checker/src/theorems/mod.rs}