Существует двудольный граф, B с совпадающим M в B. S - это набор узлов, совпадающих с совпадающим M. Кроме того, M1 - это наибольшее совпадение размеров в графе, которое гарантирует, что каждый узел в S совпадает в M1. Пусть M ∗ - максимальное совпадение в B без этого ограничения. Показать, что | M1 | ≤ | M ∗ |. Есть | M1 | = | M ∗ |? Я не могу думать о том, как решить эту проблему. Буду признателен, если вы дадите намек, который поможет мне в правильном направлении.