二部图与完全二部图详解_第1页
二部图与完全二部图详解_第2页
二部图与完全二部图详解_第3页
二部图与完全二部图详解_第4页
二部图与完全二部图详解_第5页
已阅读5页,还剩18页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

(优选)二部图与完全二部图课件计算机数学1目前一页\总数二十三页\编于十八点二部图

定义设无向图G=<V,E>,若能将V划分成V1和V2(V1V2=V,V1V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为<V1,V2,E>,称V1和V2为互补顶点子集.又若G是简单图,且V1中每个顶点都与V2中每个顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.

注意:n阶零图为二部图.2目前二页\总数二十三页\编于十八点二部图的判别法

定理无向图G=<V,E>是二部图当且仅当G中无奇圈

例下述各图都是二部图

3目前三页\总数二十三页\编于十八点

欧拉图历史上的哥尼斯堡七桥问题是著名的图论问题。

问题是这样的:18世纪的东普鲁士有个哥尼斯堡城,在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥,它们把河的两岸和两个岛连接起来(如图1)。每逢假日,城中居民进行环城游玩,人们对此提出了一个“遍游”问题,即能否有这样一种走法,使得从某地出发通过且只通过每座桥一次后又回到原地呢?4目前四页\总数二十三页\编于十八点我们将图1中的哥尼斯堡城的4块陆地部分分别标以A,B,C,D,将陆地设想为图的结点,而把桥画成相应的连接边,这样图1可简化成图2。于是七桥“遍游”问题等价于在图2中,从某一结点出发找到一条回路,通过它的每条边一次且仅一次,并回到原来的结点。5目前五页\总数二十三页\编于十八点

定义1

给定无孤立结点的图G,若存在一条经过G中每边一次且仅一次的回路,则该回路为欧拉回路。具有欧拉回路的图称为欧拉图。例如,给出如图3所示的两个图,容易看出,(a)是欧拉图,而(b)不是欧拉图。6目前六页\总数二十三页\编于十八点

下图中,(a)图的每个结点的度数都为4,所以它是欧拉图;(b)图不是欧拉图。但我们继续考察(b)图可以发现,该图中有一条路v2v3v4v5v2v1v5,它经过(b)图中的每条边一次且仅一次,我们把这样的路称为欧拉路。定理1连通图G是欧拉图的充要条件是G的所有结点的度数都是偶数。7目前七页\总数二十三页\编于十八点

定义2

通过图G的每条边一次且仅一次的路称为图G的欧拉路。

对于欧拉路有下面的判定方法。

定理2

连通图G具有一条连接结点vi和vj的欧拉路当且仅当vi和vj是G中仅有的两个奇数度结点。8目前八页\总数二十三页\编于十八点我国民间很早就流传一种“一笔画”游戏。由定理1和定理2知,有两种情况可以一笔画。

1)如果图中所有结点是偶数度结点,则可以任选一点作为始点一笔画完;

2)如果图中只有两个奇度结点,则可以选择其中一个奇度结点作为始点也可一笔画完。9目前九页\总数二十三页\编于十八点【例】下图是一幢房子的平面图形,前门进入一个客厅,由客厅通向4个房间。如果要求每扇门只能进出一次,现在你由前门进去,能否通过所有的门走遍所有的房间和客厅,然后从后门走出。10目前十页\总数二十三页\编于十八点解:将4个房间和一个客厅及前门外和后门外作为结点,若两结点有边相连就表示该两结点所表示的位置有一扇门相通。由此得图(b)。由于图中有4个结点是奇度结点,故由定理7.4.2知本题无解。11目前十一页\总数二十三页\编于十八点

定理3

一个连通有向图具有(有向)欧拉回路的充要条件是图中每个结点的入度等于出度。一个连通有向图具有有向欧拉路的充要条件是最多除两个结点外的每个结点的入度等于出度,但在这两个结点中,一个结点的入度比出度大1,另一个结点的入度比出度少1。类似于无向图的结论,对有向图有以下结果。12目前十二页\总数二十三页\编于十八点平面图和平面嵌入定义如果能将图G除顶点外边不相交地画在平面上,则称G是平面图.这个画出的无边相交的图称作G的平面嵌入.没有平面嵌入的图称作非平面图.

