2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Двудольный граф
Сообщение09.06.2015, 15:33 
Аватара пользователя
Я правильно понимаю, что для всего графа условия теоремы Холла могут и не выполняться?

 
 
 
 Re: Двудольный граф
Сообщение09.06.2015, 15:44 
Кто есть такой «весь граф»? Вся доля? Она является своим подмножеством.

-- 10.06.2015, 00:00 --

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

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

 
 
 
 Re: Двудольный граф
Сообщение09.06.2015, 17:09 
Что-то мне это не нравится. Вот это
function в сообщении #1025280 писал(а):
для любых выбранных вершин найдутся $k$ вершин из $O(M)_i$
вообще непонятно, а вот тут
function в сообщении #1025280 писал(а):
Она, как несложно понять, уже не сможет <<взаимодействовать>> ни с какой из вершин множества $O(M_i)$, поскольку все вакантные степени вершин доли $Y$ заполнятся
мне, вопреки вашим обещаниям, как-то сложно понять.

 
 
 
 Re: Двудольный граф
Сообщение09.06.2015, 17:25 
iifat в сообщении #1025298 писал(а):
Что-то мне это не нравится. Вот это
function в сообщении #1025280 писал(а):
для любых выбранных вершин найдутся $k$ вершин из $O(M)_i$
вообще непонятно, а вот тут
function в сообщении #1025280 писал(а):
Она, как несложно понять, уже не сможет <<взаимодействовать>> ни с какой из вершин множества $O(M_i)$, поскольку все вакантные степени вершин доли $Y$ заполнятся
мне, вопреки вашим обещаниям, как-то сложно понять.


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

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

 
 
 
 Re: Двудольный граф
Сообщение10.06.2015, 10:00 
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)$ заполнятся, следовательно, предположение неверно, и всё хорошо.

 
 
 
 Re: Двудольный граф
Сообщение10.06.2015, 14:34 
function в сообщении #1025565 писал(а):
Какое подмножество Вы имеете ввиду?
Такое :wink:
function в сообщении #1025248 писал(а):
достаточно показать, что для любого подмножества $M$ множества доли $X$ имеет место соотношение: $|O(M)|\geqslant |M|$
Соответственно, предположим, что есть такое, что $|O(M)|< |M|$ (что-то, стыдно сказать, формула не рисуется)

-- 10.06.2015, 22:40 --

function в сообщении #1025565 писал(а):
все вакантные степени вершин $O(M_i)$ заполнятся
Вот тут, по-моему, слабое место, которое доказать бы. Вот беру я некое подмножество вершин; вот его образ; почему вершины образа не могут быть связаны с вершинами, не вошедшими в исходное подмножество — непонятно.

 
 
 
 Re: Двудольный граф
Сообщение10.06.2015, 16:29 
Тогда немного по-другому. Из множества $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 писал(а):
что-то, стыдно сказать, формула не рисуется

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

 
 
 
 Re: Двудольный граф
Сообщение10.06.2015, 17:14 
function в сообщении #1025693 писал(а):
Тогда немного по-другому
Завтра непременно подумаю.
function в сообщении #1025693 писал(а):
В каком смысле?
А, это у меня плагин шалит. Не обращайте внимания.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group