From 2852df6b02f3e2e3b50dfc8ce267161a19870fd6 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Mon, 4 Mar 2024 10:30:42 +0400
Subject: init

---
 snk.tex | 179 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 179 insertions(+)
 create mode 100644 snk.tex

(limited to 'snk.tex')

diff --git a/snk.tex b/snk.tex
new file mode 100644
index 0000000..de435b6
--- /dev/null
+++ b/snk.tex
@@ -0,0 +1,179 @@
+\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}
-- 
cgit v1.2.3

