alt text

.

задан 12 Май '17 18:44

изменен 13 Май '17 18:20

10|600 символов нужно символов осталось
2

Можно считать что $%M_A$% не содержит вершин из $%A\setminus A'$% и $%M_B$% не содержит вершин из $%B\setminus B'$%. Рассмотрим граф G' являющийся объединением паросочетаний $%M_A$% и $%M_B$%. Так как степени вершин в $%M_A$% и в $%M_B$% равны единице, то степени вершин в G' равны одному или двум, то есть он состоит из непересекающегося набора циклов и путей. Граф G'' построим следующим образом. В каждом цикле из G' уберем все четные ребра. В каждом пути из G' уберем все четные ребра. Остается показать что граф G'' и будет искомым паросочетанием. С циклами(из которых удалили каждое четное ребро) все понятно. С путями чуть сложнее. Надо заметить что пути из G' не могут начинаться и оканчиваться в A' и не могут начинаться и оканчиваться в B'.

ссылка

отвечен 14 Май '17 14:37

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×548

задан
12 Май '17 18:44

показан
316 раз

обновлен
14 Май '17 14:37

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

по почте:

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

по RSS:

Ответы

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

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