
\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{Домашняя работа 10.}{Паросочетания}
	\begin{task}{COMB}{120}
		(1 балл) Найдите минимальный пример двудольного графа, в котором существует паросочетание, наибольшее по включению, не являющееся максимальным.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{121}
		(1,5 балла) Определить минимальный размер наибольшего по включению паросочетания в простом цикле $C_11$,
		построенном на одиннадцати вершинах. Чему будет равен этот размер в случае произвольного простого цикла $C_n$?
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{122}
		(1,5 балла) Доказать, что в любом графе $G$ размер наибольшего по включению паросочетания
		содержит по меньшей мере $\alpha'(G)/2$ ребер, где $\alpha'(G)$ --- количество ребер в максимальном паросочетании.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{123}
		(1,5 балла) Рассмотрим следующую игру на графе $G$: два игрока поочередно выбирают вершины 
		$x_1$, $x_2$, \dots, $x_n$ графа так, чтобы вершина $x_{i + 1}$ была бы смежной с вершиной $x_i$; 
		тот из игроков, кто не сможет выбрать новую вершину по этим правилам, проигрывает. 
		Доказать, что первый игрок имеет выигрышную стратегию тогда и только тогда, когда в $G$ отсутствует совершенное паросочетание.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{124}
		(1 балл) Пусть $S$ есть подмножество множества $V(G)$ вершин графа $G$,
		покрытое некоторым паросочетанием $M$. Доказать, что некоторое максимальное паросочетание
		также покрывает все вершины этого множества. Верно ли, что данный факт будет выполняться для любого максимального паросочетания?
	\end{task}
	\begin{solution}
	\end{solution}

\end{document}