Боюсь, ваша теория не верна. Представьте, что в наборе А 10 человек, а в наборе 10 предметов. Ваша теория говорит, что необходимо 19 соединений. Но на самом деле, вы могли бы иметь гораздо больше, не имея решения.
Например, разбейте наборы на группы по 7 и 3. Затем подключите каждого человека в группе из 7 человек к каждому элементу в группе. 7 предметов. Это 49 соединений.
И две группы из 3 все еще могут быть связаны, как показано в вопросе. Таким образом, с 10 людьми и 10 предметами вы можете иметь 53 соединения, не имея решения.
Спасибо @ PaulHankin за указание теорему Холла о браке в комментариях.
Я перефразирую теорему здесь. Доказательство находится в связанной статье.
Учитывая два набора A и B одинакового размера, насыщающее совпадение - это сопоставление, которое охватывает каждый элемент обоих наборов.
Для подмножества {b} в B пусть {a} обозначает подмножество A, которое имеет соединения с {b}. Теорема о браке гласит, что A и B имеют насыщающее соответствие тогда и только тогда, когда для каждого подмножества b в B:
| b | <= | a | </p>
Другими словами: каждое подмножество B имеет достаточно много связей с A.
Давайте применим это к графику в вопросе.
Мы видим, что подмножество b = {b1, b3} в B связано с подмножеством a = {a2} в A. Заметим, что | b | = = 2 и | a | == 1, поэтому условие | b | <= | a | не выполняется, и график не имеет насыщающего соответствия. </p>
Чтобы использовать теорему Холла о браке в качестве основы для алгоритма проверки существования насыщающего соответствия, нам необходимо проверить каждое подмножество B. Сколько подмножеств существует? Набор всех подмножеств B известен как powerset из B. Powerset содержит 2 ^ n подмножеств B (где n - количество элементов в B). Таким образом, использование теоремы напрямую приводит к алгоритму O (2 ^ n).
Алгоритмы, которые решают задачу максимального соответствия или проблему сбалансированного присваивания , могут использоваться для решить эту проблему более эффективно.