发布网友 发布时间:2024-10-16 01:15
共1个回答
热心网友 时间:2024-10-16 20:55
二分图是图的一种,节点由两个集合组成,同一集合内两点之间无边,任意边的两点必须属于不同集合。例如Fig.1不是二分图,Fig.2、Fig.3、Fig.4则是。匹配是边的集合,集合内任意两条边无公共顶点。Fig.3和Fig.4展示了Fig.2的不同匹配。匹配点是匹配中包含的点,未匹配点是匹配中未包含的点;匹配边是匹配中的边,非匹配边是匹配中的边。最大匹配是针对某图,包含匹配边最多的匹配。Fig.4中的匹配即为其最大匹配,包含4条匹配边。完美匹配是指某匹配使得图中的所有顶点均为匹配点。显然,完美匹配一定是最大匹配,但并非每个图都存在完美匹配。