\section{Достаточные условия, основанные на запрещённых подграфах}

Условия, представленные в данном разделе используют широко распространённую
концепцию запрещённых подграфов. Произвольный граф $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}