Added theory for forbidden subgraphs

8 files changed, 298 insertions, 14 deletions

diff --git a/graph-checker/src/theorems/forbidden.rs b/graph-checker/src/theorems/forbidden.rs
index 8c70916..9450b07 100644
--- a/graph-checker/src/theorems/forbidden.rs
+++ b/graph-checker/src/theorems/forbidden.rs
@@ -226,3 +226,69 @@ pub fn conjecture17(g: &Graph) -> bool {
 
     return g.is_4_connected() && g.is_free_of(&vec![claw]);
 }
+
+pub fn theorem_all_2con(g: &Graph) -> bool {
+    let claw = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 1, 1],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+        ],
+    };
+
+    let ng = Graph {
+        size: 6,
+        matrix: vec![
+            vec![0, 1, 1, 1, 0, 0],
+            vec![1, 0, 1, 0, 0, 1],
+            vec![1, 1, 0, 0, 1, 0],
+            vec![1, 0, 0, 0, 0, 0],
+            vec![0, 0, 1, 0, 0, 0],
+            vec![0, 1, 0, 0, 0, 0],
+        ],
+    };
+
+    let p6 = Graph {
+        size: 6,
+        matrix: vec![
+            vec![0, 1, 0, 0, 0, 0],
+            vec![1, 0, 1, 0, 0, 0],
+            vec![0, 1, 0, 1, 0, 0],
+            vec![0, 0, 1, 0, 1, 0],
+            vec![0, 0, 0, 1, 0, 1],
+            vec![0, 0, 0, 0, 1, 0],
+        ],
+    };
+
+    let z2 = Graph {
+        size: 5,
+        matrix: vec![
+            vec![0, 1, 0, 0, 0],
+            vec![1, 0, 1, 0, 0],
+            vec![0, 1, 0, 1, 1],
+            vec![0, 0, 1, 0, 1],
+            vec![0, 0, 1, 1, 1],
+        ],
+    };
+
+    let wg = Graph {
+        size: 6,
+        matrix: vec![
+            vec![0, 1, 1, 0, 0, 0],
+            vec![1, 0, 1, 0, 1, 0],
+            vec![1, 1, 0, 1, 0, 0],
+            vec![0, 0, 1, 0, 0, 0],
+            vec![0, 1, 0, 0, 0, 1],
+            vec![0, 0, 0, 0, 1, 0],
+        ],
+    };
+
+    return g.is_2_connected()
+        && g.is_free_of(&vec![claw])
+        && (g.is_free_of(&vec![ng])
+            || g.is_free_of(&vec![p6])
+            || g.is_free_of(&vec![z2])
+            || g.is_free_of(&vec![wg]));
+}
diff --git a/report/coursework.pdf b/report/coursework.pdf
index 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
new 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 "--- Компьютерная безопасность}