\documentclass[11pt]{article}
%\usepackage[T2A]{fontenc}
%\usepackage[utf8]{inputenc}
%\usepackage[russian]{babel}
\usepackage[x11names, svgnames, rgb]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,shapes}

\usepackage{scrextend}


\input{intro}

\lhead{\color{gray} Шарафатдинов Камиль 192}
\rhead{\color{gray} ДЗ-11 (\texttt{cw11\_plus})}

\makeatletter
\renewcommand*\env@matrix[1][*\c@MaxMatrixCols c]{%
  \hskip -\arraycolsep
  \let\@ifnextchar\new@ifnextchar
  \array{#1}}
\makeatother


\DeclareMathOperator{\chr}{char}

% -- Here bet  dragons --
\begin{document}
\begin{center}
    \textbf{1}
\end{center}

    Пусть это не так и множество $S_i$ содержится в $S_1 \cup \ldots \cup S_l$ целиком. Тогда $|S_1 \cup \ldots \cup S_l| = |S_1 \cup \ldots \cup S_l \cup S_i| = l < l + 1$ и тогда такое множество не удовлетворяет условию теоремы Холла.

\begin{center}
    \textbf{2}
\end{center}

    Рассмотрим ребра из $M \cup M'$. Любые два из них:

    \begin{addmargin}[2em]{0pt}
        \begin{enumerate}[noitemsep]
            \item не пересекаются -- оставляем оба
            \item совпадают -- берем любое
            \item пересекаются по одной из вершин
        \end{enumerate}
    \end{addmargin}

    Выберем какую-то компоненту связности. Она -- путь или цикл четной по вершинам длины, потому что:

    \begin{addmargin}[2em]{0pt}
        \begin{enumerate}[noitemsep]
            \item степень каждой вершины в ней не больше 2 $\implies$ это путь или цикл
            \item граф двудольный $\implies$ цикла нечетной длины быть не может
            \item если бы был путь нечетной длины ($2k + 1$), то в одной из долей было бы $k$ вершин, поэтому любое паросочетание было бы не больше $k$ и не покрывало бы хотя бы одну вершину из второй доли.
        \end{enumerate}
    \end{addmargin}

    \doubleskip
    \begin{minipage}{0.4\textwidth}
        \begin{tikzpicture}[scale=0.8]
            \draw[color=blue] (0,-2) circle [x radius=1, y radius=3];
            \draw[color=red] (3,-2) circle [x radius=1, y radius=3];
            
            %\draw (0, 0) circle (2pt) node[below] {$v_12$};
            \node[shape=circle,draw=blue,dotted] (A) at (0,0) {$v_1$};
            \node[shape=circle,draw=red]  (B) at (3,-1) {$v_2$};
            \node[shape=circle,draw=blue] (C) at (0,-2) {$v_3$};
            \node[shape=circle,draw=red] (D) at (3,-3) {$v_4$};
            \node[shape=circle,draw=blue] (E) at (0,-4) {$v_5$};

            \path [-](A) edge[dotted] node[above] {} (B);
            \path [-](B) edge node[below] {} (C);
            \path [-](C) edge node[below] {} (D);
            \path [-](D) edge node[below] {} (E);
        \end{tikzpicture}
    \end{minipage}
    \begin{minipage}{0.4\textwidth}
        \begin{tikzpicture}[scale=0.8]
            \draw[color=blue] (0,-2) circle [x radius=1, y radius=3];
            \draw[color=red] (3,-2) circle [x radius=1, y radius=3];
            
            %\draw (0, 0) circle (2pt) node[below] {$v_12$};
            %\node[shape=circle,draw=blue] (A) at (0,0) {$v_1$};
            \node[shape=circle,draw=red]  (B) at (3,-1) {$v_2$};
            \node[shape=circle,draw=blue] (C) at (0,-2) {$v_3$};
            \node[shape=circle,draw=red] (D) at (3,-3) {$v_4$};
            \node[shape=circle,draw=blue] (E) at (0,-4) {$v_5$};

            %\path [-](A) edge node[above] {} (B);
            \path [-](B) edge node[below] {} (C);
            \path [-](C) edge node[below] {} (D);
            \path [-](D) edge node[below] {} (E);
            \path [-](B) edge node[below] {} (E);
        \end{tikzpicture}
    \end{minipage}
    
    \medskip
    \medskip
    \medskip
    Понятно, что в каждом случае надо просто взять каждое второе ребро и все вершины будут покрыты. \qed


\begin{center}
    \textbf{3}
\end{center}

    Докажем, что любое вершинное покрытие в $G$ не меньше, чем $\frac{l}{d}$, тогда по теореме Кёнига можно будет утверждать, что существует паросочетание размера хотя бы $\frac{l}{d}$.

    Возьмем любое вершинное покрытие и начнем постепенно удалять вершины из него (вместе с их рёбрами). Тогда на каждом шаге мы удаляем из графа не более, чем $d$ рёбер, потому что степень каждой вершины не более, чем $d$. Всего нам надо удалить $l$ рёбер, поэтому вершин в покрытии было хотя бы $\frac{l}{d}$.


\begin{center}
    \textbf{4}
\end{center}

    Построим двудольный граф $G(L, R, E)$: слева будут подмножества размера $k$, справа - размера $k + 1$.
    Ребро между ними будет тогда, когда из левого подмножества можно получить правое, добавив какой-то элемент из $A$. Тогда $|E| = |L| \cdot (n - k)$ а максимальная степень вершины $d = \max(k + 1, n - k)$.

    \begin{align*}
        k \leq \frac{n - 1}{2}\\
        2k \leq n - 1\\
        k + 1 \leq n - k
    \end{align*}

    Поэтому $d = n - k$. Тогда воспользуемся \textbf{3} задачей -- в G есть паросочетание размера $\frac{|L|(n - k)}{n - k} = |L| \implies $ это паросочетание содержит все вершины $L$, поэтому есть инъекция $L \hookrightarrow R$, что равносильно условию задачи.



\end{document}