\documentclass[14pt]{article}
\usepackage{graphicx}
\graphicspath{ {images/} }
\usepackage{caption}
\usepackage[utf8]{inputenc}
\usepackage{amsthm,amssymb, amsmath, amsfonts, amscd}
\usepackage[russian]{babel}
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}
\begin{document}

\title{20 ноября 2017}
\date{}
\maketitle
\vspace{-35pt}

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

\begin{enumerate}

%\textit{(2.5 балла)} 


\item \textit{(1.5 балла)} Найти максимальный поток и минимальный разрез между вершинами $1$ и $8$ в графе, изображенном на рис.1.

\item \textit{(1 балл)} Рассмотрим сеть, изображенную на рис.2. Величина пропускной способности ребра $(x_4,x_3)$ равна $r=(\sqrt{5}-1)/2$ и удовлетворяет уравнению вида $r^2=1-r$. Будем искать максимальный поток в этой сети алгоритмом Форда-Фалкерсона. В качестве первого увеличивающего поток пути возьмём путь $(s,x_2,x_3,t)$. Затем будем увеличивать поток вдоль путей в следующем порядке: $p_1,p_2,p_1,p_3,p_1,p_2,p_1,p_3,\dots$, где $p_1=(s,x_4,x_3,x_2,x_1,t)$, $p_2=(s,x_2,x_3,x_4,t)$, $p_3=(s,x_1,x_2,x_3,t)$. Показать, что при стремлении количества $n$ итераций к бесконечности величина потока не будет стремится к величине максимального потока в этой сети.

\item \textit{(1.5 балла)} Для формирования ученого совета университета необходимо выбрать одного преподавателя от каждой из $k$ университетских кафедр, $k$ --- натуральное число, делящееся на три. Один и тот же преподаватель может быть приписан к одной или нескольких кафедр, но может быть выбран в ученый совет только от одной из них. На кафедре работают профессора, доценты и ассистенты. В ученый совет должно входить одинаковое количество преподавателей от каждой из этих трех групп. Описать алгоритм выбора преподавателей в ученый совет. 

\item \textit{(1.5 балла)} После проведения некоторого количества матчей в спортивном турнире команда $X$ набрала известное нам количество побед. Если команда выиграет все оставшиеся матчи, в которых она участвует, то она наберёт $W$ побед. Могут ли остальные матчи завершиться так, чтобы $X$ стала победителем в турнире? Для ответа на поставленный вопрос мы создадим следующего вида сеть:
\begin{enumerate}
\item Пусть $X_1,\dots , X_n$ — все команды кроме  команды $X$. Добавим во множество вершин сети вершины $x_1,\dots, x_n$, соответствующие этим командам.
\item Добавим также в сеть $\binom{n}{2}$ вершин с пометками $y_{i,j}$ — по вершине для каждой неупорядоченной пары различных команд $\{X_i, X_j\}$. В вершину $y_{i,j}$ направим ребра бесконечной пропускной способности из вершин $x_i$ и $x_j$.
\item Добавим в сеть исток $s$ и сток $t$. 
\item Из истока в каждую из вершин $x_i$ будет идти ребро пропускной способности $W-w_i$, где $w_i$ — количество выигранных командой $X_i$ матчей. Из каждой вершины $y_{i,j}$ в сток направим ребро пропускной способности $a_{i,j}$, равной количеству матчей, в которых команда $X_i$ встретится с командой $X_j$.
\end{enumerate}
Докажите, что максимальный поток в этой сети равен величине $\sum_{i,j} a_{i,j}$ тогда и только тогда, когда команды могут сыграть так, чтобы ни одна из них не выиграла больше $W$ матчей.


\item \textit{(2 балла)} Рассмотрим два набора ${\bf p}:=(p_1,p_2,\ldots,p_m)$ и ${\bf q}:=(q_1,q_2,\ldots,q_n)$ неотрицательных целых чисел. Говорят, что пара $({\bf p},{\bf q})$ реализуема в виде простого двудольного графа $G$, если существует простой двудольный граф $G$ с долями $X=\{x_1,x_2,\ldots,x_m\}$ и $Y=\{y_1,y_2,\ldots,y_n\}$, такой, что $\deg(x_i)=p_i$ и $\deg(y_j)=q_j$ для всех $i\in[1,m]$ и $j\in[1,n]$. 

\begin{enumerate}
\item Свести задачу проверки заданной пары $({\bf p},{\bf q})$ на реализуемость в виде простого двудольного графа $G$ к задаче о нахождении максимального потока в сети.
\item Доказать, что пара $({\bf p},{\bf q})$ реализуема в виде простого двудольного графа тогда и только тогда, когда  
$$
\sum\limits_{i=1}^mp_i=\sum\limits_{j=1}^nq_j\qquad \text{и}\qquad 
\sum\limits_{i=1}^m\min\{p_i,k\}\geq \sum\limits_{j=1}^k q_j, \quad 1\leq k\leq n
$$ 
при условии, что числа $q_j$ упорядочены по невозрастанию: $q_1\geq q_2\geq\ldots\geq q_n$.
\end{enumerate}


\item \textit{(2 балла)} Доказать вершинную теорему Менгера для ориентированных графов с помощью теоремы Форда-Фалкерсона.

\item \textit{(2 балла)} Доказать вершинную теорему Менгера для неориентированных графов с помощью теоремы Форда-Фалкерсона.


\begin{figure}
\center{
\includegraphics[scale=0.3]{5_10_3}\caption{}
}
\end{figure}
\begin{figure}
\center{
\includegraphics[scale=0.3]{5_10_4}\caption{}
}
\end{figure}



%\begin{figure}[h]
%\center{
%\begin{minipage}{0.4\linewidth}
%\center{
%\includegraphics[scale=0.1]{5_10_3}\caption{}
%}
%\end{minipage}
%\begin{minipage}{0.6\linewidth}
%\center{
%\includegraphics[scale=0.2]{5_10_4}\caption{} 
%}
%\end{minipage}
%}
%\end{figure}

\end{enumerate}
\end{document}