Added theory for forbidden subgraphs

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}