例如下图中(1)~(4)是平面图,(2)是(1)的平面嵌入,(4)是(3)的平面嵌入.(5)是非平面图.目前十三页\总数二十三页\编于十八点平面图和平面嵌入(续)今后称一个图是平面图,可以是指定义中的平面图,又可以是指平面嵌入,视当时的情况而定.当讨论的问题与图的画法有关时,是指平面嵌入.K5和K3,3是非平面图设GG,若G为平面图,则G也是平面图;若G为非平面图,则G也是非平面图.Kn(n5),K3,n(n3)都是非平面图.平行边与环不影响图的平面性.K5K3,3目前十四页\总数二十三页\编于十八点平面图的面与次数设G是一个平面嵌入G的面:由G的边将平面划分成的每一个区域无限面(外部面):面积无限的面,用R0表示有限面(内部面):面积有限的面,用R1,R2,…,Rk表示面Ri的边界:包围Ri的所有边构成的回路组面Ri的次数:Ri边界的长度,用deg(Ri)表示说明:构成一个面的边界的回路组可能是初级回路,简单回路,也可能是复杂回路,还可能是非连通的回路之并.定理

平面图各面的次数之和等于边数的2倍.目前十五页\总数二十三页\编于十八点平面图的面与次数(续)例1右图有4个面,deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.请写各面的边界.例2左边2个图是同一个平面图的平面嵌入.R1在(1)中是外部面,在(2)中是内部面;R2在(1)中是内部面,在(2)中是外部面.其实,在平面嵌入中可把任何面作为外部面.目前十六页\总数二十三页\编于十八点欧拉公式定理11(欧拉公式)设G为n阶m条边r个面的连通平面图,则nm+r=2.证对边数m做归纳证明.m=0,G为平凡图,结论为真.设m=k(k0)结论为真,m=k+1时分情况讨论如下:(1)G中无圈,则G必有一个度数为1的顶点v,删除v及它关联的边,记作G.G连通,有n-1个顶点,k条边和r个面.由归纳假设,(n-1)-k+r=2,即n-(k+1)+r=2,得证m=k+1时结论成立.(2)否则,删除一个圈上的一条边,记作G.G连通,有n个顶点,k条边和r-1个面.由归纳假设,n-k+(r-1)=2,即n-(k+1)+r=2,得证m=k+1时结论也成立.证毕.目前十七页\总数二十三页\编于十八点哈密尔顿图

与欧拉回路类似的是哈密尔顿回路问题。它是1859年哈密尔顿首先提出的一个关于12面体的数学游戏:能否在下页图中找到一个回路,使它含有图中所有结点一次且仅一次?若把每个结点看成一座城市,连接两个结点的边看成是交通线,那么这个问题就变成能否找到一条旅行路线,使得沿着该旅行路线经过每座城市恰好一次,再回到原来的出发地呢?为此,这个问题也被称作周游世界问题。18目前十八页\总数二十三页\编于十八点12面体游戏示图

对右图

,图中粗线给出了这样的回路。

定义4

给定图G,若有一条路通过G中每个结点恰好一次,则这样的路称为哈密尔顿路;若有一个圈,通过G中每个结点恰好一次(起点两次),这样的圈称为哈密尔顿回路(或哈密尔顿圈)。具有哈密尔顿回路的图称为哈密尔顿图。19目前十九页\总数二十三页\编于十八点尽管哈密尔顿回路与欧拉回路问题在形式上极为相似,但是到目前为止还不知道一个图为哈密尔顿图的充要条件,寻找该充要条件仍是图论中尚未解决的主要问题之一。下面先给出一个简单而有用的必要条件。定理1设图G=〈V,E〉是哈密尔顿图,则对于V的每个非空子集S,均有W(G-S)≤|S|成立,其中W(G-S)是图G-S的连通分支数。20目前二十页\总数二十三页\编于十八点21目前二十一页\总数二十三页\编于十八点判断哈密尔顿图的充分条件很多,我们仅介绍一个。定理2

设G=〈V,E〉是有n个结点的简单图,

1)如果任一对不相邻结点u,v∈V,均有

deg(u)+deg(v)≥n-1,则在G中存在一条哈密尔顿路;

2)如果任一对不相邻结点u,v∈V,均有

deg(u)+deg(v)≥n,则G是哈密尔顿图。22目前二十二页\总数二十三页\编于十八点【例3】某地有5个风景点。若每个景点均有两条道路与其他景点相通,问是否可经过每个景点恰

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论