精选优质文档-倾情为你奉上*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 无向图为二部图的充分必要条件为中所有回路的长度均为偶数。证明
