Perfect bipartite matching 定理：考虑二分图完美匹配的线性规划： max∑e∈:CeXe subject to ∑ xe=1v∈V e∈δ(v) 0≤xe≤1He∈E 该LP的最优解一定是整数解 注意：这个LP在一般图上面并不一定是整数解的 22Perfect bipartite matching 定理：考虑二分图完美匹配的线性规划： max ∑K∈L �K�K subject to 5 K∈M 0 �K = 1 ∀� ∈ � 0 ≤ �K ≤ 1 ∀� ∈ � 该LP的最优解一定是整数解 注意：这个LP在一般图上面并不一定是整数解的 22