From 3b4759951c3d8f03166da1d26b37ba02b0e066f2 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Wed, 17 May 2023 12:27:32 +0400
Subject: Added theory for forbidden subgraphs

---
 report/forbidden.tex | 83 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 83 insertions(+)
 create mode 100644 report/forbidden.tex

(limited to 'report/forbidden.tex')

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}
+
-- 
cgit v1.2.3