diff options
| -rw-r--r-- | .gitignore | 4 | ||||
| -rw-r--r-- | .vscode/settings.json | 3 | ||||
| -rw-r--r-- | checker.py | 28 | ||||
| -rw-r--r-- | report/coursework.pdf | bin | 51190 -> 663763 bytes | |||
| -rw-r--r-- | report/coursework.tex | 452 | ||||
| -rw-r--r-- | report/images/python_runner.png | bin | 0 -> 485536 bytes | |||
| -rw-r--r-- | report/preamble.sty | 7 | ||||
| -rw-r--r-- | report/sources.bib | 104 | ||||
| -rw-r--r-- | src/main.rs | 6 |
9 files changed, 597 insertions, 7 deletions
@@ -1,6 +1,10 @@ +# Rust /target .* +# Python +venv + # Latex auxillary files *.aux *.bbl diff --git a/.vscode/settings.json b/.vscode/settings.json index 6cb391b..e1b28e0 100644 --- a/.vscode/settings.json +++ b/.vscode/settings.json @@ -1,5 +1,8 @@ { "[bibtex]": { "files.encoding": "windows1251" + }, + "[latex]": { + "editor.tabSize": 2 } }
\ No newline at end of file diff --git a/checker.py b/checker.py new file mode 100644 index 0000000..cb0186b --- /dev/null +++ b/checker.py @@ -0,0 +1,28 @@ +import sys + + +def compare_data(data): + posa = data["posa"] + bigalke = data["bigalke-jung"] + bauer = data["bauer"] + + print(f"Поша: {len(posa)}, Бигалке-Юнг: {len(bigalke)}, Бауэр: {len(bauer)}") + print(f"Поша & Бауэр: {len(posa & bauer)}, Поша & Бигалке-Юнг: {len(posa & bigalke)}") + + print(f"Совпадают ли пересечения? {posa & bauer == posa & bigalke}") + print(f"Поша & Бауэр <= Поша & Бигалке-Юнг? {posa & bauer <= posa & bigalke}") + print(f"Поша & Бауэр >= Поша & Бигалке-Юнг? {posa & bauer >= posa & bigalke}") + + print(f"Графы Поша являются подмножеством графов Бигалке-Юнга? {posa <= bigalke}") + print(f"Графы Поша являются подмножеством графов Бауэра? {posa <= bauer}") + print(f"Симм. разность Бауэр и Поша: {bauer ^ posa}") + print(f"Графы Бауэра являются подмножеством графов Бигалке-Юнга? {bauer <= bigalke}") + print(f"Симм. разность Бауэр и Бигалке-Юнга: {bauer ^ bigalke}") + + +d = {} +for line in sys.stdin: + if line.startswith("g6"): + _, type, graph = line.strip().split(":") + d[type] = d.get(type, set()) | {graph} +compare_data(d)
\ No newline at end of file diff --git a/report/coursework.pdf b/report/coursework.pdf Binary files differindex 06a3d4b..a8eaae1 100644 --- a/report/coursework.pdf +++ b/report/coursework.pdf 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 diff --git a/report/images/python_runner.png b/report/images/python_runner.png Binary files differnew file mode 100644 index 0000000..c258a58 --- /dev/null +++ b/report/images/python_runner.png diff --git a/report/preamble.sty b/report/preamble.sty index ba8082b..cf89494 100644 --- a/report/preamble.sty +++ b/report/preamble.sty @@ -34,7 +34,10 @@ \newcommand{\eqdef}{\stackrel {\rm def}{=}} \renewcommand\theFancyVerbLine{\small\arabic{FancyVerbLine}} +\newtheorem{theorem}{Теорема} +\newtheorem{definition}{Определение} \newtheorem{lemma}{Лемма} \newtheorem*{lemma*}{Лемма} -\newtheorem{definition}{Определение} -\newtheorem*{example}{Пример}
\ No newline at end of file +\newtheorem*{example}{Пример} + +\setminted[rust]{fontsize=\small, breaklines=true, style=bw, linenos}
\ No newline at end of file diff --git a/report/sources.bib b/report/sources.bib index 3c1a691..6db2de9 100644 --- a/report/sources.bib +++ b/report/sources.bib @@ -1,2 +1,106 @@ % !TeX encoding = windows-1251 +@BOOK{Bogomolov_1997, + author = {. . and . . }, + title = { }, + publisher = {}, + address = {}, + year = {1997}, + language = {russian}, +} + +@article{bigalke1979hamiltonsche, + title={{\"U}ber hamiltonsche kreise und unabh{\"a}ngige ecken in graphen}, + author={Bigalke, A and Jung, HA}, + journal={Monatshefte f{\"u}r Mathematik}, + volume={88}, + number={3}, + pages={195--210}, + year={1979}, + publisher={Springer}, + language = {deutsch}, +} + +@article{dirac1952some, + title={Some theorems on abstract graphs}, + author={Dirac, Gabriel Andrew}, + journal={Proceedings of the London Mathematical Society}, + volume={3}, + number={1}, + pages={69--81}, + year={1952}, + publisher={Oxford Academic} +} + +@article{bondy1976method, + title={A method in graph theory}, + author={Bondy, J Adrian and Chv{\'a}tal, Vasek}, + journal={Discrete Mathematics}, + volume={15}, + number={2}, + pages={111--135}, + year={1976}, + publisher={Elsevier} +} + +@article{mckay2014practical, + title={Practical graph isomorphism, II}, + author={McKay, Brendan D and Piperno, Adolfo}, + journal={Journal of symbolic computation}, + volume={60}, + pages={94--112}, + year={2014}, + publisher={Elsevier} +} + +@article{bauer1995long, + title={Long cycles in graphs with prescribed toughness and minimum degree}, + author={Bauer, Douglas and Broersma, Haitze J and van den Heuvel, Jan and Veldman, Henk Jan}, + journal={Discrete mathematics}, + volume={141}, + number={1-3}, + pages={1--10}, + year={1995}, + publisher={Elsevier} +} + +@article{bauer2006toughness, + title={Toughness in graphs--a survey}, + author={Bauer, Douglas and Broersma, Hajo and Schmeichel, Edward}, + journal={Graphs and Combinatorics}, + volume={22}, + number={1}, + pages={1--35}, + year={2006}, + publisher={Springer} +} + +@article{ore1960note, + title={A note on hamiltonian circuits}, + author={Ore, Oystein}, + journal={American Mathematical Monthly}, + volume={67}, + pages={55}, + year={1960} +} + +@article{posa1963circuits, + title={On the circuits of finite graphs}, + author={P{\'o}sa, Lajos}, + journal={Magyar Tud. Akad. Mat. Kutat{\'o} Int. K{\"o}zl}, + volume={8}, + pages={355--361}, + year={1963} +} + +@book{harary_1973, + title={ }, + author={, }, + year={1973}, + publisher={" } +} + +@book{graph6, + title={Description of graph6, sparse6 and digraph6 encodings [{} ]}, + note={URL:~\url{http://users.cecs.anu.edu.au/~bdm/data/formats.txt} ( 05.06.2022). . . . .}}, +}
\ No newline at end of file diff --git a/src/main.rs b/src/main.rs index 41a5f5b..a6416e6 100644 --- a/src/main.rs +++ b/src/main.rs @@ -494,26 +494,32 @@ fn main() { if theorem15(&g, toughness, min_degree) { counters.t15_hamiltonian += 1; + println!("g6:bigalke-jung:{}", line); } if theorem25(&g, toughness, min_degree) { counters.t25_hamiltonian += 1; + println!("g6:bauer:{}", line); } if dirac_theorem(&g) { counters.dirac_hamiltonian += 1; + println!("g6:dirac:{}", line); } if ore_theorem(&g) { counters.ore_hamiltonian += 1; + println!("g6:ore:{}", line); } if posa_theorem(&g) { counters.posa_hamiltonian += 1; + println!("g6:posa:{}", line); } if is_complete { counters.bch_hamiltonian += 1; + println!("g6:bondy-chvatal:{}", line); } if is_complete && false { |
