path: root/report/coursework.tex

\documentclass[spec, och, coursework-kb]{SCWorks}
\usepackage{preamble}

\title{Жёсткость и запрещённые подграфы в достаточных условиях гамильтоновости
графов}
\author{Гущина Андрея Юрьевича} % Фамилия, имя, отчество в родительном падеже

\begin{document}
\input{titlepage.tex}
\tableofcontents

\intro

В 1859 году сэр Уильям Роуэн Гамильтон выпустил в продажу игру <<Путешествие
вокруг света>>. От играющего требовалось обойти <<вокруг света>>, то есть найти
такой обход рёбер додекаэдра, чтобы пройти через каждую вершину ровно один раз.

К созданию этой головоломки его привело изучение додекаэдра, которое в свою
очередь привело к введению в теорию графов такого понятия, как <<гамильтонов
граф>>.

Проверка произвольного графа на гамильтоновость представляет из себя задачу
полного перебора всех возможных построений гамильтонова цикла, что является
NP"=полной задачей, крайне неэффективной для вычисления.

В связи с этим было предложено большое количество вариантов более эффективной
проверки на гамильтоновость графов с наложением определённых условий. Например,
одним из первых достаточных условий гамильтоновости графов было условие,
предложеное Дираком в 1952 году. Оно является крайне эффективным для вычисления,
но при этом позволяет определить менее 1\% гамильтоновых графов.

Впоследствии были предложены условия Оре, Поша и Бонди"=Хватала, обобщающие
условие Дирака и позволяющие определить большее количество гамильтоновых графов.

В данной работе рассмотрены теоремы, основанные на понятии \textit{жёсткости},
введённом Вацлавом Хваталом в 1973 году и теоремы, основанные на широко
используемой концепции \emph{запрещённых подграфов}, а также сравнение данных
теорем с указанными выше достаточными условиями гамильтоновости графов.


\section{Основные определения}

Рассмотрим основные определения, которые понадобятся при изучении достаточных
условий гамильтоновости графов. Данные определения даются по работам
\cite{Bogomolov_1997} и \cite{abrosimov2016graphs}.

\begin{definition}
  Неориентированным графом (везде далее просто графом) называется пара $G = (V,
  \alpha)$, где $\alpha$ "--- симметричное и антирефлексивное отношение на
  множестве вершин $V$, называемое отношением смежности. Если $(u, v) \in a$, то
  говорят, что вершины $u$ и $v$ смежны и эти вершины соединены ребром $(u, v)$.
  При этом $(u, v)$ и $(v, u)$ это одно и то же ребро, которое обозначают $\{u,
  v\}$. Говорят, что ребро $\{u, v\}$ инцидентно каждой из вершин $u$ и $v$ и
  эти вершины называются концевыми вершинами или концами ребра $\{u, v\}$. Два
  ребра называются смежными, если они имеют общую концевую вершину.
\end{definition}

\begin{definition}
  Граф называется полным, если любые две его вершины соединены ребром, т. е.
  если $\alpha = (V \times V) - \Delta$.
\end{definition}

\begin{definition}
  Путём в графе называется последовательность дуг $(v_0, v_1)$, $(v_1, v_2)$,
  $\dots$, $(v_{n - 1}, v_n)$, в которой $(v_{i - 1}, v_i) \in \alpha ~ (\forall
  ~ 1 \leq i \leq n)$. Если начальная и конечная вершины совпадают, то путь
  называется циклическим. Путь, каждая вершина которого принадлежит не более
  чем двум его рёбрам, считается простым. Если начальная вершина простого пути
  совпадает с конечной, путь называют циклом, в противном случае – цепью.
\end{definition}

\begin{definition}
  Цикл или цепь, содержащие все вершины графа, называются гамильтоновыми. Граф,
  содержащий гамильтонов цикл, также называется гамильтоновым.
\end{definition}

\begin{definition}
  Вершины $u$ и $v$ графа $G$ называются связанными, если в $G$ существует
  проходящий через них путь. Классы эквивалентности отношения связности
  называются компонентами связности (или просто компонентами) графа.
\end{definition}

\begin{definition}
  Частью графа называется граф $G^* = (V^*, \alpha^*)$, где $V^* \subseteq V$ и
  $\alpha^* \subseteq (V^* \times V^*) \cap \alpha$.
\end{definition}

\begin{definition}
  Подграф графа $G$ "--- это такая его часть $G^* = (V^*, \alpha^*)$, которая
  содержит все дуги графа $G$, соединяющие попавшие в данную часть вершины, т.
  е. $\alpha^* = (V^* \times V^*) \cap \alpha$.
