diff options
Diffstat (limited to 'report')
| -rw-r--r-- | report/coursework.pdf | bin | 901992 -> 883263 bytes | |||
| -rw-r--r-- | report/coursework.tex | 59 | ||||
| -rw-r--r-- | report/forbidden.tex | 23 | ||||
| -rw-r--r-- | report/sources.bib | 2 |
4 files changed, 46 insertions, 38 deletions
diff --git a/report/coursework.pdf b/report/coursework.pdf Binary files differindex 820cb57..ec95e21 100644 --- a/report/coursework.pdf +++ b/report/coursework.pdf diff --git a/report/coursework.tex b/report/coursework.tex index c48e219..98a9f87 100644 --- a/report/coursework.tex +++ b/report/coursework.tex @@ -1,7 +1,8 @@ \documentclass[spec, och, coursework-kb]{SCWorks} \usepackage{preamble} -\title{Сравнение различных достаточных условий гамильтоновости графов} +\title{Жёсткость и запрещённые подграфы в достаточных условиях гамильтоновости +графов} \author{Гущина Андрея Юрьевича} % Фамилия, имя, отчество в родительном падеже \begin{document} @@ -32,8 +33,9 @@ NP"=полной задачей, крайне неэффективной для условие Дирака и позволяющие определить большее количество гамильтоновых графов. В данной работе рассмотрены теоремы, основанные на понятии \textit{жёсткости}, -введённом Вацлавом Хваталом в 1973 году, а также их сравнение с указанными выше -достаточными условиями гамильтоновости графов. +введённом Вацлавом Хваталом в 1973 году и теоремы, основанные на широко +используемой концепции \emph{запрещённых подграфов}, а также сравнение данных +теорем с указанными выше достаточными условиями гамильтоновости графов. \section{Основные определения} @@ -60,10 +62,10 @@ NP"=полной задачей, крайне неэффективной для \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)$. Если начальная и конечная вершины совпадают, то путь - называется циклическим. Путь, каждая вершина которого принадлежит не более чем - двум его рёбрам, считается простым. Если начальная вершина простого пути + $\dots$, $(v_{n - 1}, v_n)$, в которой $(v_{i - 1}, v_i) \in \alpha ~ (\forall + ~ 1 \leq i \leq n)$. Если начальная и конечная вершины совпадают, то путь + называется циклическим. Путь, каждая вершина которого принадлежит не более + чем двум его рёбрам, считается простым. Если начальная вершина простого пути совпадает с конечной, путь называют циклом, в противном случае – цепью. \end{definition} @@ -201,7 +203,7 @@ fn posa_theorem(g: &Graph) -> bool { условие $d(u) + d(v) \geq n$. \end{definition} -Можно заметить, что такой алгоритм построения такого замыкания имеет сложность +Можно заметить, что алгоритм построения такого замыкания имеет сложность $O(n^4)$. Немного изменённая версия этого алгоритма используется при построении гамильтонова цикла на основе нижеследующих теорем. @@ -282,10 +284,10 @@ m$ за $O(n)$ шагов. Тогда, цикл $C'$: u_1 u_{s + 1} u_{s + 2} \dots u_n u_s u_{s - 1} \dots u_1 \end{equation*} -Данную процедуру необходимо повторять до тех пор, пока не будет найден -гамильтонов цикл не будет найден. Так как $(\forall i, j) ~ a_{ij} \leq C_n^2$, -первоначальный цикл $C$ в замыкании $C_n(G)$ будет преобразован в гамильтонов -цикл в графе $G$ не более, чем за $O(n^3)$ шагов. +Данную процедуру необходимо повторять до тех пор, пока гамильтонов цикл не будет +найден. Так как $(\forall i, j) ~ a_{ij} \leq C_n^2$, первоначальный цикл $C$ в +замыкании $C_n(G)$ будет преобразован в гамильтонов цикл в графе $G$ не более, +чем за $O(n^3)$ шагов. \section{Достаточные условия, основанные на жёсткости} @@ -397,7 +399,7 @@ fn check_toughness(&self, t: f64) -> bool { В первую очередь необходимо посчитать количество графов с разным количеством вершин, отвечающих соответствующим достаточным условиям гамильтоновости. Для выполнения данной задачи была написана программа на языке программирования Rust, -которая указана в Приложении \ref{app:rust}. +которая указана в Приложениях \ref{app:rust1} -- \ref{app:rust6}. \subsection{Условия, основанные на жёсткости} @@ -485,7 +487,7 @@ fn check_toughness(&self, t: f64) -> bool { Абсолютные значения количества определяемых графов не представляют особой ценности, так как условие Бонди"=Хватала определило значительно большее -количество графов. Более полезными будут данные о разности графов, определяемых +количество графов. Более полезными будут данные о разности множеств графов, определяемых указанными теоремами с графами, определяемыми эталонной теоремой Бонди"=Хватала. В колонках таблицы \ref{tbl:forbidden-diff} указан размер множества графов, @@ -557,11 +559,26 @@ $|T_{BH} - (T_{BH} \cap T)|$, где $T_{BH}$ "--- множество графо вариантов построения гамильтонова цикла в графе, который также является NP"=полной задачей. -Теорема Поша, с которой производилось сравнение Теорем \ref{thm:bigalke} и +Теорема Поша, с которой производилось сравнение теорем \ref{thm:bigalke} и \ref{thm:bauer} является более подходящей для такой задачи, так как способна определять гамильтоновость более 25\% графов, при этом имея значительно более эффективную сложность $O(n + m)$. +Теоремы, основанные на запрещённых подграфах при этом позволяют определить +ещё меньшее количество графов по сравнению с другими рассмотренными теоремами. +Но при этом они позволяют определять некоторые из графов, которые не способна +определить теорема Бонди"=Хватала, которая является самой эффективной из +рассмотренных. + +Данные теоремы в основном представляют теоретический интерес, так как +рассматривают совершенно иной способ определения гамильтоновости для +произвольных графов. Хотя они являются достаточно неэффективными в смысле +вычислительной сложности, они всё же имеют полиномиальную сложность и поэтому +в некоторых случаях их можно использовать для проверки на гамильтоновость тех +графов, которые не способна определить теорема Бонди"=Хватала. Например, +такие теоремы позволяют распознать гамильтоновы графы с небольшим количеством +рёбер вокруг цикла. + \bibliographystyle{gost780uv} \inputencoding{cp1251} @@ -571,27 +588,27 @@ NP"=полной задачей. \appendix \section{Исходный код программы подсчёта графов на языке Rust, файл main.rs} -\label{app:rust} +\label{app:rust1} \inputminted{rust}{../graph-checker/src/main.rs} \section{Исходный код программы подсчёта графов на языке Rust, файл graph.rs} -\label{app:rust} +\label{app:rust2} \inputminted{rust}{../graph-checker/src/graph.rs} \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/basic.rs} -\label{app:rust} +\label{app:rust3} \inputminted{rust}{../graph-checker/src/theorems/basic.rs} \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/forbidden.rs} -\label{app:rust} +\label{app:rust4} \inputminted{rust}{../graph-checker/src/theorems/forbidden.rs} \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/toughness.rs} -\label{app:rust} +\label{app:rust5} \inputminted{rust}{../graph-checker/src/theorems/toughness.rs} \section{Исходный код программы подсчёта графов на языке Rust, файл theorems/mod.rs} -\label{app:rust} +\label{app:rust6} \inputminted{rust}{../graph-checker/src/theorems/mod.rs} diff --git a/report/forbidden.tex b/report/forbidden.tex index 4a37ab7..0091dbb 100644 --- a/report/forbidden.tex +++ b/report/forbidden.tex @@ -1,24 +1,15 @@ \section{Достаточные условия, основанные на запрещённых подграфах} Условия, представленные в данном разделе используют широко распространённую -концепцию запрещённых подграфов. Рассмотрим определение подграфа. -\begin{definition} - Подграфов графа $G = (V, \alpha)$ называется такой граф $G^* = (V^*, - \alpha^*)$, в котором $V^* \subseteq V, \alpha^* = \alpha \cap (V^* \times - V^*)$. То есть подграф состоит из некоторых вершин графа и \textbf{всех} - рёбер, соединяющих эти вершины в графе. - \label{def:subgraph} -\end{definition} - -Произвольный граф $G$ называют свободным от подграфа $H$ в том случае, если -ни один из подграфов графа $G$ не является изоморфным графу $H$. В общем -случае проверка на запрещённость подграфа является NP-полной задачей, так как -необходимо перебрать все подграфы и проверить их на изоморфность некоторому -другому подграфу. +концепцию запрещённых подграфов. Произвольный граф $G$ называют свободным от +подграфа $H$ в том случае, если ни один из подграфов графа $G$ не является +изоморфным графу $H$. В общем случае проверка на запрещённость подграфа является +NP-полной задачей, так как необходимо перебрать все подграфы и проверить их на +изоморфность некоторому другому подграфу. -Но есть возможность улучшения сложности данных проверок для графов, +Но есть возможность улучшения сложности проверок для графов, рассмотренных в данной работе с помощью алгоритма представленного в -статье \cite{hopcroft1974linear}, в которой представлен алгоритм проверки +статье \cite{hopcroft1974linear}, в которой описан алгоритм проверки изоморфизмов на планарных графах. Графы, рассмотренные в данной работе (рис. \ref{fig:forbidden}), очевидно планарные. В случае, если планарность графов не очевидна, существует линейный алгоритм проверки на планарность, представленный diff --git a/report/sources.bib b/report/sources.bib index adf3266..22c2e5d 100644 --- a/report/sources.bib +++ b/report/sources.bib @@ -110,7 +110,7 @@ @book{graph6, title={Description of graph6, sparse6 and digraph6 encodings [{} ]}, - note={URL:~\url{http://users.cecs.anu.edu.au/~bdm/data/formats.txt} ( 05.06.2022). . . . .}}, + note={URL:~\url{http://users.cecs.anu.edu.au/~bdm/data/formats.txt} ( 20.04.2023). . . . .}}, } @inproceedings{hopcroft1974linear, |