diff options
Diffstat (limited to 'snk.tex')
| -rw-r--r-- | snk.tex | 179 |
1 files changed, 179 insertions, 0 deletions
@@ -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} |