第七节二分图(2) (2)图G的匹配M是最大匹配当且仅当G不 含M的可扩路; (3)设G=(VE)为二分图顶点划分为V=M ∪V2则G存在饱和V的每个顶点匹配 的充要条件是对任何S均有 N(S)2S 3算法:匈牙利算法,解决了二分图的匹 配问题。 返回本章首页 2021/1212021/1/21 12 第七节 二分图(2) (2)图G的匹配M是最大匹配当且仅当G不 含M的可扩路; (3)设G=(V,E)为二分图,顶点划分为V= V1 ∪ V2 ,则G存在饱和V1的每个顶点匹配 的充要条件是对任何S V1均有 |N(S)|≧|S|； 3.算法：匈牙利算法，解决了二分图的匹 配问题。  返回本章首页