\end{definition}

\begin{definition}
  Степенью вершины $v$ в неориентированном графе $G$ будем называть количество
  вершин в $G$, смежных с $v$, и обозначать через $d(v)$.
\end{definition}


\section{Основные достаточные условия гамильтоновости графов}

\begin{theorem}[Дирак, \cite{dirac1952some}]
  \label{thm:dirac}
  Если в графе $G$ с числом вершин $n \geq 3$ степень любой вершины $d(u) \geq n
  / 2$, то граф $G$ "--- гамильтонов.
\end{theorem}

\begin{minted}{rust}
fn dirac_theorem(g: &Graph) -> bool {
    for vertex in 0..g.size {
        if (g.degree(vertex) as f64) < g.size as f64 / 2.0 {
            return false;
        }
    }
    return true;
}
\end{minted}

Вычислительная сложность данного алгоритма "--- $O(n + m)$.

\begin{theorem}[Оре, \cite{ore1960note}]
  \label{thm:ore}
  Если в графе $G$ с числом вершин $n \geq 3$ для любых двух несмежных вершин
  $u$ и $v$ выполняется неравенство $d(u) + d(v) \geq n$, то граф $G$ "---
  гамильтонов.
\end{theorem}

\begin{minted}{rust}
fn ore_theorem(g: &Graph) -> bool {
    for v1 in 0..g.size {
        for v2 in 0..g.size {
            if v1 == v2 || g.matrix[v1][v2] != 0 {
                continue;
            }
            let d1 = g.degree(v1);
            let d2 = g.degree(v2);
            if d1 + d2 < g.size {
                return false;
            }
        }
    }
    return true;
}
\end{minted}

\begin{theorem}[Поша, \cite{posa1963circuits}]
  \label{thm:posa}
  Если граф $G$ с числом вершин $n \geq 3$ и степенной последовательностью $d_1
  \leq \dots \leq d_n$ удовлетворяет следующим двум условиям, то он гамильтонов:
  \begin{enumerate}
    \item 
      для всякого $k: ~ 1 \leq k < \frac{n - 1}{2}$ число вершин со степенями
      меньшими или равными $k$ меньше, чем $k$;
    \item
      для нечётного $n$ число вершин со степенями меньшими или равными $\frac{n
      - 1}{2}$ не превосходит ${n - 1}{2}$.
  \end{enumerate}
\end{theorem}

\begin{minted}{rust}
fn posa_theorem(g: &Graph) -> bool {
    let mut degrees = Vec::new();
    for v in 0..g.size {
        degrees.push(g.degree(v));
    }

    let end = if g.size % 2 == 0 {
        g.size / 2
    } else {
        (g.size - 1) / 2
    };

    for k in 1..end {
        let mut cnt = 0;
        for d in &degrees {
            if *d <= k {
                cnt += 1;
            }
        }
        if cnt >= k {
            return false;
        }
    }
    if g.size % 2 != 0 {
        let mut cnt = 0;
        for d in &degrees {
            if *d <= end {
                cnt += 1;
            }
        }
        if cnt > end {
            return false;
        }
    }
    return true;
}
\end{minted}


\begin{definition}
  Замыкание $[G]$ $n$"=вершинного графа $G$ получается из графа $G$ добавлением
  рёбер $\{ u, v \}$ для всех пар вершин $u$ и $v$, для которых выполняется
  условие $d(u) + d(v) \geq n$.
\end{definition}

Можно заметить, что алгоритм построения такого замыкания имеет сложность
$O(n^4)$. Немного изменённая версия этого алгоритма используется при построении
гамильтонова цикла на основе нижеследующих теорем.

