diff options
| -rw-r--r-- | report/coursework.pdf | bin | 665596 -> 668458 bytes | |||
| -rw-r--r-- | report/coursework.tex | 49 |
2 files changed, 43 insertions, 6 deletions
diff --git a/report/coursework.pdf b/report/coursework.pdf Binary files differindex 75df8f5..4cda32c 100644 --- a/report/coursework.pdf +++ b/report/coursework.pdf diff --git a/report/coursework.tex b/report/coursework.tex index d29a699..dd9d275 100644 --- a/report/coursework.tex +++ b/report/coursework.tex @@ -10,7 +10,30 @@ \intro -Введение +В 1859 году сэр Уильям Роуэн Гамильтон выпустил в продажу игру <<Путешествие +вокруг света>>. От играющего требовалось обойти <<вокруг света>>, то есть найти +такой обход рёбер додекаэдра, чтобы пройти через каждую вершину ровно один раз. + +К созданию этой головоломки его привело изучение додекаэдра, которое в свою +очередь привело к введению в теорию графов такого понятия, как <<гамильтонов +граф>>. + +Проверка произвольного графа на гамильтоновость представляет из себя задачу +полного перебора всех возможных построений гамильтонова цикла, что является +NP"=полной задачей, крайне неэффективной для вычисления. + +В связи с этим было предложено большое количество вариантов более эффективной +проверки на гамильтоновость графов с наложением определённых условий. Например, +одним из первых достаточных условий гамильтоновости графов было условие, +предложеное Дираком в 1952 году. Оно является крайне эффективным для вычисления, +но при этом позволяет определить менее 1\% гамильтоновых графов. + +Впоследствии были предложены условия Оре, Поша и Бонди"=Хватала, обобщающие +условие Дирака и позволяющие определить большее количество гамильтоновых графов. + +В данной работе рассмотрены теоремы, основанные на понятии \textit{жёсткости}, +введённом Вацлавом Хваталом в 1973 году, а также их сравнение с указанными выше +достаточными условиями гамильтоновости графов. \section{Основные определения} @@ -433,15 +456,29 @@ fn check_toughness(&self, t: f64) -> bool { вершинами; \end{itemize} + +\conclusion + Наиболее эффективным условием (по проценту определяемых графов), всё ещё -остаётся условие Бонди"=Хватала. Хотя теоремы Бауэра и Бигалке"=Юнга на -небольшом количестве вершин сравнимы с условием Поша, уже на 10 вершинах они -значительно уступают данному условию. +остаётся условие Бонди"=Хватала, которое позволяет установить гамильтоновость +примерно 90\% графов. +Хотя теоремы Бауэра и Бигалке"=Юнга на небольшом количестве вершин сравнимы с +условием Поша, уже на 10 вершинах они значительно уступают данному условию. +При этом, имея вычислительную сложность $O(2^n \cdot \log (n))$, они являются +крайне неэффективными способами установления гамильтоновости графов. -\conclusion +Так как алгоритм определения жёсткости работает за неполиномиальное время, +достаточные условия гамильтоновости графов, основанные на этом определении, +являются лишь небольшим улучшением по сравнению с обычным перебором различных +вариантов построения гамильтонова цикла в графе, который также является +NP"=полной задачей. + +Теорема Поша, с которой производилось сравнение Теорем \ref{thm:bigalke} и +\ref{thm:bauer} является более подходящей для такой задачи, так как +способна определять гамильтоновость более 25\% графов, при этом имея +значительно более эффективную сложность $O(n + m)$. -Заключение \bibliographystyle{gost780uv} \inputencoding{cp1251} |