匈牙利法与KM算法简介.ppt

二分图匹配 匈牙利算法和KM算法简介 二分图的概念 二分图又称作二部图,是图论中的一种特殊 模型 冷设G=(V{R})是一个无向图如顶点集V可分 割为两个互不相交的子集,并且图中每条边 依附的两个顶点都分属两个不同的子集贝 称图G为二分图 最大匹配 给定一个二分图G,在G的一个子图M中,M 的边集{}中的任意两条边都不依附于同一个 顶点,则称M是一个匹配 选择这样的边数最大的子集称为图的最大匹