Пусть G – двудольный граф, с долями L и R, |L| = |R| = n, и множеством рёбер E. Степень каждой вершины v ∈ L ∪ R равна 2. Докажите, что существует биекция f : L → R, такая что f(u) = v, если {u, v} ∈ E.

задан 28 Окт '17 2:08

В заголовке использован оборот "доказать биекцию". Так не говорят: доказать можно какое-то утверждение, а биекция утверждением не является. В условии всё верно: доказать существование биекции можно.

Это следствие теоремы Холла о паросочетаниях. Рассмотрим какие-то k вершин левой доли. Для них рассмотрим вершины правой доли, соединённые хотя бы с одной из них. Чтобы теорема сработала, надо проверить, что их число m не меньше k.

В двудольном подграфе типа (k,m) рёбер ровно 2k. В любую вершину правой доли входит не более двух из них, и предположение m < k приводит к противоречию.

(28 Окт '17 2:38) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×635
×561
×83

задан
28 Окт '17 2:08

показан
1082 раза

обновлен
28 Окт '17 2:38

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru