\documentclass[12pt]{article}
\usepackage[left=1.5cm,right=1.5cm,top=1.5cm,bottom=1cm,bindingoffset=0cm]{geometry}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage{euscript}
\usepackage{graphicx}
\usepackage{amsthm, amsmath, amssymb}
%\usepackage[text={163mm,255mm},centering]{geometry}
\usepackage{hyperref}
\newtheorem{thm}{Теорема}
\newtheorem*{lemma}{Лемма}
\newtheorem{sled}{Следствие}
\newtheorem{example}{Пример}
\newtheorem{utv}{Утверждение}
\theoremstyle{definition}
\newtheorem{opr}{Определение}
\theoremstyle{remark}
\newtheorem{zam}{Замечание}

\newcommand\BCf[2]{\binom{#1}{#2}}
\newcommand\BCCf[2]{\left(\binom{#1}{#2}\right)}
\newcommand\Z{\mathbb{Z}}

\def\odin{\mathbf{1}}
\let\leq\leqslant
\let\geq\geqslant


\pagenumbering{gobble}

\begin{document}

\begin{center}

    \huge {Домашнее задание \textnumero 12}
		
		\large Группа 504

\end{center}    

\vspace{0.5cm}

Количество баллов на зачёт: \textbf{7}.

\begin{enumerate}

\item (1,5) Доказать, что в двудольном графе $G[X,Y]$ существует совершенное паросочетание тогда и только тогда, когда для любого $S\subseteq V(G)$ выполняется неравенство $|S|\leq |N(S)|$. Предъявить бесконечное семейство графов, для которых данное свойство выполняется, а совершенное паросочетание при этом отсутствует.

\item (1,5) Пусть в двудольном графе $G[X,Y]$ степень любой вершины $x\in X$ больше или равна степени любой вершины $y\in Y$. Доказать, что в $G[X,Y]$ существует $X$-насыщенное паросочетание.

\item (2) Пусть в двудольном графе $G[X,Y]$ существует $X$-насыщенное паросочетание. Доказать, что количество рёбер в $G[X,Y]$, которые не принадлежат ни одному $X$-насыщенному паросочетанию, не превосходит $\BCf{|X|}{2}$. Показать, что эта оценка достигается при любом значении $|X|$.

\item (1,5) Доказать теорему Холла, используя теорему Кёнига-Эгервари.

\item \label{exerc:Hall_gen} (1,5) В двудольном графе $G[X,Y]$ обозначим через $\rm{def}(S)$, $S\subseteq X$, разность между $|S|$ и $|N(S)|$. По определению положим $\rm{def}(\emptyset)=0$. Доказать, что в двудольном графе $G[X,Y]$ существует паросочетание $M$, состоящее хотя бы из $|X|-d$ ребер, где $d:=\max_{S\subseteq X}\rm{def}(S)$. 

\item (1,5) Доказать теорему Кёнига-Эгервари с помощью сформулированного в упражнении \ref{exerc:Hall_gen} утверждения.

\item (1) Рассмотрим прямоугольную матрицу $A$, состоящую из нулей и единиц. Пусть $l$ есть максимальное количество единиц, которые можно выбрать так, чтобы никакие две из них не принадлежали одной и той же строке или одному и тому же столбцу матрицы $A$, а $k$ равно минимальному количеству строк и (или) столбцов, содержащих все единицы матрицы $A$. К примеру, в матрице
$$
A=\begin{pmatrix}
1&1&\boxed{1}&0&0&0\\
0&0&1&\boxed{1}&1&1
\end{pmatrix}
$$
существуют $l=2$ единицы, обведенные в квадратную рамочку, которые не принадлежат одной и той же строке или одному и тому же столбцу матрицы $A$. Далее, существует $k=2$ строки, которые содержат все единицы матрицы $A$. 
Доказать справедливость равенства $l=k$ в общем случае.

\begin{lemma} Матрицей $P$ перестановок называется квадратная бинарная матрица, в которой ровно одна единица стоит в каждой строке и в каждом столбце. Любая такая матрица является, по сути, матричным представлением некоторой перестановки $\sigma$. Доказать, что любая квадратная матрица $n\times n$, состоящая из неотрицательных целых чисел, выражается в виде суммы $k$ матриц перестановок тогда и только тогда, когда сумма чисел в любой строке, а также сумма чисел в любом столбце равны $k$.  
\end{lemma}
\begin{proof}
В одну сторону утверждение очевидно --- если $A$ есть сумма $k$ матриц перестановок $P_i$, $i=1,\ldots,k$, то каждая такая матрица дает вклад, равный единице, в сумму элементов каждой строки и каждого столбца. Для доказательства обратного утверждения будем действовать индукцией по $k$. База индукции $k=1$ верна --- в этом случае $A=P$ --- матрице перестановок. 

В случае $k>1$ построим двудольный граф $G[X,Y]$ с блоками $X=\{x_1,\ldots,x_n\}$ и $Y=\{y_1,\ldots,y_n\}$, и соединим $x_i$ с $y_j$ ребрами в количестве, равном $a_{i,j}$. Так как такой граф является $k$-регулярным, то, на основании упражнения 3 из класса, в нем имеется совершенное паросочетание $M$. Для любого ребра $\{x_i,y_j\}\in M$ положим $b_{i,j}=1$, и $b_{i,j}=0$ в противном случае. Матрица $B$, составленная из элементов $b_{i,j}$, является матрицей перестановок. Вычитая из $A$ матрицу $B$, получим матрицу $A'$, сумма элементов в любой строке и в любом столбце которой равна $k-1$. По индукционному предположению, она раскладывается в сумму $k-1$ матриц перестановок. Добавляя к ним $B$, получим требуемое разложение матрицы $A$.
\end{proof}

\item (1,5) Дважды стохастической матрицей $Q$ называется вещественная неотрицательная матрица, в которой сумма чисел в любой строке и сумма чисел в любой строке равняется единице. Доказать, что любая такая матрица $Q$ представима в виде линейной комбинации
$$
Q=c_1\cdot P_1+\ldots+c_m\cdot P_m,
$$
где $P_i$ --- матрицы перестановок, $c_i$ --- вещественные неотрицательные числа, сумма которых равна единице.

%\begin{center}
%\includegraphics[height=3cm]{i15}
%\end{center}



\end{enumerate}

\end{document}