diff options
| -rw-r--r-- | report/coursework.pdf | bin | 663763 -> 665596 bytes | |||
| -rw-r--r-- | report/coursework.tex | 62 | ||||
| -rw-r--r-- | report/sources.bib | 7 | ||||
| -rw-r--r-- | report/titlepage.tex | 4 |
4 files changed, 40 insertions, 33 deletions
diff --git a/report/coursework.pdf b/report/coursework.pdf Binary files differindex a8eaae1..75df8f5 100644 --- a/report/coursework.pdf +++ b/report/coursework.pdf 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} Множество вершин называется независимым, если никакие две из них не смежны diff --git a/report/sources.bib b/report/sources.bib index 6db2de9..8bb2d3b 100644 --- a/report/sources.bib +++ b/report/sources.bib @@ -93,6 +93,13 @@ year={1963} } +@article{abrosimov2016graphs, + title={ }, + author={, and , }, + journal={: .--2008}, + year={2016} +} + @book{harary_1973, title={ }, author={, }, diff --git a/report/titlepage.tex b/report/titlepage.tex index ab3116a..84cd471 100644 --- a/report/titlepage.tex +++ b/report/titlepage.tex @@ -12,11 +12,11 @@ % \studenttitle{Студентки} % Заведующий кафедрой -\chtitle{д.ф.-м.н.} % степень, звание +\chtitle{д.ф.-м.н., доцент} % степень, звание \chname{М.~Б.~Абросимов} %Научный руководитель (для реферата преподаватель проверяющий работу) -\satitle{д.ф.-м.н.} %должность, степень, звание +\satitle{д.ф.-м.н., доцент} %должность, степень, звание \saname{М.~Б.~Абросимов} % Руководитель практики от организации (только для практики, |