1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
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}
|
