下载此文档

一些特殊的图.ppt


文档分类:建筑/环境 | 页数:约38页 举报非法文档有奖
1/38
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/38 下载此文档
文档列表 文档介绍
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中任两结点间无边存在。

一些特殊的图 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数38
  • 收藏数0 收藏
  • 顶次数0
  • 上传人282975922
  • 文件大小4.59 MB
  • 时间2020-07-31