精选优质文档-倾情为你奉上*7.5 二部图及匹配 7.5.1二部图在许多实际问题中常用到二部图,本节先介绍二部图的基本概念和主要结论,然后介绍它的一个重要应用匹配。定义7.5.1 若无向图的顶点集能分成两个子集和,满足(1),;(2),均有,。则称为二部图或偶图(Bipartite Graph或Bigraph),和称为互补顶点子集,常记为。如果中每个顶点都与中所有顶点邻接,则称为完全二部图或完全偶图(Complete Bipartite Graph),并记为,其中。由定义可知,二部图是无自回路的图。图7-55中,都是二部图,其中是完全二部图。图7-55二部图示例显然,在完全二部图中中,顶点数,边数。一个无向图如果能画成上面的样式,很容易判定它是二部图。有些图虽然表面上不是上面的样式,但经过改画就能成为上面的样式,仍可判定它是一个二部图,如图7-56中可改画成图,图可改画成图。可以看出,它们仍是二部图。图7-56二部图示例定理7.5.1 无向图为二部图的充分必要条件为中所有回路的长度均为偶数。证明