\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}