From 8fb4ba6c422c6941189791a5cc4bfa08d16cb6f9 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Tue, 10 Sep 2024 18:40:51 +0400 Subject: chore: merge presentation with report --- report/presentation.tex | 180 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 180 insertions(+) create mode 100644 report/presentation.tex (limited to 'report/presentation.tex') diff --git a/report/presentation.tex b/report/presentation.tex new file mode 100644 index 0000000..8ecedd1 --- /dev/null +++ b/report/presentation.tex @@ -0,0 +1,180 @@ +\documentclass{beamer} + +% \usepackage[T2A]{fontenc} +% \usepackage[utf8]{inputenc} + +\usepackage{fontspec} +\setmainfont[ + Path=./fonts/freefont/, + Extension = .otf, + UprightFont=*, + BoldFont=*Bold, + ItalicFont=*Italic, + BoldItalicFont=*BoldItalic +]{FreeSerif} +\setsansfont[ + Path=./fonts/freefont/, + Extension = .otf, + UprightFont=*, + BoldFont=*Bold, + ItalicFont=*Oblique, + BoldItalicFont=*BoldOblique +]{FreeSans} +\setmonofont[ + Path=./fonts/freefont/, + Extension = .otf, + UprightFont=*, + BoldFont=*Bold, + ItalicFont=*Oblique, + BoldItalicFont=*BoldOblique +]{FreeMono} + +\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}[thm]{\protect Теорема} +% \let\definition\relax +% \newtheorem{definition}{Определение} + +\usepackage[style=ieee, backend=bibtex]{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}{Библиография} + \printbibliography +\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} -- cgit v1.2.3