Пусть $%M_1$% — максимальное по включению паросочетание в некотором графе $%G$%, а $%M_2$% — наибольшее паросочетание в $%G$%. Как доказать, что $%|M_2| =< 2|M_1|$%?

задан 14 Сен 16:31

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

$%M_1, M_2$% - максимальные паросочетания. Справедливо неравенство $%|M_2|\leq2|M_1|$%.

Каждое ребро из $%M_1\backslash M_2$% может быть сопряжено максимум двум ребрам из $%M_2\backslash M_1$%. При этом каждое ребро $%M_2\backslash M_1$% сопряжено с ребром $%M_1\backslash M_2$%. Следовательно, $%|M_2\backslash M_1|\leq 2|M_1\backslash M_2|$%. И далее $%|M_2|=|M_1\cap M_2|+|M_2\backslash M_1|\leq 2|M_1\cap M_2|+2|M_1\backslash M_2|=2|M_1|$%

ссылка

отвечен 14 Сен 17:32

Можете пояснить, что вы подразумеваете под сопряжено?

(14 Сен 19:45) KappaGolden

@KappaGolden, имеется ввиду смежность ребер. Наверное, не самый удачный подбор слова

(14 Сен 20:11) haosfortum
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×548

задан
14 Сен 16:31

показан
59 раз

обновлен
14 Сен 20:11

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

по почте:

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

по RSS:

Ответы

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

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