1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
\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}
|
