Update documentclass and main definitions

4 files changed, 40 insertions, 33 deletions

diff --git a/report/coursework.pdf b/report/coursework.pdf
index a8eaae1..75df8f5 100644
--- a/report/coursework.pdf
+++ b/report/coursework.pdf
diff --git a/report/coursework.tex b/report/coursework.tex
index ab86834..d29a699 100644
--- a/report/coursework.tex
+++ b/report/coursework.tex
@@ -1,4 +1,4 @@
-\documentclass[spec, och, coursework]{SCWorks}
+\documentclass[spec, och, coursework-kb]{SCWorks}
 \usepackage{preamble}
 
 \title{Сравнение различных достаточных условий гамильтоновости графов}
@@ -17,36 +17,36 @@
 
 Рассмотрим основные определения, которые понадобятся при изучении достаточных
 условий гамильтоновости графов. Данные определения даются по работам
-\cite{Bogomolov_1997} и \cite{harary_1973}.
+\cite{Bogomolov_1997} и \cite{abrosimov2016graphs}.
 
 \begin{definition}
-  Неориентированным графом (или просто графом) называется пара $G = (V,
-  \alpha)$, где $V$ "--- конечное непустое множество (\textit{вершины} графа), а
-  $\alpha \subseteq V \times V$ "--- симметричное и антирефлексивное отношение
-  на множестве вершин $V$. Пара $(u, v) \in \alpha$ называется дугой графа с
-  началом $u$ и концом $v$.
+  Неориентированным графом (везде далее просто графом) называется пара $G = (V,
+  \alpha)$, где $\alpha$ "--- симметричное и антирефлексивное отношение на
+  множестве вершин $V$, называемое отношением смежности. Если $(u, v) \in a$, то
+  говорят, что вершины $u$ и $v$ смежны и эти вершины соединены ребром $(u, v)$.
+  При этом $(u, v)$ и $(v, u)$ это одно и то же ребро, которое обозначают $\{u,
+  v\}$. Говорят, что ребро $\{u, v\}$ инцидентно каждой из вершин $u$ и $v$ и
+  эти вершины называются концевыми вершинами или концами ребра $\{u, v\}$. Два
+  ребра называются смежными, если они имеют общую концевую вершину.
 \end{definition}
 
 \begin{definition}
   Граф называется полным, если любые две его вершины соединены ребром, т. е.
-  если $\alpha = (V \times V) = \Delta$.
+  если $\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)$. Циклический маршрут "--- это маршрут, в котором начальная и
-  конечная вершины совпадают. Маршрут, в котором никакая дуга не встречается
-  более одного раза, называется путём. Путь, каждая вершина которого принадлежит
-  не более, чем двум его дугам, по определению является простым. Простой
-  циклический путь называют контуром, а простой путь, не являющийся контуром
-  "--- бесконтурным путём или цепью.
+  Путём в графе называется последовательность дуг $(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}
@@ -66,6 +66,11 @@
   е. $\alpha^* = (V^* \times V^*) \cap \alpha$.
 \end{definition}
 
+\begin{definition}
+  Степенью вершины $v$ в неориентированном графе $G$ будем называть количество
+  вершин в $G$, смежных с $v$, и обозначать через $d(v)$.
+\end{definition}
+
 
 \section{Основные достаточные условия гамильтоновости графов}
 
@@ -173,7 +178,7 @@ fn posa_theorem(g: &Graph) -> bool {
   условие $d(u) + d(v) \geq n$.
 \end{definition}
 
-Можно заметить, что такое алгоритм построения такого замыкания имеет сложность
+Можно заметить, что такой алгоритм построения такого замыкания имеет сложность
 $O(n^4)$. Немного изменённая версия этого алгоритма используется при построении
 гамильтонова цикла на основе нижеследующих теорем.
 
@@ -269,10 +274,6 @@ m$ за $O(n)$ шагов. Тогда, цикл $C'$:
 \cite{bauer2006toughness}. Далее приведены две теоремы, основанные на понятии
 жёсткости, а также необходимые для этих теорем определения.
 
-\begin{definition}
-  $\omega(G)$ "--- количество компонент связности в графе $G$. 
-\end{definition}
-
 Для вычисления количества компонент графа можно использовать алгоритм поиска в
 глубину со сложностью $O(n + m)$.
 
@@ -335,14 +336,13 @@ fn check_toughness(&self, t: f64) -> bool {
   является $t$"=жёстким.
 \end{definition}
 
-Так как число $\tau$ является вещественным, и при этом монотонной и скачковой,
-его можно найти с помощью алгоритма бинарного поиска, имеющего сложность $O(\log
-(n))$. Вкупе с проверкой графа на $t$"=жёсткость, сложность нахождения жёсткости
-имеет сложность $O(2^n \cdot \log (n))$
+Так как функция жёсткости $\tau$ является вещественной, монотонной и скачковой,
+значение жёсткости графа можно найти с помощью алгоритма бинарного поиска,
+имеющего сложность $O(\log (n))$. Вкупе с проверкой графа на $t$"=жёсткость,
+сложность нахождения жёсткости имеет сложность $O(2^n \cdot \log (n))$
 
-\begin{definition}
-  $\delta(G)$ "--- минимальная степень в графе $G$.
-\end{definition}
+Обозначим $\delta(G)$ "--- минимальную степень в графе $G$ и $\omega(G)$ "---
+количество компонент связности в графе $G$. 
 
 \begin{definition}
   Множество вершин называется независимым, если никакие две из них не смежны
diff --git a/report/sources.bib b/report/sources.bib
index 6db2de9..8bb2d3b 100644
--- a/report/sources.bib
+++ b/report/sources.bib
@@ -93,6 +93,13 @@
   year={1963}
 }
 
+@article{abrosimov2016graphs,
+  title={������������ ������� �� ������},
+  author={���������, �� and ������, ��},
+  journal={�������: ������� �����.--2008},
+  year={2016}
+}
+
 @book{harary_1973,
   title={������ ������},
   author={������, �����},
diff --git a/report/titlepage.tex b/report/titlepage.tex
index ab3116a..84cd471 100644
--- a/report/titlepage.tex
+++ b/report/titlepage.tex
@@ -12,11 +12,11 @@
 % \studenttitle{Студентки}
 
 % Заведующий кафедрой
-\chtitle{д.ф.-м.н.} % степень, звание
+\chtitle{д.ф.-м.н., доцент} % степень, звание
 \chname{М.~Б.~Абросимов}
 
 %Научный руководитель (для реферата преподаватель проверяющий работу)
-\satitle{д.ф.-м.н.} %должность, степень, звание
+\satitle{д.ф.-м.н., доцент} %должность, степень, звание
 \saname{М.~Б.~Абросимов}
 
 % Руководитель практики от организации (только для практики,