From 9a5f88dc8bbd45ce1c427133bc05adf87c23e90c Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Wed, 8 Jun 2022 13:51:12 +0400
Subject: Add intro and conclusion

---
 report/coursework.tex | 49 +++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 43 insertions(+), 6 deletions(-)

(limited to 'report/coursework.tex')

diff --git a/report/coursework.tex b/report/coursework.tex
index d29a699..dd9d275 100644
--- a/report/coursework.tex
+++ b/report/coursework.tex
@@ -10,7 +10,30 @@
 
 \intro
 
-Введение
+В 1859 году сэр Уильям Роуэн Гамильтон выпустил в продажу игру <<Путешествие
+вокруг света>>. От играющего требовалось обойти <<вокруг света>>, то есть найти
+такой обход рёбер додекаэдра, чтобы пройти через каждую вершину ровно один раз.
+
+К созданию этой головоломки его привело изучение додекаэдра, которое в свою
+очередь привело к введению в теорию графов такого понятия, как <<гамильтонов
+граф>>.
+
+Проверка произвольного графа на гамильтоновость представляет из себя задачу
+полного перебора всех возможных построений гамильтонова цикла, что является
+NP"=полной задачей, крайне неэффективной для вычисления.
+
+В связи с этим было предложено большое количество вариантов более эффективной
+проверки на гамильтоновость графов с наложением определённых условий. Например,
+одним из первых достаточных условий гамильтоновости графов было условие,
+предложеное Дираком в 1952 году. Оно является крайне эффективным для вычисления,
+но при этом позволяет определить менее 1\% гамильтоновых графов.
+
+Впоследствии были предложены условия Оре, Поша и Бонди"=Хватала, обобщающие
+условие Дирака и позволяющие определить большее количество гамильтоновых графов.
+
+В данной работе рассмотрены теоремы, основанные на понятии \textit{жёсткости},
+введённом Вацлавом Хваталом в 1973 году, а также их сравнение с указанными выше
+достаточными условиями гамильтоновости графов. 
 
 
 \section{Основные определения}
@@ -433,15 +456,29 @@ fn check_toughness(&self, t: f64) -> bool {
     вершинами;
 \end{itemize}
 
+
+\conclusion 
+
 Наиболее эффективным условием (по проценту определяемых графов), всё ещё
-остаётся условие Бонди"=Хватала. Хотя теоремы Бауэра и Бигалке"=Юнга на
-небольшом количестве вершин сравнимы с условием Поша, уже на 10 вершинах они
-значительно уступают данному условию.
+остаётся условие Бонди"=Хватала, которое позволяет установить гамильтоновость
+примерно 90\% графов.
 
+Хотя теоремы Бауэра и Бигалке"=Юнга на небольшом количестве вершин сравнимы с
+условием Поша, уже на 10 вершинах они значительно уступают данному условию.
+При этом, имея вычислительную сложность $O(2^n \cdot \log (n))$, они являются
+крайне неэффективными способами установления гамильтоновости графов.
 
-\conclusion 
+Так как алгоритм определения жёсткости работает за неполиномиальное время,
+достаточные условия гамильтоновости графов, основанные на этом определении,
+являются лишь небольшим улучшением по сравнению с обычным перебором различных
+вариантов построения гамильтонова цикла в графе, который также является
+NP"=полной задачей.
+
+Теорема Поша, с которой производилось сравнение Теорем \ref{thm:bigalke} и
+\ref{thm:bauer} является более подходящей для такой задачи, так как
+способна определять гамильтоновость более 25\% графов, при этом имея
+значительно более эффективную сложность $O(n + m)$.
 
-Заключение
 
 \bibliographystyle{gost780uv}
 \inputencoding{cp1251}
-- 
cgit v1.2.3

