二分图

时间：2018-09-01 20:12:09 阅读：146 评论：0 收藏：0 [点我收藏+]

1.概念

G=(V, E)是一个无向图

如果G的顶点集V可分割为两个互不相交的子集X和Y，并且E中每条边连接的两个顶点一个在X中，另一个在Y中，则称图G为二分图，记为G=(X,Y,E)

匹配：给定一个二分图G=(X,Y,E)，若存在E的一个子集M，满足M中的任意两条边都没有公共顶点，则M称为一个G的匹配

匹配边：在匹配中的边

未匹配边：不在匹配中的边

未匹配点：对于一个匹配，不与任何匹配边邻接的点

匹配点：刚好相反

极大匹配：无法再加边的匹配

最大匹配：在所有极大匹配中，边数|M|最大的匹配

完全匹配：如果一个匹配中，图中每个顶点都与一条边相关联，则称此匹配为完全匹配

2.条件

无向图G为二分图的充分必要条件是，G至少有两个顶点，且其所有回路的长度均为偶数

原文：https://www.cnblogs.com/lcan/p/9571211.html

踩

(0)

评论一句话评论（0）

分享档案

更多>