diff options
Diffstat (limited to 'report')
| -rw-r--r-- | report/coursework.pdf | bin | 668187 -> 901992 bytes | |||
| -rw-r--r-- | report/coursework.tex | 124 | ||||
| -rw-r--r-- | report/forbidden.tex | 83 | ||||
| -rw-r--r-- | report/images/forbidden.jpg | bin | 0 -> 186501 bytes | |||
| -rw-r--r-- | report/preamble.sty | 3 | ||||
| -rw-r--r-- | report/sources.bib | 32 | ||||
| -rw-r--r-- | report/titlepage.tex | 4 |
7 files changed, 232 insertions, 14 deletions
diff --git a/report/coursework.pdf b/report/coursework.pdf Binary files differindex 6b3da27..820cb57 100644 --- a/report/coursework.pdf +++ b/report/coursework.pdf diff --git a/report/coursework.tex b/report/coursework.tex index 66edcfe..c48e219 100644 --- a/report/coursework.tex +++ b/report/coursework.tex @@ -288,7 +288,7 @@ m$ за $O(n)$ шагов. Тогда, цикл $C'$: цикл в графе $G$ не более, чем за $O(n^3)$ шагов. -\section{Достаточные условия гамильтоновости графов, основанные на жёсткости} +\section{Достаточные условия, основанные на жёсткости} Впервые понятие жёсткости было введено Вацлавом Хваталом в 1973 году. Впоследствии на основе данного понятия было доказано большое количество новых @@ -386,6 +386,7 @@ fn check_toughness(&self, t: f64) -> bool { неравенство $\delta \geq n / (t + 1) - 1$, то граф $G$ "--- гамильтонов. \end{theorem} +\input{forbidden.tex} \section{Вычислительный эксперимент} @@ -398,7 +399,14 @@ fn check_toughness(&self, t: f64) -> bool { выполнения данной задачи была написана программа на языке программирования Rust, которая указана в Приложении \ref{app:rust}. -\begin{table}[H] +\subsection{Условия, основанные на жёсткости} + +По результатам вычислений, указанных в таблице \ref{tbl:stats}, можно заметить, +что Теоремы \ref{thm:bigalke} и \ref{thm:bauer} по эффективности сравнимы с +теоремой \ref{thm:posa}, поэтому проведём более подробное сравнение графов, +отвечающих данным условиям. + +\begin{table}[ht] \small \centering \caption{Количество графов, отвечающих рассмотренным теоремам} @@ -417,11 +425,6 @@ fn check_toughness(&self, t: f64) -> bool { \label{tbl:stats} \end{table} -По результатам вычислений, указанных в таблице \ref{tbl:stats}, можно заметить, -что Теоремы \ref{thm:bigalke} и \ref{thm:bauer} по эффективности сравнимы с -теоремой \ref{thm:posa}, поэтому проведём более подробное сравнение графов, -отвечающих данным условиям. - Для этого была написана программа на языке программирования Python, считывающая вывод программы подсчёта количества графов (которая также выводит сами графы, отвечающие заданным условиям). Данная программа приведена в Приложении @@ -457,6 +460,86 @@ fn check_toughness(&self, t: f64) -> bool { \end{itemize} +\subsection{Условия, основанные на запрещённых подграфах} + +В таблице \ref{tbl:forbidden-full} указаны значения количества графов, которые +определяются каждой из рассмотренных в разделе с запрещёнными подграфами теорем. + +\begin{table}[ht] + \small + \centering + \caption{Количество определяемых гамильтоновых графов} + \begin{tabular}{|c|c| >{\centering}p{2.5cm} | >{\centering}p{2cm} | >{\centering}p{1.5cm}|c|c|} + \hline + $n$ & Бонди"=Хватал & Duffus"=Gould"=Jacobson & Broersma"=Veldman & Gould"=Jacobson & Bedrossian & Shepherd \\ \hline + 4 & 3 & 3 & 3 & 3 & 3 & 1 \\ \hline + 5 & 7 & 8 & 8 & 8 & 8 & 3 \\ \hline + 6 & 45 & 32 & 32 & 25 & 32 & 13 \\ \hline + 7 & 352 & 126 & 123 & 56 & 122 & 60 \\ \hline + 8 & 5540 & 605 & 578 & 133 & 554 & 359 \\ \hline + 9 & 157016 & 3148 & 2925 & 331 & 2723 & 2241 \\ \hline + 10 & 8298805 & 19296 & 17691 & 945 & 16446 & 15889 \\ \hline + \end{tabular} + \label{tbl:forbidden-full} +\end{table} + +Абсолютные значения количества определяемых графов не представляют особой +ценности, так как условие Бонди"=Хватала определило значительно большее +количество графов. Более полезными будут данные о разности графов, определяемых +указанными теоремами с графами, определяемыми эталонной теоремой Бонди"=Хватала. + +В колонках таблицы \ref{tbl:forbidden-diff} указан размер множества графов, +определяемый теоремой, соответствующей колонке. Данные вычислялись по формуле +$|T_{BH} - (T_{BH} \cap T)|$, где $T_{BH}$ "--- множество графов, определяемых +теоремой Бонди"=Хватала, $T$ "--- множество графов, определяемых теоремой, +указанной в колонке. +\begin{table}[ht] + \small + \centering + \caption{Разность условий с условием Бонди"=Хватала} + \begin{tabular}{|c|>{\centering}p{2.5cm} | >{\centering}p{2cm} | >{\centering}p{1.5cm}|c|c|} + \hline + $n$ & Duffus"=Gould"=Jacobson & Broersma"=Veldman & Gould"=Jacobson & Bedrossian & Shepherd \\ \hline + 4 & 0 & 0 & 0 & 0 & 0 \\ \hline + 5 & 1 & 1 & 1 & 1 & 0 \\ \hline + 6 & 2 & 2 & 1 & 2 & 0 \\ \hline + 7 & 11 & 8 & 2 & 8 & 0 \\ \hline + 8 & 42 & 18 & 1 & 11 & 1 \\ \hline + 9 & 203 & 52 & 3 & 34 & 14 \\ \hline + 10 & 879 & 89 & 2 & 46 & 67 \\ \hline + \end{tabular} + \label{tbl:forbidden-diff} +\end{table} + + +Также можно заметить, что первые четыре теоремы формулируются практически +одинаково, за исключением множества запрещённых подграфов. То есть, можно +объединить данные условия в одно и узнать сколько графов они способны определить +вместе. В таблицу \ref{tbl:forbidden-union} занесены данные о количестве +определённых графов объединением теорем \ref{thm:duffus-gould-jacobson}, +\ref{thm:broersma-veldman}, \ref{thm:gould-jacobson} и \ref{thm:bedrossian}. + +\begin{table}[H] + \small + \centering + \caption{Объединение теорем} + \begin{tabular}{|c|c|} + \hline + $n$ & Bedrossian, Broersma, Duffus, Gould, Jacobson, Veldman \\ \hline + 4 & 0 \\ \hline + 5 & 1 \\ \hline + 6 & 2 \\ \hline + 7 & 11 \\ \hline + 8 & 42 \\ \hline + 9 & 204 \\ \hline + 10 & 885 \\ \hline + \end{tabular} + \label{tbl:forbidden-union} +\end{table} + +Можно увидеть, что практически все графы из объединённой теоремы определяются +теоремой \ref{thm:duffus-gould-jacobson}. + \conclusion Наиболее эффективным условием (по проценту определяемых графов), всё ещё @@ -487,12 +570,33 @@ NP"=полной задачей. \appendix -\section{Исходный код программы подсчёта графов на языке Rust} +\section{Исходный код программы подсчёта графов на языке Rust, файл main.rs} \label{app:rust} -\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{rust}{../src/main.rs} +\inputminted{rust}{../graph-checker/src/main.rs} + +\section{Исходный код программы подсчёта графов на языке Rust, файл graph.rs} +\label{app:rust} +\inputminted{rust}{../graph-checker/src/graph.rs} + +\section{Исходный код программы подсчёта графов на языке Rust, файл theorems/basic.rs} +\label{app:rust} +\inputminted{rust}{../graph-checker/src/theorems/basic.rs} + +\section{Исходный код программы подсчёта графов на языке Rust, файл theorems/forbidden.rs} +\label{app:rust} +\inputminted{rust}{../graph-checker/src/theorems/forbidden.rs} + +\section{Исходный код программы подсчёта графов на языке Rust, файл theorems/toughness.rs} +\label{app:rust} +\inputminted{rust}{../graph-checker/src/theorems/toughness.rs} + +\section{Исходный код программы подсчёта графов на языке Rust, файл theorems/mod.rs} +\label{app:rust} +\inputminted{rust}{../graph-checker/src/theorems/mod.rs} + \section{Исходный код программы сравнения множеств графов на языке Python} \label{app:python} -\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{rust}{../checker.py} +\inputminted{python}{../checker.py} \end{document} diff --git a/report/forbidden.tex b/report/forbidden.tex new file mode 100644 index 0000000..4a37ab7 --- /dev/null +++ b/report/forbidden.tex @@ -0,0 +1,83 @@ +\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-полной задачей, так как +необходимо перебрать все подграфы и проверить их на изоморфность некоторому +другому подграфу. + +Но есть возможность улучшения сложности данных проверок для графов, +рассмотренных в данной работе с помощью алгоритма представленного в +статье \cite{hopcroft1974linear}, в которой представлен алгоритм проверки +изоморфизмов на планарных графах. Графы, рассмотренные в данной работе (рис. +\ref{fig:forbidden}), очевидно планарные. В случае, если планарность графов не +очевидна, существует линейный алгоритм проверки на планарность, представленный +в работе \cite{hopcroft1974efficient}. + +Также перед рассмотрением теорем необходимо ввести определение вершинной +$k$"=связности. +\begin{definition} + Произвольный граф $G$ является вершинно $k$"=связным (или просто + $k$"=связным), если он имеет больше чем $k$ вершин и после удаления менее чем + $k$ любых вершин граф остаётся связным. 2"=связный граф также можно назвать + двусвязным, а 3"=связный "--- трисвязным. +\end{definition} + +Рассмотрим сами теоремы с достаточными условиями. + +\begin{theorem}[Duffus"=Gould"=Jacobson, \cite{gould2003advances}] % 85 + Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3}, + N}$, то он также является гамильтоновым. + \label{thm:duffus-gould-jacobson} +\end{theorem} + +\begin{theorem}[Broersma"=Veldman, \cite{gould2003advances}] % 86 + Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3}, + P_6}$, то он также является гамильтоновым. + \label{thm:broersma-veldman} +\end{theorem} + +\begin{theorem}[Gould"=Jacobson, \cite{gould2003advances}] % 87 + Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3}, + Z_2}$, то он также является гамильтоновым. + \label{thm:gould-jacobson} +\end{theorem} + +\begin{theorem}[Bedrossian, \cite{gould2003advances}] % 88 + Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3}, + W}$, то он также является гамильтоновым. + \label{thm:bedrossian} +\end{theorem} + +Следующая теорема формулируется похожим образом на теорему +\ref{thm:duffus-gould-jacobson}, но при этом в результате получается +более сильное условие гамильтоновой связности. + +\begin{definition} + Произвольный граф $G$ называется гамильтоново"=связным в том случае, если + между любой парой его вершин существует гамильтонов путь. +\end{definition} + +\begin{theorem}[Shepherd, \cite{gould2003advances}] % 96 + Если граф $G$ является трисвязным и свободным от подграфов $\set{K_{1, 3}, + N}$, то он также является гамильтоново"=связным. + \label{thm:shepherd} +\end{theorem} + +\begin{figure}[ht] + \centering + \includegraphics[width=\textwidth]{forbidden} + \caption{Рассмотренные запрещённые подграфы} + \label{fig:forbidden} +\end{figure} + diff --git a/report/images/forbidden.jpg b/report/images/forbidden.jpg Binary files differnew file mode 100644 index 0000000..a94f53c --- /dev/null +++ b/report/images/forbidden.jpg diff --git a/report/preamble.sty b/report/preamble.sty index fc984ce..48a523c 100644 --- a/report/preamble.sty +++ b/report/preamble.sty @@ -22,6 +22,7 @@ \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsthm} +\usepackage{braket} \usepackage{fancyvrb} \usepackage{listings} \usepackage{listingsutf8} @@ -40,4 +41,4 @@ \newtheorem*{lemma*}{Лемма} \newtheorem*{example}{Пример} -\setminted[rust]{fontsize=\small, breaklines=true, style=bw, linenos} +\setminted{fontsize=\small, breaklines=true, style=bw, linenos} diff --git a/report/sources.bib b/report/sources.bib index 54399c3..adf3266 100644 --- a/report/sources.bib +++ b/report/sources.bib @@ -111,4 +111,34 @@ @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). . . . .}}, -}
\ No newline at end of file +} + +@inproceedings{hopcroft1974linear, + title={Linear time algorithm for isomorphism of planar graphs (preliminary report)}, + author={Hopcroft, John E and Wong, Jin-Kue}, + booktitle={Proceedings of the sixth annual ACM symposium on Theory of computing}, + pages={172--184}, + year={1974} +} + +@article{hopcroft1974efficient, + title={Efficient planarity testing}, + author={Hopcroft, John and Tarjan, Robert}, + journal={Journal of the ACM (JACM)}, + volume={21}, + number={4}, + pages={549--568}, + year={1974}, + publisher={ACM New York, NY, USA} +} + +@article{gould2003advances, + title={Advances on the Hamiltonian problem--a survey}, + author={Gould, Ronald J}, + journal={Graphs and Combinatorics}, + volume={19}, + number={1}, + pages={7--52}, + year={2003}, + publisher={Springer} +} diff --git a/report/titlepage.tex b/report/titlepage.tex index 8c88798..364d958 100644 --- a/report/titlepage.tex +++ b/report/titlepage.tex @@ -1,7 +1,7 @@ \selectlanguage{russian} \chair{теоретических основ компьютерной безопасности и криптографии} -\course{3} -\group{331} +\course{4} +\group{431} \department{факультета компьютерных наук и информационных технологий} \napravlenie{10.05.01 "--- Компьютерная безопасность} |
