上图不是二分图。 那么怎样的图才是二分图?二分图有怎 样的特征? 利用回路概念,可以给出二分图的特征。 定理57:G是二分图当且仅当G中没有 奇回路
上图不是二分图。 那么怎样的图才是二分图？二分图有怎 样的特征？ 利用回路概念, 可以给出二分图的特征。 定理5.7：G是二分图当且仅当G中没有 奇回路
证明:(1)若G是二分图则G中没有奇回 路 (V1V)的二分图,若G 没有回路当然就不会 G中有一条回路 不失一般性设v∈V1 v
证明：(1)若G是二分图则G中没有奇回 路 设G是具有二划分(V1 ,V2 )的二分图,若G 没有回路则已成立(没有回路当然就不会 有奇回路。 若 G 有回路 ， 设 G 中 有 一 条 回 路 C:(v0 ,v1 ,…,vm,v0 )。不失一般性,设v0V1
(2)若G中没有奇回路则G是二分图 设G是连通图否则对G的每个分支进行证明。 又设G是一个不包含奇回路的图。 下面关键是构造G的二划分V和V2 然后证明(1,V2)是G的一个二划分
(2)若G中没有奇回路则G是二分图 设G是连通图,否则对G的每个分支进行证明。 又设G是一个不包含奇回路的图。 下面关键是构造G的二划分V1和V2。 然后证明(V1 ,V2 )是G的一个二划分