Изменения

Пусть дан [[Основные определения теории графов|взвешенный полный двудольный граф ]] c целыми весами ребер <tex> K_{n, n} </tex>, нужно найти в нем [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях|полное паросочетание минимального веса]]. Вес [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях|паросочетания ]] определяется как сумма весов его ребер. Далее будем обозначать левую и правую доли графа за <tex> X </tex> и <tex> Y </tex> соответственно, вес ребра <tex> xy </tex> — как <tex> c(xy) </tex>.