diff options
Diffstat (limited to 'report/coursework.tex')
| -rw-r--r-- | report/coursework.tex | 452 |
1 files changed, 447 insertions, 5 deletions
diff --git a/report/coursework.tex b/report/coursework.tex index 38b6854..ab86834 100644 --- a/report/coursework.tex +++ b/report/coursework.tex @@ -5,15 +5,457 @@ \author{Гущина Андрея Юрьевича} % Фамилия, имя, отчество в родительном падеже \begin{document} -\include{titlepage.tex} +\input{titlepage.tex} \tableofcontents \intro +Введение -% \bibliographystyle{gost780uv} -% \inputencoding{cp1251} -% \bibliography{sources} -% \inputencoding{utf8} + +\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 °rees { + if *d <= k { + cnt += 1; + } + } + if cnt >= k { + return false; + } + } + if g.size % 2 != 0 { + let mut cnt = 0; + for d in °rees { + 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}
\ No newline at end of file |