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