From a1e230f819652826ddd7860288c4a838912ef0d4 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Wed, 8 Jun 2022 12:47:56 +0400 Subject: Update documentclass and main definitions --- report/coursework.tex | 62 +++++++++++++++++++++++++-------------------------- 1 file changed, 31 insertions(+), 31 deletions(-) (limited to 'report/coursework.tex') diff --git a/report/coursework.tex b/report/coursework.tex index ab86834..d29a699 100644 --- a/report/coursework.tex +++ b/report/coursework.tex @@ -1,4 +1,4 @@ -\documentclass[spec, och, coursework]{SCWorks} +\documentclass[spec, och, coursework-kb]{SCWorks} \usepackage{preamble} \title{Сравнение различных достаточных условий гамильтоновости графов} @@ -17,36 +17,36 @@ Рассмотрим основные определения, которые понадобятся при изучении достаточных условий гамильтоновости графов. Данные определения даются по работам -\cite{Bogomolov_1997} и \cite{harary_1973}. +\cite{Bogomolov_1997} и \cite{abrosimov2016graphs}. \begin{definition} - Неориентированным графом (или просто графом) называется пара $G = (V, - \alpha)$, где $V$ "--- конечное непустое множество (\textit{вершины} графа), а - $\alpha \subseteq V \times V$ "--- симметричное и антирефлексивное отношение - на множестве вершин $V$. Пара $(u, v) \in \alpha$ называется дугой графа с - началом $u$ и концом $v$. + Неориентированным графом (везде далее просто графом) называется пара $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$. + если $\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)$. Циклический маршрут "--- это маршрут, в котором начальная и - конечная вершины совпадают. Маршрут, в котором никакая дуга не встречается - более одного раза, называется путём. Путь, каждая вершина которого принадлежит - не более, чем двум его дугам, по определению является простым. Простой - циклический путь называют контуром, а простой путь, не являющийся контуром - "--- бесконтурным путём или цепью. + Путём в графе называется последовательность дуг $(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} @@ -66,6 +66,11 @@ е. $\alpha^* = (V^* \times V^*) \cap \alpha$. \end{definition} +\begin{definition} + Степенью вершины $v$ в неориентированном графе $G$ будем называть количество + вершин в $G$, смежных с $v$, и обозначать через $d(v)$. +\end{definition} + \section{Основные достаточные условия гамильтоновости графов} @@ -173,7 +178,7 @@ fn posa_theorem(g: &Graph) -> bool { условие $d(u) + d(v) \geq n$. \end{definition} -Можно заметить, что такое алгоритм построения такого замыкания имеет сложность +Можно заметить, что такой алгоритм построения такого замыкания имеет сложность $O(n^4)$. Немного изменённая версия этого алгоритма используется при построении гамильтонова цикла на основе нижеследующих теорем. @@ -269,10 +274,6 @@ m$ за $O(n)$ шагов. Тогда, цикл $C'$: \cite{bauer2006toughness}. Далее приведены две теоремы, основанные на понятии жёсткости, а также необходимые для этих теорем определения. -\begin{definition} - $\omega(G)$ "--- количество компонент связности в графе $G$. -\end{definition} - Для вычисления количества компонент графа можно использовать алгоритм поиска в глубину со сложностью $O(n + m)$. @@ -335,14 +336,13 @@ fn check_toughness(&self, t: f64) -> bool { является $t$"=жёстким. \end{definition} -Так как число $\tau$ является вещественным, и при этом монотонной и скачковой, -его можно найти с помощью алгоритма бинарного поиска, имеющего сложность $O(\log -(n))$. Вкупе с проверкой графа на $t$"=жёсткость, сложность нахождения жёсткости -имеет сложность $O(2^n \cdot \log (n))$ +Так как функция жёсткости $\tau$ является вещественной, монотонной и скачковой, +значение жёсткости графа можно найти с помощью алгоритма бинарного поиска, +имеющего сложность $O(\log (n))$. Вкупе с проверкой графа на $t$"=жёсткость, +сложность нахождения жёсткости имеет сложность $O(2^n \cdot \log (n))$ -\begin{definition} - $\delta(G)$ "--- минимальная степень в графе $G$. -\end{definition} +Обозначим $\delta(G)$ "--- минимальную степень в графе $G$ и $\omega(G)$ "--- +количество компонент связности в графе $G$. \begin{definition} Множество вершин называется независимым, если никакие две из них не смежны -- cgit v1.2.3