diff options
Diffstat (limited to 'report/coursework.tex')
| -rw-r--r-- | report/coursework.tex | 52 |
1 files changed, 26 insertions, 26 deletions
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} |