From b8ca36dc18ca8237d53bb4b39c71a4bf113fb000 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin@altlinux.org>
Date: Thu, 5 Sep 2024 14:54:31 +0400
Subject: =?UTF-8?q?=D0=9F=D0=BE=D1=87=D0=B8=D0=BD=D0=B8=D0=BB=20tex=20?=
 =?UTF-8?q?=D0=BF=D1=80=D0=BE=D0=B5=D0=BA=D1=82=20=D0=B4=D0=BB=D1=8F=20?=
 =?UTF-8?q?=D0=BA=D0=BE=D0=BC=D0=BF=D0=B8=D0=BB=D1=8F=D1=86=D0=B8=D0=B8=20?=
 =?UTF-8?q?=D1=87=D0=B5=D1=80=D0=B5=D0=B7=20tectonic?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 report/coursework.tex | 52 +++++++++++++++++++++++++--------------------------
 1 file changed, 26 insertions(+), 26 deletions(-)

(limited to 'report/coursework.tex')

diff --git a/report/coursework.tex b/report/coursework.tex
index 66edcfe..55f6620 100644
--- a/report/coursework.tex
+++ b/report/coursework.tex
@@ -33,7 +33,7 @@ NP"=полной задачей, крайне неэффективной для
 
 В данной работе рассмотрены теоремы, основанные на понятии \textit{жёсткости},
 введённом Вацлавом Хваталом в 1973 году, а также их сравнение с указанными выше
-достаточными условиями гамильтоновости графов. 
+достаточными условиями гамильтоновости графов.
 
 
 \section{Основные определения}
@@ -103,7 +103,7 @@ NP"=полной задачей, крайне неэффективной для
   / 2$, то граф $G$ "--- гамильтонов.
 \end{theorem}
 