\begin{theorem}[Бонди"=Хватал, \cite{bondy1976method}]
  \label{thm:bondy-chvatal-1}
  Граф $G$ является гамильтоновым тогда и только тогда, когда его замыкание
  $[G]$ является гамильтоновым.
\end{theorem}

\begin{theorem}[Бонди"=Хватал, \cite{bondy1976method}]
  \label{thm:bondy-chvatal-2}
  Если замыкание $[G]$ графа $G$ является полным графом, то граф $G$ "---
  гамильтонов.
\end{theorem}

\begin{minted}{rust}
fn get_closure_traced(&self, trace_steps: bool) -> Graph {
    let mut step = if trace_steps { 2 } else { 1 };

    let mut closure = self.clone();
    for _ in 0..(closure.size * closure.size) {
        let mut changed = false;
        for row in 0..closure.size {
            for col in 0..closure.size {
                if row == col || closure.matrix[row][col] != 0 {
                    continue;
                }
                let sum = closure.degree(row) + closure.degree(col);
                if sum >= closure.size {
                    closure.matrix[row][col] = step;
                    if trace_steps {
                        step += 1;
                    }
                    changed = true;
                }
            }
        }
        if !changed {
            break;
        }
    }
    return closure;
}
\end{minted}

\subsection{Алгоритм нахождения гамильтонова цикла на основе условия Бонди"=Хватала}

В том случае, если некоторый граф $G = (V, \alpha)$ отвечает теореме
\ref{thm:bondy-chvatal-2}, то к нему можно применить алгоритм нахождения
гамильтонова цикла со сложностью $O(n^3)$.

Пусть $A = (a_{ij})$ "--- матрица смежности графа $G$. Построим матрицу
смежности замыкания $C_k(G)$ по следующему алгоритму:
\begin{enumerate}
  \item Установить $(\forall i) ~ D_i = \sum a_{ij}$. Установить $M = 2$.
  \item 
    Находится некоторая пара $(i, j)$, где $i \neq j, a_{ij} = 0 \land D_i + D_j
    \geq k$. Если такая пара не может быть найдена, то остановить алгоритм.
  \item
    Заменить $a_{ij}$ и $a_{ji}$ на число $M$. Заменить $D_i$ на $D_i + 1$ и 
    $D_j$ на $D_j + 1$. Заменить $M$ на $M + 1$. Перейти на шаг 2.
\end{enumerate}

Обозначим множество вершин графа как $V(G)$, а множество рёбер как $E(G)$.

При завершении алгоритма получаем матрицу смежности $A = (a_{ij})$, в которой
$a_{ij} = 1 \iff ij \in E(G)$ и $a_{ij} = 0 \iff ij \not\in E(C_k(G))$. Далее,
возьмём некоторый гамильтонов цикл $C: ~ u_1 u_2 \dots u_n u_1$ в замыкании
$C_k(G)$. Так как по условию теоремы, это замыкание полное, то можно взять любой
набор вершин графа. Обозначим $m$ равным максимальному значению $a_{ij}$ среди
всех рёбер цикла $C$. Если $m > 1$, то ребро с таким значением уникально. Если
$m = 1$, то цикл $C$ является искомым гамильтоновым циклом в графе $G$. Пусть
ребро у которого $a_{ij} = m$ "--- это $u_1 u_n$. Тогда построить новый цикл
$C'$ такой, что максимальное значение $a_{ij}$ среди его рёбер меньше, чем $m$.
Найдём вершину $u_s$ такую, что $0 < a_{u_1 u_{s + 1}} < m$ и $0 < a_{u_n u_s} <
m$ за $O(n)$ шагов. Тогда, цикл $C'$:
\begin{equation*}
  u_1 u_{s + 1} u_{s + 2} \dots u_n u_s u_{s - 1} \dots u_1
\end{equation*}

Данную процедуру необходимо повторять до тех пор, пока гамильтонов цикл не будет
найден. Так как $(\forall i, j) ~ a_{ij} \leq C_n^2$, первоначальный цикл $C$ в
замыкании $C_n(G)$ будет преобразован в гамильтонов цикл в графе $G$ не более,
чем за $O(n^3)$ шагов.


\section{Достаточные условия, основанные на жёсткости}

Впервые понятие жёсткости было введено Вацлавом Хваталом в 1973 году.
Впоследствии на основе данного понятия было доказано большое количество новых
достаточных условий гамильтоновости графов. Например, в 2006 году было проведено
обширное исследование таких условий с результатами от разных авторов
\cite{bauer2006toughness}. Далее приведены две теоремы, основанные на понятии
жёсткости, а также необходимые для этих теорем определения.

Для вычисления количества компонент графа можно использовать алгоритм поиска в
глубину со сложностью $O(n + m)$.

\begin{minted}{rust}
fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) {
    visited[*vertex] = 1;
    for i in 0..self.size {
        if visited[i] == 0 && self.matrix[*vertex][i] != 0 {
            self.dfs(&i, visited);
        }
    }
}

fn count_components_partial(&self, included_vertices: &Vec<i32>) -> usize {
    let mut visited = vec![0; self.size];
    for i in 0..included_vertices.len() {
        if included_vertices[i] == 0 {
            visited[i] = 1;
        }
    }
    let mut count = 0;
    while visited.iter().sum::<usize>() != visited.len() {
        let mut next = 0;
        for i in 0..self.size {
            if visited[i] == 0 {
                next = i;
                break;
            }
        }
        self.dfs(&next, &mut visited);
        count += 1;
    }
    return count;
}
\end{minted}

\begin{definition}
  Граф является $t$"=жёстким, если $(\forall ~ S \subseteq V(G) ~ : ~ \omega(G -
  S) > 1) ~ |S| \geq t \cdot \omega(G - S)$.
