From fabbc86a41dad1b83e46c554e083a1df402b43f4 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Thu, 5 Sep 2024 14:54:31 +0400 Subject: feat: move project to compiling with tectonic typesetting Bibliography with bibtex for russian-language sources still needs to be fixed. --- report/coursework.tex | 50 ++++++++++++++++++++++++-------------------------- 1 file changed, 24 insertions(+), 26 deletions(-) (limited to 'report/coursework.tex') diff --git a/report/coursework.tex b/report/coursework.tex index 98a9f87..23d146e 100644 --- a/report/coursework.tex +++ b/report/coursework.tex @@ -105,7 +105,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 { @@ -114,7 +114,7 @@ fn dirac_theorem(g: &Graph) -> bool { } return true; } -\end{minted} +\end{Verbatim} Вычислительная сложность данного алгоритма "--- $O(n + m)$. @@ -125,7 +125,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 { @@ -141,14 +141,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 @@ -157,7 +157,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 { @@ -194,7 +194,7 @@ fn posa_theorem(g: &Graph) -> bool { } return true; } -\end{minted} +\end{Verbatim} \begin{definition} @@ -219,7 +219,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 }; @@ -247,7 +247,7 @@ fn get_closure_traced(&self, trace_steps: bool) -> Graph { } return closure; } -\end{minted} +\end{Verbatim} \subsection{Алгоритм нахождения гамильтонова цикла на основе условия Бонди"=Хватала} @@ -259,11 +259,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} @@ -302,7 +302,7 @@ m$ за $O(n)$ шагов. Тогда, цикл $C'$: Для вычисления количества компонент графа можно использовать алгоритм поиска в глубину со сложностью $O(n + m)$. -\begin{minted}{rust} +\begin{Verbatim} fn dfs(&self, vertex: &usize, visited: &mut Vec) { visited[*vertex] = 1; for i in 0..self.size { @@ -333,14 +333,14 @@ fn count_components_partial(&self, included_vertices: &Vec) -> 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; @@ -351,7 +351,7 @@ fn check_toughness(&self, t: f64) -> bool { } return true; } -\end{minted} +\end{Verbatim} Можно заметить, что проверка графа на $t$"=жёсткость имеет сложность $O(2^n)$, что делает данные условия крайне неэффективными для проверки. @@ -367,7 +367,7 @@ fn check_toughness(&self, t: f64) -> bool { сложность нахождения жёсткости имеет сложность $O(2^n \cdot \log (n))$ Обозначим $\delta(G)$ "--- минимальную степень в графе $G$ и $\omega(G)$ "--- -количество компонент связности в графе $G$. +количество компонент связности в графе $G$. \begin{definition} Множество вершин называется независимым, если никакие две из них не смежны @@ -446,7 +446,7 @@ fn check_toughness(&self, t: f64) -> bool { Выполнив данную программу для графов размером до 8 вершин удалось установить несколько фактов об отношениях данных условий гамильтоновости: \begin{itemize} - \item + \item Для графов размеров 3, 4, 5 графы Поша являются подмножеством как графов Бауэра, так и графов Бигалке"=Юнга. При этом, графы Поша дополнительно являются подмножеством графов Бигалке"=Юнга, но не Бауэра это связанно с @@ -581,39 +581,37 @@ NP"=полной задачей. \bibliographystyle{gost780uv} -\inputencoding{cp1251} \bibliography{sources} -\inputencoding{utf8} \appendix \section{Исходный код программы подсчёта графов на языке Rust, файл main.rs} \label{app:rust1} -\inputminted{rust}{../graph-checker/src/main.rs} +\VerbatimInput{../graph-checker/src/main.rs} \section{Исходный код программы подсчёта графов на языке Rust, файл graph.rs} \label{app:rust2} -\inputminted{rust}{../graph-checker/src/graph.rs} +\VerbatimInput{../graph-checker/src/graph.rs} \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/basic.rs} \label{app:rust3} -\inputminted{rust}{../graph-checker/src/theorems/basic.rs} +\VerbatimInput{../graph-checker/src/theorems/basic.rs} \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/forbidden.rs} \label{app:rust4} -\inputminted{rust}{../graph-checker/src/theorems/forbidden.rs} +\VerbatimInput{../graph-checker/src/theorems/forbidden.rs} \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/toughness.rs} \label{app:rust5} -\inputminted{rust}{../graph-checker/src/theorems/toughness.rs} +\VerbatimInput{../graph-checker/src/theorems/toughness.rs} \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/mod.rs} \label{app:rust6} -\inputminted{rust}{../graph-checker/src/theorems/mod.rs} +\VerbatimInput{../graph-checker/src/theorems/mod.rs} \section{Исходный код программы сравнения множеств графов на языке Python} \label{app:python} -\inputminted{python}{../checker.py} +\VerbatimInput{../checker.py} \end{document} -- cgit v1.2.3