Двудольный граф

[function]

Здравствуйте! Имеется двудольный граф $G$, в котором степень каждой вершины равна в точности $k$ ($k>0$). Помогите доказать через теорему Холла, что в $G$ существует совершенное сочетание пар.

Для этого достаточно показать, что для любого подмножества $M$ множества доли $X$ имеет место соотношение: $|O(M)|\geqslant |M|$, т. е. число элементов окрестности множества $M$ должно быть не меньше, чем число элементов множества $M$. Дальше не ясно, как наиболее аккуратно действовать.

[svv]

Я правильно понимаю, что для всего графа условия теоремы Холла могут и не выполняться?

[iifat]

Кто есть такой «весь граф»? Вся доля? Она является своим подмножеством.

-- 10.06.2015, 00:00 --

Предположим, есть такое подмножество. Сколько дуг из него выходит? А сколько входит в образ?

[function]

Выберем произвольно множество $M_i$ вершин доли $X$ графа $G$. Допустим противное: $|O(M_i)|<|M_i|$, тогда в $M_i$ выберем какие-нибудь $|O(M_i)|$ вершин, тогда по условию задачи для любых выбранных вершин найдутся $k$ вершин из $O(M)_i$, теперь рассмотрим какую-нибудь оставшуюся вершину из $M_i$, отличную от ранее выбранных. Она, как несложно понять, уже не сможет <<взаимодействовать>> ни с какой из вершин множества $O(M_i)$, поскольку все вакантные степени вершин доли $Y$ заполнятся, следовательно, предположение неверно, и всё хорошо. Можно ли таким образом завершить д-во?

[iifat]

Что-то мне это не нравится. Вот это

function в сообщении #1025280 писал(а):

для любых выбранных вершин найдутся $k$ вершин из $O(M)_i$

вообще непонятно, а вот тут

function в сообщении #1025280 писал(а):

Она, как несложно понять, уже не сможет <<взаимодействовать>> ни с какой из вершин множества $O(M_i)$, поскольку все вакантные степени вершин доли $Y$ заполнятся

мне, вопреки вашим обещаниям, как-то сложно понять.

[function]

iifat в сообщении #1025298 писал(а):

Что-то мне это не нравится. Вот это

function в сообщении #1025280 писал(а):

для любых выбранных вершин найдутся $k$ вершин из $O(M)_i$

вообще непонятно, а вот тут

function в сообщении #1025280 писал(а):

Она, как несложно понять, уже не сможет <<взаимодействовать>> ни с какой из вершин множества $O(M_i)$, поскольку все вакантные степени вершин доли $Y$ заполнятся

мне, вопреки вашим обещаниям, как-то сложно понять.

Исправляю неточные формулировки:
для любых выбранных вершин найдутся $k$ вершин из $O(M_i)$, соединённые ребром с каждой из них.

Она, как несложно понять, уже не может быть смежной ни с какой из вершин множества, поскольку все вакантные степени вершин доли $Y$ (доля $Y$ --- эта доля, которая не $X$) заполнятся.

[function]

iifat в сообщении #1025268 писал(а):

Предположим, есть такое подмножество. Сколько дуг из него выходит? А сколько входит в образ?

Какое подмножество Вы имеете ввиду? Что такое <<дуги>>?

А как насчёт моих исправлений в варианте доказательства?
Выберем произвольно множество $M_i$ вершин доли $X$ графа $G$. Допустим противное: $|O(M_i)|<|M_i|$, тогда в $M_i$ выберем какие-нибудь $|O(M_i)|$ вершин, тогда по условию задачи для любых выбранных вершин найдутся $k$ смежных вершин из $O(M_i)$. Теперь рассмотрим какую-нибудь оставшуюся вершину из $M_i$, отличную от ранее выбранных. Она, как несложно понять, уже не может быть смежной ни с какой из вершин множества, поскольку все вакантные степени вершин $O(M_i)$ заполнятся, следовательно, предположение неверно, и всё хорошо.

[iifat]

function в сообщении #1025565 писал(а):

Какое подмножество Вы имеете ввиду?

Такое

function в сообщении #1025248 писал(а):

достаточно показать, что для любого подмножества $M$ множества доли $X$ имеет место соотношение: $|O(M)|\geqslant |M|$

Соответственно, предположим, что есть такое, что $|O(M)|< |M|$ (что-то, стыдно сказать, формула не рисуется)

-- 10.06.2015, 22:40 --

function в сообщении #1025565 писал(а):

все вакантные степени вершин $O(M_i)$ заполнятся

Вот тут, по-моему, слабое место, которое доказать бы. Вот беру я некое подмножество вершин; вот его образ; почему вершины образа не могут быть связаны с вершинами, не вошедшими в исходное подмножество — непонятно.

[function]

Тогда немного по-другому. Из множества $M_i$ исходит $k|M_i|$ рёбер, а из $O(M_i)$ исходит $k|O(M_i)|$, но тогда $k|O(M_i)|$ не меньше, чем $k|M_i|$, т. к. некоторые рёбра, смежные с вершинами $k|O(M_i)|$ не обязательно могут быть смежными с вершинами множества $M_i$, плюс к тому же некоторые рёбра с вершинами в $O(M_i)$ полностью насыщают вершины из $M_i$, откуда и следует требуемое.

iifat в сообщении #1025649 писал(а):

что-то, стыдно сказать, формула не рисуется

В каком смысле?

[iifat]

function в сообщении #1025693 писал(а):

Тогда немного по-другому

Завтра непременно подумаю.

function в сообщении #1025693 писал(а):

В каком смысле?

А, это у меня плагин шалит. Не обращайте внимания.