一些特殊的图.ppt

文档介绍：2019/12/=<V,E>的顶点集V分成两个子集V1和V2,且V=V1∪V2,V1∩V2=?。使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G是二部图或偶图,记作G=<V1,V2,E>,称V1和V2为互补顶点子集,或称V1,V2是V的划分。在一个二部图G=<V1,V2,E>中,若|V1|=m,|V2|=n,且对任意的u∈V1,v∈V2均有(u,v)∈E,则称G为完全二部图,记为Km,n。完全二部图此两图均是K3,3,?G中无奇数长度的回路。说明:二部图G中所有基本圈/初级回路的长度为偶数。证明必要性:设图G是偶图G=<V1,V2,E>,令C=v0,v1,v2,…,vk,v0是G的一条回路,其长度为k+1。不失一般性,假设v0∈V1,由偶图的定义知v1∈V2,v2∈V1。由此可知,v2i∈V1且v2i+1∈V2。又因为v0∈V1,所以vk∈V2,因而k为奇数,故C的长度为偶数。充分性:设G中每条回路的长度均为偶数,若G是连通图,任选v0∈V,定义V的两个子集如下V1={vi|d(v0,vi)为偶数}V2=V-V1现证明V1中任两结点间无边存在。假若存在一条边(vi,vj)∈E,其中vi,vj∈V1,则由v0到vi间的短程线(长度为偶数)以及边(vi,vj)再加上vj到v0间的短程线(长度为偶数)所组成的回路的长度为奇数,与假设矛盾。同理可证V2中任两结点间无边存在。