-\begin{minted}{rust}
+\begin{Verbatim}
 fn dirac_theorem(g: &Graph) -> bool {
     for vertex in 0..g.size {
         if (g.degree(vertex) as f64) < g.size as f64 / 2.0 {
@@ -112,7 +112,7 @@ fn dirac_theorem(g: &Graph) -> bool {
     }
     return true;
 }
-\end{minted}
+\end{Verbatim}
 
 Вычислительная сложность данного алгоритма "--- $O(n + m)$.
 
@@ -123,7 +123,7 @@ fn dirac_theorem(g: &Graph) -> bool {
   гамильтонов.
 \end{theorem}
 
-\begin{minted}{rust}
+\begin{Verbatim}
 fn ore_theorem(g: &Graph) -> bool {
     for v1 in 0..g.size {
         for v2 in 0..g.size {
@@ -139,14 +139,14 @@ fn ore_theorem(g: &Graph) -> bool {
     }
     return true;
 }
-\end{minted}
+\end{Verbatim}
 
 \begin{theorem}[Поша, \cite{posa1963circuits}]
   \label{thm:posa}
   Если граф $G$ с числом вершин $n \geq 3$ и степенной последовательностью $d_1
   \leq \dots \leq d_n$ удовлетворяет следующим двум условиям, то он гамильтонов:
   \begin{enumerate}
-    \item 
+    \item
       для всякого $k: ~ 1 \leq k < \frac{n - 1}{2}$ число вершин со степенями
       меньшими или равными $k$ меньше, чем $k$;
     \item
@@ -155,7 +155,7 @@ fn ore_theorem(g: &Graph) -> bool {
   \end{enumerate}
 \end{theorem}
 
-\begin{minted}{rust}
+\begin{Verbatim}
 fn posa_theorem(g: &Graph) -> bool {
     let mut degrees = Vec::new();
     for v in 0..g.size {
@@ -192,7 +192,7 @@ fn posa_theorem(g: &Graph) -> bool {
     }
     return true;
 }
-\end{minted}
+\end{Verbatim}
 
 
 \begin{definition}
@@ -217,7 +217,7 @@ $O(n^4)$. Немного изменённая версия этого алгор
   гамильтонов.
 \end{theorem}
 
-\begin{minted}{rust}
+\begin{Verbatim}
 fn get_closure_traced(&self, trace_steps: bool) -> Graph {
     let mut step = if trace_steps { 2 } else { 1 };
 
@@ -245,7 +245,7 @@ fn get_closure_traced(&self, trace_steps: bool) -> Graph {
     }
     return closure;
 }
-\end{minted}
+\end{Verbatim}
 
 \subsection{Алгоритм нахождения гамильтонова цикла на основе условия Бонди"=Хватала}
 
@@ -257,11 +257,11 @@ fn get_closure_traced(&self, trace_steps: bool) -> Graph {
 смежности замыкания $C_k(G)$ по следующему алгоритму:
 \begin{enumerate}
   \item Установить $(\forall i) ~ D_i = \sum a_{ij}$. Установить $M = 2$.
-  \item 
+  \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$ и 
+    Заменить $a_{ij}$ и $a_{ji}$ на число $M$. Заменить $D_i$ на $D_i + 1$ и
     $D_j$ на $D_j + 1$. Заменить $M$ на $M + 1$. Перейти на шаг 2.
 \end{enumerate}
 
@@ -300,7 +300,7 @@ m$ за $O(n)$ шагов. Тогда, цикл $C'$:
 Для вычисления количества компонент графа можно использовать алгоритм поиска в
 глубину со сложностью $O(n + m)$.
 
-\begin{minted}{rust}
+\begin{Verbatim}
 fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) {
     visited[*vertex] = 1;
     for i in 0..self.size {
@@ -331,14 +331,14 @@ fn count_components_partial(&self, included_vertices: &Vec<i32>) -> usize {
     }
     return count;
 }
-\end{minted}
+\end{Verbatim}
 
 \begin{definition}
   Граф является $t$"=жёстким, если $(\forall ~ S \subseteq V(G) ~ : ~ \omega(G -
   S) > 1) ~ |S| \geq t \cdot \omega(G - S)$.
 \end{definition}
 
-\begin{minted}{rust}
+\begin{Verbatim}
 fn check_toughness(&self, t: f64) -> bool {
     for cutset in self.cutsets() {
         let components_count = cutset.graph.count_components_partial(&cutset.vertices) as f64;
@@ -349,7 +349,7 @@ fn check_toughness(&self, t: f64) -> bool {
     }
     return true;
 }
-\end{minted}
+\end{Verbatim}
 
 Можно заметить, что проверка графа на $t$"=жёсткость имеет сложность $O(2^n)$,
 что делает данные условия крайне неэффективными для проверки.
@@ -365,7 +365,7 @@ fn check_toughness(&self, t: f64) -> bool {
 сложность нахождения жёсткости имеет сложность $O(2^n \cdot \log (n))$
 
 Обозначим $\delta(G)$ "--- минимальную степень в графе $G$ и $\omega(G)$ "---
-количество компонент связности в графе $G$. 
+количество компонент связности в графе $G$.
 
 \begin{definition}
   Множество вершин называется независимым, если никакие две из них не смежны
@@ -399,7 +399,7 @@ fn check_toughness(&self, t: f64) -> bool {
 которая указана в Приложении \ref{app:rust}.
 
 \begin{table}[H]
-  \small    
+  \small
   \centering
   \caption{Количество графов, отвечающих рассмотренным теоремам}
   \begin{tabular}{|c|c|c|c|c|c|c|c|}
@@ -441,7 +441,7 @@ fn check_toughness(&self, t: f64) -> bool {
 Выполнив данную программу для графов размером до 8 вершин удалось установить
 несколько фактов об отношениях данных условий гамильтоновости:
 \begin{itemize}
-  \item 
+  \item
     Для графов размеров 3, 4, 5 графы Поша являются подмножеством как графов
     Бауэра, так и графов Бигалке"=Юнга. При этом, графы Поша дополнительно
     являются подмножеством графов Бигалке"=Юнга, но не Бауэра это связанно с
@@ -457,7 +457,7 @@ fn check_toughness(&self, t: f64) -> bool {
 \end{itemize}
 
 
-\conclusion 
+% \conclusion
 
 Наиболее эффективным условием (по проценту определяемых графов), всё ещё
 остаётся условие Бонди"=Хватала, которое позволяет установить гамильтоновость
@@ -480,19 +480,19 @@ NP"=полной задачей.
 значительно более эффективную сложность $O(n + m)$.
 
 
-\bibliographystyle{gost780uv}
-\inputencoding{cp1251}
-\bibliography{sources}
-\inputencoding{utf8}
+% \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}
+\VerbatimInput{../graph-checker/src/main.rs}
 
 \section{Исходный код программы сравнения множеств графов на языке Python}
 \label{app:python}
-\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{rust}{../checker.py}
+\VerbatimInput{../checker.py}
 
 \end{document}
-- 
cgit v1.2.3

