path: root/report/coursework.tex

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

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

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

\intro

Введение


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

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

\begin{definition}
  Неориентированным графом (или просто графом) называется пара $G = (V,
  \alpha)$, где $V$ "--- конечное непустое множество (\textit{вершины} графа), а
  $\alpha \subseteq V \times V$ "--- симметричное и антирефлексивное отношение
  на множестве вершин $V$. Пара $(u, v) \in \alpha$ называется дугой графа с
  началом $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}
  Бесконтурный путь длины $n - 1$ в графе $G$ называется гамильтоновой цепью, а
  контур длины $n$ "--- гамильтоновым контуром. Граф, в котором существует
  гамильтонов контур, по определению, является гамильтоновым.
\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}


\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}. Далее приведены две теоремы, основанные на понятии
жёсткости, а также необходимые для этих теорем определения.

\begin{definition}
  $\omega(G)$ "--- количество компонент связности в графе $G$. 
\end{definition}

Для вычисления количества компонент графа можно использовать алгоритм поиска в
глубину со сложностью $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))$

\begin{definition}
  $\delta(G)$ "--- минимальная степень в графе $G$.
\end{definition}

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


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

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

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

\begin{table}[H]
  \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}

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

Для этого была написана программа на языке программирования 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}

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


\conclusion 

Заключение

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

\appendix

\section{Исходный код программы подсчёта графов на языке Rust}
\label{app:rust}
\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{rust}{../src/main.rs}

\section{Исходный код программы сравнения множеств графов на языке Python}
\label{app:python}
\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{rust}{../checker.py}

\end{document}