
\documentclass[12pt,fleqn,a4paper]{article}

\usepackage[russian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{enumitem}
\usepackage{ntheorem}
\usepackage{tikz}
\usepackage{verbatim}

\usetikzlibrary{arrows,shapes}

\tikzstyle{vertex}=[circle,fill=black,minimum size=3pt,inner sep=0pt]
\tikzstyle{edge} = [draw,thick,-]

\newtheorem{definition}{Определение}
\newtheorem*{solution}{Решение}

\newenvironment{task}[2] {
	\noindent\fbox{\bf {#1} {#2}.}
}{
}

\newcommand{\mytitle}[2] {
  \begin{center}
      \bf {#1} {#2}.
  \end{center}
}

\let\origenumerate\enumerate
\let\origendenumerate\endenumerate
\renewenvironment{enumerate}{\origenumerate[topsep = 0pt, noitemsep]}{\origendenumerate}

\begin{document}
	\mytitle{Домашняя работа 7.}{Гамильтоновы графы}
	\begin{task}{COMB}{81}
		(1 балл) Пусть у нас есть граф $G$. Выразите количество гамильтоновых циклов в графе $G$, через $C_X$ --- количество циклов в графе $G \setminus X$, где $X \subseteq V(G)$
		(в искомой формуле могут использоваться $C_X$ для всевоможных $X$).
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{82}
		(2 балла) Придумайте алоритм вычисляющий количество гамильтоновых путей такой, что он работает $2^n poly(n)$, где $n$ --- число вершин.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{83}
		(3 балла). Доказать, что в случае шахматной доски размерами $4 \times n$ невозможно конем
		обойти все клетки доски, проходя каждую клетку лишь один раз и вернувшись в ту клетку, с которой начался обход.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{84}
		(1 балл) Доказать, что для любого подмножества $S$ множества $V(G)$ вершин графа $G$ справедливо равенство
		$\partial(S) = \sum_{x \in S} \mathrm{deg}(x) - 2|E(G[S])|$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{85}
		(1 балл) Доказать, что для любого реберного разреза $[S, \bar{S}]$ найдется набор из
		нескольких попарно непересекающихся между собой минимальных реберных разрезов,
		объединение которых даст нам реберный разрез $[S, \bar{S}]$.
	\end{task}
	\begin{solution}
	\end{solution}

\end{document}