\end{definition}

\begin{minted}{rust}
fn check_toughness(&self, t: f64) -> bool {
    for cutset in self.cutsets() {
        let components_count = cutset.graph.count_components_partial(&cutset.vertices) as f64;
        let cut_cardinality = (self.size - cutset.cardinality) as f64;
        if components_count > 1.0 && cut_cardinality < t * components_count {
            return false;
        }
    }
    return true;
}
\end{minted}

Можно заметить, что проверка графа на $t$"=жёсткость имеет сложность $O(2^n)$,
что делает данные условия крайне неэффективными для проверки.

\begin{definition}
  Жёсткость $\tau(G)$ "--- максимальное значение $t$, для которого граф $G$
  является $t$"=жёстким.
\end{definition}

Так как функция жёсткости $\tau$ является вещественной, монотонной и скачковой,
значение жёсткости графа можно найти с помощью алгоритма бинарного поиска,
имеющего сложность $O(\log (n))$. Вкупе с проверкой графа на $t$"=жёсткость,
сложность нахождения жёсткости имеет сложность $O(2^n \cdot \log (n))$

Обозначим $\delta(G)$ "--- минимальную степень в графе $G$ и $\omega(G)$ "---
количество компонент связности в графе $G$. 

\begin{definition}
  Множество вершин называется независимым, если никакие две из них не смежны
  \cite{harary_1973}. Обозначим мощность максимального множества независимых
  вершин графа $G$ как $\alpha(G)$.
\end{definition}

\begin{theorem}[Бигалке"=Юнг, \cite{bigalke1979hamiltonsche}]
  \label{thm:bigalke}
  Если для 1"=жёсткого графа $G$ с числом вершин $n \geq 3$ выполняется
  неравенство $\delta \geq \max \{ n / 3, \alpha - 1 \}$, то граф $G$ "---
  гамильтонов.
\end{theorem}

\begin{theorem}[Бауэр, \cite{bauer1995long}]
  \label{thm:bauer}
  Если для $t$"=жёсткого графа $G$ с числом вершин $n \geq 3$ выполняется
  неравенство $\delta \geq n / (t + 1) - 1$, то граф $G$ "--- гамильтонов.
\end{theorem}

\input{forbidden.tex}

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

Для произведения вычислительного эксперимента была использована программа
\verb|geng| из пакета \verb|nauty| \cite{mckay2014practical} для генерации
графов в формате \verb|graph6| \cite{graph6}.

В первую очередь необходимо посчитать количество графов с разным количеством
вершин, отвечающих соответствующим достаточным условиям гамильтоновости. Для
выполнения данной задачи была написана программа на языке программирования Rust,
которая указана в Приложениях \ref{app:rust1} -- \ref{app:rust6}.

\subsection{Условия, основанные на жёсткости}

По результатам вычислений, указанных в таблице \ref{tbl:stats}, можно заметить,
что Теоремы \ref{thm:bigalke} и \ref{thm:bauer} по эффективности сравнимы с
теоремой \ref{thm:posa}, поэтому проведём более подробное сравнение графов,
отвечающих данным условиям.

\begin{table}[ht]
  \small    
  \centering
  \caption{Количество графов, отвечающих рассмотренным теоремам}
  \begin{tabular}{|c|c|c|c|c|c|c|c|}
    \hline
    $n$ & Всего     & Дирак  & Оре    & Поша    & Бонди"=Хватал & Бигалке"=Юнг & Бауэр   \\ \hline
    3   & 4         & 1      & 1      & 1       & 1             & 1            & 1       \\ \hline
    4   & 11        & 3      & 3      & 3       & 3             & 3            & 3       \\ \hline
    5   & 34        & 3      & 5      & 6       & 7             & 8            & 10      \\ \hline
    6   & 156       & 19     & 21     & 31      & 45            & 48           & 19      \\ \hline
    7   & 1044      & 29     & 68     & 190     & 352           & 145          & 145     \\ \hline
    8   & 12346     & 424    & 503    & 2484    & 5540          & 2553         & 2047    \\ \hline
    9   & 274668    & 1165   & 4942   & 53492   & 157016        & 83481        & 59395   \\ \hline
    10  & 12005168  & 108376 & 128361 & 2683649 & 8298805       & 1249871      & 1245462 \\ \hline
  \end{tabular}
  \label{tbl:stats}
\end{table}

Для этого была написана программа на языке программирования Python, считывающая
вывод программы подсчёта количества графов (которая также выводит сами графы,
отвечающие заданным условиям). Данная программа приведена в Приложении
\ref{app:python}.

С помощью этой программы можно проверить пересечения и разности разных
комбинаций множеств графов Поша, графов Бауэра и графов Бигалке"=Юнга (рис.
\ref{fig:checker-py}).

