\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}