13 files changed, 242 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..7a5a9f1
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,28 @@
+.*
+!.gitignore
+polygon
+
+# Rust
+target
+
+# Python
+venv
+
+# Latex auxillary files
+*.aux
+*.bbl
+*.blg
+*.fdb_latexmk
+*.fls
+*.log
+*.out
+*.gz
+*.toc
+*.dvi
+_minted-*
+
+# Beamer files
+*.bcf
+*.nav
+*.run.xml
+*.snm
diff --git a/01guschin.jpg b/01guschin.jpg
new file mode 100644
index 0000000..a94f53c
--- /dev/null
+++ b/01guschin.jpg
diff --git a/maker.sh b/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/maker.sh
@@ -0,0 +1,35 @@
+#!/bin/sh
+
+watch() {
+    [ -z "$1" ] && echo "Необходимо указать название основного документа" && help
+    set -o xtrace
+    latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1
+}
+
+doc() {
+    [ -z "$1" ] && echo "Необходимо указать название основного документа" && help
+    set -o xtrace
+    latexmk -pdf -f -shell-escape -interaction=nonstopmode $1
+}
+
+clean() {
+    set -o xtrace
+    rm -rf _minted-*
+    find . -name "*.aux" -exec rm {} \;
+    rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc
+}
+
+help() {
+    echo "Использование:"
+    echo "./maker.sh watch <main-doc>.tex -> Запуск процесса, пересобирающего документ при изменениях"
+    echo "./maker.sh doc <main-doc>.tex -> Пересобрать документ"
+    echo "./maker.sh clean -> Удаление сгенерированных файлов"
+    exit 1
+}
+
+case "$1" in
+    watch) watch $2 ;;
+    doc) doc $2 ;;
+    clean) clean ;;
+    *) help ;;
+esac
diff --git a/snk-images/A.png b/snk-images/A.png
new file mode 100644
index 0000000..141bdaa
--- /dev/null
+++ b/snk-images/A.png
diff --git a/snk-images/I.png b/snk-images/I.png
new file mode 100644
index 0000000..ec0764b
--- /dev/null
+++ b/snk-images/I.png
diff --git a/snk-images/K_1,3.png b/snk-images/K_1,3.png
new file mode 100644
index 0000000..0626654
--- /dev/null
+++ b/snk-images/K_1,3.png
diff --git a/snk-images/P_6.png b/snk-images/P_6.png
new file mode 100644
index 0000000..4e9a2ff
--- /dev/null
+++ b/snk-images/P_6.png
diff --git a/snk-images/n.png b/snk-images/n.png
new file mode 100644
index 0000000..152e7e7
--- /dev/null
+++ b/snk-images/n.png
diff --git a/snk-images/w.png b/snk-images/w.png
new file mode 100644
index 0000000..c2e5f82
--- /dev/null
+++ b/snk-images/w.png
diff --git a/snk-images/z1.png b/snk-images/z1.png
new file mode 100644
index 0000000..4b1837d
--- /dev/null
+++ b/snk-images/z1.png
diff --git a/snk-images/z2.png b/snk-images/z2.png
new file mode 100644
index 0000000..f782dc2
--- /dev/null
+++ b/snk-images/z2.png
diff --git a/snk.pdf b/snk.pdf
new file mode 100644
index 0000000..8ed5472
--- /dev/null
+++ b/snk.pdf
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}