\begin{figure}[ht]
  \centering
  \includegraphics[width=0.7\textwidth]{python_runner.png}
  \caption{Пример вывода программы checker.py}
  \label{fig:checker-py}
\end{figure}

Выполнив данную программу для графов размером до 8 вершин удалось установить
несколько фактов об отношениях данных условий гамильтоновости:
\begin{itemize}
  \item 
    Для графов размеров 3, 4, 5 графы Поша являются подмножеством как графов
    Бауэра, так и графов Бигалке"=Юнга. При этом, графы Поша дополнительно
    являются подмножеством графов Бигалке"=Юнга, но не Бауэра это связанно с
    тем, что при 6 вершинах графов Бауэра меньше, чем графов Поша. В данном
    случае, наоборот, Графы Бауэра являются подмножеством графов Поша;
  \item
    Пересечения множеств графов Поша \& графов Бауэра совпадают с
    пересечениями графов Поша \& графов Бигалке"=Юнга вплоть до
    графов с 8 вершинами, кроме случая с 6 вершинами;
  \item
    Графы Бигалке"=Юнга с 7 вершинами совпадают с графами Бауэра с 7
    вершинами;
\end{itemize}


\subsection{Условия, основанные на запрещённых подграфах}

В таблице \ref{tbl:forbidden-full} указаны значения количества графов, которые
определяются каждой из рассмотренных в разделе с запрещёнными подграфами теорем.

\begin{table}[ht]
  \small
  \centering
  \caption{Количество определяемых гамильтоновых графов}
  \begin{tabular}{|c|c| >{\centering}p{2.5cm} | >{\centering}p{2cm} | >{\centering}p{1.5cm}|c|c|}
    \hline
    $n$ & Бонди"=Хватал & Duffus"=Gould"=Jacobson   & Broersma"=Veldman   & Gould"=Jacobson   & Bedrossian   & Shepherd \\ \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:forbidden-full}
\end{table}

Абсолютные значения количества определяемых графов не представляют особой
ценности, так как условие Бонди"=Хватала определило значительно большее
количество графов. Более полезными будут данные о разности множеств графов, определяемых
указанными теоремами с графами, определяемыми эталонной теоремой Бонди"=Хватала.

