Учитывая двудольный граф с равными размерами сторон X и Y, как мы можем эффективно найти минимальное количество ребер, которые мы должны добавить, чтобы график имел идеальный соответствия? есть ли лучшее решение, чем итерация по всем 2^(| X |) подмножествам и добавление ребер до тех пор, пока не будет выполнена теорема Холла?Изменение двудольного графа, чтобы он имел идеальное соответствие
Спасибо.
Если я правильно понял вопрос, должно быть возможно эффективно сгенерировать согласование cardinality-maximal исходного графика, используя либо так называемый Hungarian method, либо моделью как проблему сетевого потока. После того, как найдено максимальное максимальное соответствие, в любом разделе должно быть одинаковое количество непревзойденных узлов, которые по желанию могут быть сопоставлены с использованием дополнительных ребер.
Другими словами, если M есть мощность из-максимальной мощности соответствия в исходном графе и |X|=|Y| имеет место, то по крайней мере M-|X| краев должны быть добавлены для того, чтобы иметь полное совпадение, содержащийся в графе.