Add stuffHEADmaster

1 files changed, 130 insertions, 0 deletions

diff --git a/dm-11.tex b/dm-11.tex
new file mode 100644
index 0000000..7e2b979
--- /dev/null
+++ b/dm-11.tex
@@ -0,0 +1,130 @@
+\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}