В колонках таблицы \ref{tbl:forbidden-diff} указан размер множества графов,
определяемый теоремой, соответствующей колонке. Данные вычислялись по формуле
$|T_{BH} - (T_{BH} \cap T)|$, где $T_{BH}$ "--- множество графов, определяемых
теоремой Бонди"=Хватала, $T$ "--- множество графов, определяемых теоремой,
указанной в колонке.
\begin{table}[ht]
  \small
  \centering
  \caption{Разность условий с условием Бонди"=Хватала}
  \begin{tabular}{|c|>{\centering}p{2.5cm} | >{\centering}p{2cm} | >{\centering}p{1.5cm}|c|c|}
    \hline
    $n$ & Duffus"=Gould"=Jacobson   & Broersma"=Veldman   & Gould"=Jacobson   & Bedrossian   & Shepherd \\ \hline
    4   & 0     & 0     & 0    & 0     & 0  \\ \hline
    5   & 1     & 1     & 1    & 1     & 0  \\ \hline
    6   & 2     & 2     & 1    & 2     & 0  \\ \hline
    7   & 11    & 8     & 2    & 8     & 0  \\ \hline
    8   & 42    & 18    & 1    & 11    & 1  \\ \hline
    9   & 203   & 52    & 3    & 34    & 14 \\ \hline
    10  & 879   & 89    & 2    & 46    & 67 \\ \hline
  \end{tabular}
  \label{tbl:forbidden-diff}
\end{table}


Также можно заметить, что первые четыре теоремы формулируются практически
одинаково, за исключением множества запрещённых подграфов. То есть, можно
объединить данные условия в одно и узнать сколько графов они способны определить
вместе. В таблицу \ref{tbl:forbidden-union} занесены данные о количестве
определённых графов объединением теорем \ref{thm:duffus-gould-jacobson},
\ref{thm:broersma-veldman}, \ref{thm:gould-jacobson} и \ref{thm:bedrossian}.

\begin{table}[H]
  \small
  \centering
  \caption{Объединение теорем}
  \begin{tabular}{|c|c|}
    \hline
    $n$ & Bedrossian, Broersma, Duffus, Gould, Jacobson, Veldman \\ \hline
    4   & 0    \\ \hline
    5   & 1    \\ \hline
    6   & 2    \\ \hline
    7   & 11   \\ \hline
    8   & 42   \\ \hline
    9   & 204  \\ \hline
    10  & 885  \\ \hline
  \end{tabular}
  \label{tbl:forbidden-union}
\end{table}

Можно увидеть, что практически все графы из объединённой теоремы определяются
теоремой \ref{thm:duffus-gould-jacobson}.

\conclusion 

Наиболее эффективным условием (по проценту определяемых графов), всё ещё
остаётся условие Бонди"=Хватала, которое позволяет установить гамильтоновость
примерно 90\% графов.

Хотя теоремы Бауэра и Бигалке"=Юнга на небольшом количестве вершин сравнимы с
условием Поша, уже на 10 вершинах они значительно уступают данному условию.
При этом, имея вычислительную сложность $O(2^n \cdot \log (n))$, они являются
крайне неэффективными способами установления гамильтоновости графов.

Так как алгоритм определения жёсткости работает за неполиномиальное время,
достаточные условия гамильтоновости графов, основанные на этом определении,
являются лишь небольшим улучшением по сравнению с обычным перебором различных
вариантов построения гамильтонова цикла в графе, который также является
NP"=полной задачей.

Теорема Поша, с которой производилось сравнение теорем \ref{thm:bigalke} и
\ref{thm:bauer} является более подходящей для такой задачи, так как
способна определять гамильтоновость более 25\% графов, при этом имея
значительно более эффективную сложность $O(n + m)$.

Теоремы, основанные на запрещённых подграфах при этом позволяют определить
ещё меньшее количество графов по сравнению с другими рассмотренными теоремами.
Но при этом они позволяют определять некоторые из графов, которые не способна
определить теорема Бонди"=Хватала, которая является самой эффективной из
рассмотренных.

Данные теоремы в основном представляют теоретический интерес, так как
рассматривают совершенно иной способ определения гамильтоновости для
произвольных графов. Хотя они являются достаточно неэффективными в смысле
вычислительной сложности, они всё же имеют полиномиальную сложность и поэтому
в некоторых случаях их можно использовать для проверки на гамильтоновость тех
графов, которые не способна определить теорема Бонди"=Хватала. Например,
такие теоремы позволяют распознать гамильтоновы графы с небольшим количеством
рёбер вокруг цикла.


\bibliographystyle{gost780uv}
\inputencoding{cp1251}
\bibliography{sources}
\inputencoding{utf8}

\appendix

\section{Исходный код программы подсчёта графов на языке Rust, файл main.rs}
\label{app:rust1}
\inputminted{rust}{../graph-checker/src/main.rs}

\section{Исходный код программы подсчёта графов на языке Rust, файл graph.rs}
\label{app:rust2}
\inputminted{rust}{../graph-checker/src/graph.rs}

\section{Исходный код программы подсчёта графов на языке Rust, файл theorems/basic.rs}
\label{app:rust3}
\inputminted{rust}{../graph-checker/src/theorems/basic.rs}

\section{Исходный код программы подсчёта графов на языке Rust, файл theorems/forbidden.rs}
\label{app:rust4}
\inputminted{rust}{../graph-checker/src/theorems/forbidden.rs}

\section{Исходный код программы подсчёта графов на языке Rust, файл theorems/toughness.rs}
\label{app:rust5}
\inputminted{rust}{../graph-checker/src/theorems/toughness.rs}

\section{Исходный код программы подсчёта графов на языке Rust, файл theorems/mod.rs}
\label{app:rust6}
\inputminted{rust}{../graph-checker/src/theorems/mod.rs}


\section{Исходный код программы сравнения множеств графов на языке Python}
\label{app:python}
\inputminted{python}{../checker.py}

\end{document}