689
правок
Изменения
м
→Некоторые полезные утверждения
Если веса всех ребер графа, инцидентных какой-либо вершине, изменить на одно и то же число, то в новом графе оптимальное паросочетание будет состоять из тех же ребер, что и в старом.
|proof=
Полное паросочетание для каждой вершины содержит ровно одно ребро, инцидентное этой вершине. Указанная операция изменит на одно и то же число вес любого паросочетания. При изменении весов всех реберЗначит, инцидентных данной вершинеребро, на одно и то же числокоторое принадлежало оптимальному паросочетанию в старом графе, выбранное ребро останется оптимальнымв новом графе тоже будет ему принадлежать.
}}
{{Лемма
|statement=
Выделим в множествах <tex>X</tex> и <tex>Y</tex> подмножества <tex>X', Y'</tex>. Пусть <tex>d = \min \{c(xy)|\ x \in X \setminus X', y \in Y'\}</tex>. Прибавим <tex> d </tex> ко всем весам ребер, инцидентных вершинам из <tex>X'</tex>. Затем отнимем <tex> d </tex> от всех весов ребер, инцидентных вершинам из <tex>Y'</tex> (далее для краткости будем обозначать эту операцию эта операция обозначается как <tex> X' \uparrow\downarrow Y' </tex>). Тогда:
# Веса всех ребер графа останутся неотрицательными.
# Веса ребер вида <tex>xy</tex>, где <tex>x \in X', y \in Y'</tex> или <tex>x \in X \backslash X', y \in Y \backslash Y'</tex>, не изменятся.
