西安电子科技大学二部图的充要条件$6.2.4软件学院家茶茶教茶(充分性）设G是连通图，否则对G的每个连通分支进行证明。设G=<V，E>仅含有偶数长度的回路，任取vOEV，定义结点集X，Y如下：X=(v | d(vO,v)为偶数Y={v I d(vO,v)为奇数假设存在结点vi,vjEY，且(vi，vi)EE。由于G是连通的，并且vO到vi和vj的距离均为奇数，所以从vO到vi有一条最短路径，其长度为奇数；从vO到vj也有一条最短路径，其长度为奇数。于是由(vi，vi)及上述两条最短路径构成的回路长度为奇数，如图所示，这与G中仅含偶数长度的回路矛盾。故Y中任意两个结点间不存在边。同理可证，X中任意两个结点间不存在边。根据二部图的定义有G是二部图。西安电子科技大学 §6.2.4 二部图的充要条件 软件学院 (充分性） 设G是连通图，否则对G的每个连通分支进行证明。设 G=<V, E>仅含有偶数长度的回路，任取v0∈V，定义结点 集X, Y如下： X={v | d(v0,v)为偶数} Y={v | d(v0,v)为奇数} 假设存在结点vi,vj∈Y，且(vi, vj)∈E。由于G是连通的， 并且v0到vi和vj的距离均为奇数，所以从v0到vi有一条最短 路径，其长度为奇数；从v0到vj也有一条最短路径，其长度 为奇数。于是由(vi, vj)及上述两条最短路径构成的回路长度 为奇数，如图所示，这与G中仅含偶数长度的回路矛盾。故 Y中任意两个结点间不存在边。 同理可证，X中任意两个结点间不存在边。 根据二部图的定义有G是二部图