Из теории графов

[Stensen]

Доброго времени суток. Поясните пожалуйста решение задачи (см.ниже).



Не понятны последние два абзаца (выделено красным):

1. почему каждому графу $G_i$ принадлежит не более двух ребер наибольшего паросочетания?
Правильно я понимаю (см.рис.), что максимально, что можно "выжать" из графов $G_i$, это поменять местами паросочетания на концах увеличивающей цепи, если не нарушим паросочетания (на рис. показал стрелкой), и количество пар в этом случае может увеличиться в два раза?

2. в последнем абзаце опечатка? должно быть 12?

[Connector]

Если я правильно понял задачу, то можно думать так: если граф содержит три ребра паросочетания (или больше), то по крайней мере два из них будут смежными; но этого не может быть, поскольку экипажи двухместные, да и по определению паросочетания... Ошибаюсь?

[iifat]

Stensen в сообщении #1404804 писал(а):

2. в последнем абзаце опечатка? должно быть 12?

Похоже на то.

[provincialka]

Какое-то заумное решение. Может, я чего-то не понимаю... Но я рассуждала бы так.
За пределами 6 экипажей в графе нет ни одного ребра. Рассмотрим какое-нибудь паросочетание. Каждая его пара должна содержать хотя бы одного представителя 6 экипажей, то есть таких пар не более 12. Всё.

Может, приведенное решение говорит о том же? Только "научно"?

[Stensen]

provincialka в сообщении #1405100 писал(а):

Какое-то заумное решение.
За пределами 6 экипажей в графе нет ни одного ребра. Рассмотрим какое-нибудь паросочетание. Каждая его пара должна содержать хотя бы одного представителя 6 экипажей, то есть таких пар не более 12. Всё.

Может, приведенное решение говорит о том же? Только "научно"?

Да, ваше решение действительно проще. В этой книге описывается метод построения увеличивающей цепи, поэтому пытался этим способом. В этом случае построение увеличивающей цепи приведет к тому же результату. Это, видимо, одно из объяснений увеличивающей цепи.

[SiberianSemion]

Stensen в сообщении #1404804 писал(а):

1. почему каждому графу $G_i$ принадлежит не более двух ребер наибольшего паросочетания?

Это особенность $G_i\colon$ все его ребра строятся вокруг двух вершин. Больше двух ребер в нем не поместится, потому что первое ребро коснется одной вершины, второе $-$ другой, а для третьего места не останется.

То есть, все то, что сказала provincialka, только заумно.

[Stensen]

спасибо, пока понятно