二分图
维基百科,自由的 encyclopedia
在图论中,二分图(英语:Bipartite graph)是一类特殊的图,又称为二部图、偶图、双分图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图,使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价的,二分图可以被定义成图中所有的环都有偶数个顶点[1][2]。
可以将 和 当做一个着色: 中所有顶点为蓝色, 中所有顶点着绿色,每条边的两个端点的颜色不同,符合图着色问题的要求[3][4]。相反的,非二分图无法被二着色,例如 (3 个顶点的完全图),将其中一个顶点着蓝色并且另外一个着绿色后,第三个顶点与上述具有两个颜色的顶点相连,无法再对它着蓝色或绿色。
二分图的一种描述方式为:,包含了独立集 和 ,以及边 的资讯。假如不是连通图,可能有多种将所有顶点分成 和 的方式[5];在特定的应用场合中,将顶点的两部分、写出来是有必要的。如果,则 称为平衡二分图[3]。如果二分图 以及 的顶点分别有相同的度数,则 被称为是双正则的(英语:Biregular graph)。
给定一个二分图 ,在 的一个子图 中, 的边集中的任意两条边都没有共同的端点,则称 是一个匹配。