diff options
| -rw-r--r-- | .gitignore | 6 | ||||
| -rw-r--r-- | presentation/images/DUW.png | bin | 0 -> 76172 bytes | |||
| -rw-r--r-- | presentation/images/forbidden.jpg | bin | 0 -> 186501 bytes | |||
| -rwxr-xr-x | presentation/maker.sh | 35 | ||||
| -rw-r--r-- | presentation/presentation.pdf | bin | 0 -> 407372 bytes | |||
| -rw-r--r-- | presentation/presentation.tex | 149 | ||||
| -rw-r--r-- | presentation/sources.bib | 31 |
7 files changed, 221 insertions, 0 deletions
@@ -20,3 +20,9 @@ venv *.toc *.dvi _minted-* + +# Beamer files +*.bcf +*.nav +*.run.xml +*.snm diff --git a/presentation/images/DUW.png b/presentation/images/DUW.png Binary files differnew file mode 100644 index 0000000..2ef0043 --- /dev/null +++ b/presentation/images/DUW.png diff --git a/presentation/images/forbidden.jpg b/presentation/images/forbidden.jpg Binary files differnew file mode 100644 index 0000000..a94f53c --- /dev/null +++ b/presentation/images/forbidden.jpg diff --git a/presentation/maker.sh b/presentation/maker.sh new file mode 100755 index 0000000..9b12212 --- /dev/null +++ b/presentation/maker.sh @@ -0,0 +1,35 @@ +#!/bin/sh + +watch() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1 +} + +doc() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode $1 +} + +clean() { + set -o xtrace + rm -rf _minted-* + find . -name "*.aux" -delete + rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc *.bcf *.nav *.xml *.snm *.vrb *.bbl +} + +help() { + echo "Использование:" + echo "./maker.sh watch <main-doc>.tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc <main-doc>.tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac diff --git a/presentation/presentation.pdf b/presentation/presentation.pdf Binary files differnew file mode 100644 index 0000000..b9715ec --- /dev/null +++ b/presentation/presentation.pdf diff --git a/presentation/presentation.tex b/presentation/presentation.tex new file mode 100644 index 0000000..86a706c --- /dev/null +++ b/presentation/presentation.tex @@ -0,0 +1,149 @@ +\documentclass{beamer} + +\usepackage[T2A]{fontenc} +\usepackage[utf8]{inputenc} +\usepackage[english,russian]{babel} +\usepackage{wrapfig} +\usepackage{graphicx} +\usepackage{multirow} +\usepackage{fancyvrb} +\usepackage{underscore} +\graphicspath{ {./images/} } + +\usetheme{Madrid} + +\usepackage{amsmath} +\usepackage{amsthm} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{mathtools} +\usepackage{braket} +\usepackage{csquotes} + +\setbeamertemplate{caption}[numbered] +\setbeamertemplate{theorems}[numbered] +\let\theorem\relax +\newtheorem{theorem}{Теорема} +\let\definition\relax +\newtheorem{definition}{Определение} + +\usepackage[style=ieee]{biblatex} +\setbeamertemplate{bibliography item}{\insertbiblabel} +\addbibresource{sources.bib} + +\title[Достат. условия гамильтоновости]{Сравнение достаточных условий гамильтоновости графов на основе запрещённых подграфов} +\author[Гущин~А.~Ю.]{Гущин~Андрей~Юрьевич} +\institute[СГУ]{Саратовский Государственный Университет} +\date{4 мая 2023 г.} + +\begin{document} + +\maketitle + +\begin{frame}{Условие для сравнения} + \begin{definition} + Замыкание $[G]$ $n$"=вершинного графа $G$ получается из графа $G$ добавлением + рёбер $\{ u, v \}$ для всех пар вершин $u$ и $v$, для которых выполняется + условие $d(u) + d(v) \geq n$. + \end{definition} + + \begin{theorem}[Бонди"=Хватал, \cite{bondy1976method}] + Если замыкание $[G]$ графа $G$ является полным графом, то граф $G$ "--- + гамильтонов. + \end{theorem} +\end{frame} + +\begin{frame}{Условия с запрещёнными подграфами} + \begin{theorem}[Duffus"=Gould"=Jacobson, \cite{gould2003advances}] % 85 + Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3}, + N}$, то он также является гамильтоновым. + \end{theorem} + + \begin{theorem}[Broersma"=Veldman, \cite{gould2003advances}] % 86 + Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3}, + P_6}$, то он также является гамильтоновым. + \end{theorem} +\end{frame} + +\begin{frame}{Условия с запрещёнными подграфами} + \begin{theorem}[Gould"=Jacobson, \cite{gould2003advances}] % 87 + Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3}, + Z_2}$, то он также является гамильтоновым. + \end{theorem} + + \begin{theorem}[Bedrossian, \cite{gould2003advances}] % 88 + Если граф $G$ является двусвязным и свободным от подграфов $\set{K_{1, 3}, + W}$, то он также является гамильтоновым. + \end{theorem} + + \begin{theorem}[Shepherd, \cite{gould2003advances}] % 96 + Если граф $G$ является трисвязным и свободным от подграфов $\set{K_{1, 3}, + N}$, то он также является гамильтоново-связным. + \end{theorem} +\end{frame} + +\begin{frame} + \begin{figure}[H] + \centering + \includegraphics[width=\textwidth]{forbidden} + \caption{Упомянутые запрещённые подграфы} + \label{fig:forbidden} + \end{figure} +\end{frame} + +\begin{frame}{Результаты, полученные с помощью программы, \cite{mckay2014practical}} + \begin{table}[H] + \centering + \caption{Количество определяемых гамильтоновых графов} + \begin{tabular}{|c|c|c|c|c|c|c|} + \hline + $n$ & Т1. Бонди-Хватала & Т2 & Т3 & Т4 & Т5 & Т6 \\ \hline + 4 & 3 & 3 & 3 & 3 & 3 & 1 \\ \hline + 5 & 7 & 8 & 8 & 8 & 8 & 3 \\ \hline + 6 & 45 & 32 & 32 & 25 & 32 & 13 \\ \hline + 7 & 352 & 126 & 123 & 56 & 122 & 60 \\ \hline + 8 & 5540 & 605 & 578 & 133 & 554 & 359 \\ \hline + 9 & 157016 & 3148 & 2925 & 331 & 2723 & 2241 \\ \hline + 10 & 8298805 & 19296 & 17691 & 945 & 16446 & 15889 \\ \hline + \end{tabular} + \label{tbl:res} + \end{table} +\end{frame} + +\begin{frame}{Результаты, полученные с помощью программы, \cite{mckay2014practical}} + \begin{table}[H] + \centering + \caption{Разность условий с условием Бонди"=Хватала} + \begin{tabular}{|c|c|c|c|c|c|c|c|} + \hline + $n$ & Т2 & Т3 & Т4 & Т5 & Т6 & T2-5 & T2-5 - T2 \\ \hline + 4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline + 5 & 1 & 1 & 1 & 1 & 0 & 1 & 0 \\ \hline + 6 & 2 & 2 & 1 & 2 & 0 & 2 & 0 \\ \hline + 7 & 11 & 8 & 2 & 8 & 0 & 11 & 0 \\ \hline + 8 & 42 & 18 & 1 & 11 & 1 & 42 & 0 \\ \hline + 9 & 203 & 52 & 3 & 34 & 14 & 204 & 1 \\ \hline + 10 & 879 & 89 & 2 & 46 & 67 & 885 & 6 \\ \hline + \end{tabular} + \label{tbl:res} + \end{table} +\end{frame} + +\begin{frame} + \begin{figure}[H] + \centering + \includegraphics[height=0.7\textheight]{DUW} + \caption{5-вершинный граф DUW} + \label{fig:DUW} + \end{figure} +\end{frame} + +\begin{frame}{Библиография} + \begin{enumerate} + \item \emph{Bondy J. A.}, Chvatal V. A method in graph theory // Discrete Mathematics. 1976. — Vol. 15, № 2. P. 111–135. + \item \emph{Gould R. J.} Advances on the hamiltonian problem–a survey // Graphs and Combinatorics. 2003. Vol. 19. P. 7–52. + \item \emph{McKay B. D.}, Piperno A. Practical graph isomorphism, II // Journal of symbolic computation. 2014. Vol. 60. P. 94–112. + \end{enumerate} +\end{frame} + +\end{document} diff --git a/presentation/sources.bib b/presentation/sources.bib new file mode 100644 index 0000000..46d47be --- /dev/null +++ b/presentation/sources.bib @@ -0,0 +1,31 @@ +@article{gould2003advances, + title={Advances on the Hamiltonian problem--a survey}, + author={Gould, Ronald J}, + journal={Graphs and Combinatorics}, + volume={19}, + number={1}, + pages={7--52}, + year={2003}, + publisher={Springer} +} + +@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} +} |
