\documentclass[14pt,a4paper,oneside]{extarticle}

\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}

\usepackage[
  a4paper, mag=1000,
  left=2.5cm, right=2.5cm,
  top=2.5cm, bottom=2.5cm,
]{geometry}

\usepackage[hidelinks,colorlinks=false]{hyperref}
\usepackage{url}
\usepackage{indentfirst}
\usepackage{tempora}
\usepackage{titlesec}
\usepackage{float}
\usepackage{graphicx}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{braket}

\usepackage{setspace}
\onehalfspacing

\newtheorem{theorem}{Теорема}
\newtheorem{corollary}{Заключение}

\titleformat{\section}
{\centering\normalfont\bfseries}
{\thesection}{1em}{}


\begin{document}

\begin{flushright}
  \textbf{А. Ю. Гущин}
\end{flushright}

\begin{center}
  СРАВНЕНИЕ ДОСТАТОЧНЫХ УСЛОВИЙ ГАМИЛЬТОНОВОСТИ ГРАФОВ НА ОСНОВЕ
  ЗАПРЕЩЁННЫХ ПОДГРАФОВ
\end{center}

\begin{center}
  Факультет Компьютерных Наук и Информационных технологий \\
  Научный руководитель: д.ф.-м.н., доцент \emph{М. Б. Абросимов}
\end{center}

Проверка произвольного графа на гамильтоновость представляет из себя задачу
полного перебора всех возможных построений гамильтонова цикла, что является
NP-полной задачей, крайне неэффективной для вычисления. Одно из наиболее
эффективных достаточных условий гамильтоновости графа было предложено в
1976 году математиками Бонди и Хваталом [1]. В данной работе рассмотрены
теоремы, основанные на достаточно широко распространённой концепции запрещённых
подграфов. Практическая эффективность этих условий исследуется путём сравнения с
условием Бонди-Хватала.

% \section{Исследуемые достаточные условия}

На рисунке \ref{fig:graphs} изображены графы, упоминаемые в следующих теоремах.

\begin{theorem}[{[2]}] % 85
  Всякий двусвязный граф $G$ свободный от подграфов $\set{K_{1, 3}, N}$ является гамильтоновым.
\end{theorem}

\begin{theorem}[{[2]}] % 86
  Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3},
  P_6}$, то он также является гамильтоновым.
\end{theorem}

\begin{theorem}[{[2]}] % 87
  Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3},
  Z_2}$, то он также является гамильтоновым.
\end{theorem}

\begin{theorem}[{[2]}] % 88
  Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3},
  W}$, то он также является гамильтоновым.
\end{theorem}

\begin{theorem}[{[2]}] % 96
  Если граф $G$ является трисвязным и свободным от подграфов $\set{K_{1, 3},
  N}$, то он также является гамильтоново-связным.
\end{theorem}

\begin{figure}[ht]
  \centering
  \includegraphics[width=0.9\textwidth]{01guschin.jpg}
  \caption{Графы $P_6$, $K_{1,3}$, $N$, $Z_2$, $W$}
  \label{fig:graphs}
\end{figure}


% \begin{theorem}[{[3]}] % 3.1
%   Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3},
%   Z_1}$, то он также является гамильтоновым.
% \end{theorem}

% \begin{theorem}[{[3]}] % 3.2
%   Всякий связный, локально связный, свободный от подграфов $K_{1, 3}$ граф
%   $G$ с количеством вершин $n \geq 3$ является гамильтоновым.
% \end{theorem}

% \begin{corollary}[{[3]}] % 3.5
%   Если граф $G$ является двусвязным и свободным от подграфов $K_{1, 3}$, то
%   \begin{enumerate}
%     \item если $G$ свободен от подграфов $I$, то он также является гамильтоновым;
%     \item если $G$ свободен от подграфов $A$, то он также является гамильтоновым.
%   \end{enumerate}
% \end{corollary}


% \section{Вычислительный эксперимент}

Для сравнения выбранных условий была разработана программа, проверяющая
условия для заданных графов. Графы генерировались с помощь программы geng из
пакета nauty [3]. Результаты занесены в таблицу \ref{tbl:res}.

% \begin{table}[H]
%   \centering
%   \caption{Результаты вычислительного эксперимента}
%   \begin{tabular}{|c|p{2cm}|c|c|c|c|c|c|c|c|}
%     \hline
%     $n$ & Т. Бонди-Хватала & Т1   & Т2   & Т3   & Т4   & Т5   & Т6   & Т7   & З1   \\ \hline
%     1   & 1      & 0    & 0    & 0    & 0    & 0    & 0    & 0    & 0    \\ \hline
%     2   & 1      & 2    & 2    & 2    & 2    & 0    & 2    & 0    & 2    \\ \hline
%     3   & 1      & 1    & 1    & 1    & 1    & 4    & 1    & 1    & 1    \\ \hline
%     4   & 3      & 3    & 3    & 3    & 3    & 1    & 3    & 2    & 3    \\ \hline
%     5   & 7      & 8    & 8    & 8    & 8    & 3    & 4    & 5    & 8    \\ \hline
%     6   & 45     & 32   & 32   & 25   & 32   & 13   & 5    & 18   & 29   \\ \hline
%     7   & 352    & 126  & 123  & 56   & 122  & 60   & 5    & 69   & 96   \\ \hline
%     8   & 5540   & 605  & 578  & 133  & 554  & 359  & 6    & 349  & 399  \\ \hline
%     9   & 157016 & 3148 & 2925 & 331  & 2723 & 2241 & 6    & 2049 & 1895 \\ \hline
%   \end{tabular}
% \end{table}

\begin{table}[H]
  \centering
  \footnotesize
  \caption{Результаты вычислительного эксперимента}
  \begin{tabular}{|c|c|c|c|c|c|c|}
    \hline
    $n$ & Т. Бонди-Хватала & Т1   & Т2   & Т3   & Т4   & Т5 \\ \hline
    1   & 1      & 0    & 0    & 0    & 0    & 0    \\ \hline
    2   & 1      & 2    & 2    & 2    & 2    & 0    \\ \hline
    3   & 1      & 1    & 1    & 1    & 1    & 4    \\ \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:res}
\end{table}

В результате выполнения вычислительного эксперимента удалось выяснить, что
указанные теоремы позволяют определить гамильтоновость графов, которые не
определяются с помощью условия Бонди-Хватала.

\begin{center}
  Библиографический список
\end{center}

\begin{enumerate}
  \item \emph{Bondy, J. A.} A method in graph theory / J. A. Bondy, V. Chvatal // \emph{Discrete Mathematics.} — 1976. — Vol. 15, no. 2. — Pp. 111–135.
  \item \emph{Gould, R. J.} Advances on the hamiltonian problem–a survey / R. J. Gould // \emph{Graphs and Combinatorics.} — 2003. — Vol. 19, no. 1. — Pp. 7–52.
  % \item \emph{Gould, R. J.} Updating the hamiltonian problema survey / R. J. Gould // \emph{Journal of Graph Theory.} — 1991. — Vol. 15, no. 2. — Pp. 121–157.
  \item \emph{McKay, B. D.} Practical graph isomorphism, ii / B. D. McKay, A. Piperno // \emph{Journal of symbolic computation.} — 2014. — Vol. 60. — Pp. 94–112.
\end{enumerate}

\end{document}
