部图与完全二部.ppt

《部图与完全二部.ppt》由会员分享，可在线阅读，更多相关《部图与完全二部.ppt（24页珍藏版）》请在三一办公上搜索。

1、二部图,二部图完全二部图,1,二部图,定义 设无向图 G=,若能将V 划分成V1 和 V2(V1V2=V,V1V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为,称V1和V2为互补顶点子集.又若G是简单图,且V1中每个顶点都与V2中每个顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.注意:n 阶零图为二部图.,2,二部图的判别法,定理 无向图G=是二部图当且仅当G中无奇圈 例 下述各图都是二部图,3,欧拉图,历史上的哥尼斯堡七桥问题是著名的图论问题。问题是这样的：18世纪的东普鲁士有个哥尼斯堡城，在横贯全城的普雷格尔河两岸和两个

2、岛之间架设了7座桥，它们把河的两岸和两个岛连接起来（如图1）。每逢假日，城中居民进行环城游玩，人们对此提出了一个“遍游”问题，即能否有这样一种走法，使得从某地出发通过且只通过每座桥一次后又回到原地呢？,4,我们将图1中的哥尼斯堡城的4块陆地部分分别标以A，B，D，将陆地设想为图的结点，而把桥画成相应的连接边，这样图1可简化成图2。于是七桥“遍游”问题等价于在图2中，从某一结点出发找到一条回路，通过它的每条边一次且仅一次，并回到原来的结点。,5,定义 1 给定无孤立结点的图G，若存在一条经过G中每边一次且仅一次的回路，则该回路为欧拉回路。具有欧拉回路的图称为欧拉图。例如，给出如图3所示的两个图，

3、容易看出，(a)是欧拉图，而(b)不是欧拉图。,6,下图中，(a)图的每个结点的度数都为，所以它是欧拉图；(b)图不是欧拉图。但我们继续考察(b)图可以发现，该图中有一条路v2v3v4v5v2v1v5，它经过(b)图中的每条边一次且仅一次，我们把这样的路称为欧拉路。,定理 1 连通图G是欧拉图的充要条件是G的所有结点的度数都是偶数。,7,定义2 通过图G的每条边一次且仅一次的路称为图G的欧拉路。对于欧拉路有下面的判定方法。定理2 连通图G具有一条连接结点vi和vj的欧拉路当且仅当vi和vj是G中仅有的两个奇数度结点。,8,我国民间很早就流传一种“一笔画”游戏。由定理1和定理2知，有两种情况可以

4、一笔画。1)如果图中所有结点是偶数度结点，则可以任选一点作为始点一笔画完；2)如果图中只有两个奇度结点，则可以选择其中一个奇度结点作为始点也可一笔画完。,9,【例】下图是一幢房子的平面图形，前门进入一个客厅，由客厅通向4个房间。如果要求每扇门只能进出一次，现在你由前门进去，能否通过所有的门走遍所有的房间和客厅，然后从后门走出。,10,解:将4个房间和一个客厅及前门外和后门外作为结点，若两结点有边相连就表示该两结点所表示的位置有一扇门相通。由此得图(b)。由于图中有4个结点是奇度结点，故由定理知本题无解。,11,定理3 一个连通有向图具有（有向）欧拉回路的充要条件是图中每个结点的入度等于出度。一

5、个连通有向图具有有向欧拉路的充要条件是最多除两个结点外的每个结点的入度等于出度，但在这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度少1。,类似于无向图的结论，对有向图有以下结果。,12,平面图和平面嵌入,定义 如果能将图G除顶点外边不相交地画在平面上,则称G是平面图.这个画出的无边相交的图称作G的平面嵌入.没有平面嵌入的图称作非平面图.例如 下图中(1)(4)是平面图,(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.(5)是非平面图.,平面图和平面嵌入(续),今后称一个图是平面图,可以是指定义中的平面图,又可以是指平面嵌入,视当时的情况而定.当讨论的问题与图的画法有关时,是

6、指平面嵌入.K5和K3,3是非平面图设G G,若G为平面图,则G 也是 平面图;若G 为非平面图,则G也 是非平面图.Kn(n5),K3,n(n3)都是非平面图.平行边与环不影响图的平面性.,平面图的面与次数,设G是一个平面嵌入G的面:由G的边将平面划分成的每一个区域无限面(外部面):面积无限的面,用R0表示有限面(内部面):面积有限的面,用R1,R2,Rk表示 面Ri的边界:包围Ri的所有边构成的回路组面Ri的次数:Ri边界的长度，用deg(Ri)表示 说明:构成一个面的边界的回路组可能是初级回路,简单回路,也可能是复杂回路,还可能是非连通的回路之并.定理 平面图各面的次数之和等于边数的2倍

7、.,平面图的面与次数(续),例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-

8、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面体的数学游戏：能否在下页图中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次

9、，再回到原来的出发地呢？为此，这个问题也被称作周游世界问题。,18,12 面体游戏示图,对右图，图中粗线给出了这样的回路。定义4 给定图G，若有一条路通过G中每个结点恰好一次，则这样的路称为哈密尔顿路；若有一个圈，通过G中每个结点恰好一次(起点两次)，这样的圈称为哈密尔顿回路（或哈密尔顿圈）。具有哈密尔顿回路的图称为哈密尔顿图。,19,尽管哈密尔顿回路与欧拉回路问题在形式上极为相似，但是到目前为止还不知道一个图为哈密尔顿图的充要条件，寻找该充要条件仍是图论中尚未解决的主要问题之一。下面先给出一个简单而有用的必要条件。,定理1 设图GV,E是哈密尔顿图，则对于V的每个非空子集S，均有W（GS）|

10、S|成立，其中W（GS）是图GS 的连通分支数。,20,21,判断哈密尔顿图的充分条件很多，我们仅介绍一个。,定理2 设GV,E是有n个结点的简单图，1）如果任一对不相邻结点u，vV，均有 deg(u)deg(v)n1，则在G中存在一条哈密尔顿路；2）如果任一对不相邻结点u，vV，均有 deg(u)deg(v)n，则G是哈密尔顿图。,22,【例3】某地有个风景点。若每个景点均有两条道路与其他景点相通，问是否可经过每个景点恰好一次而游完这处？解 将景点作为结点，道路作为边，则得到一个有个结点的无向图。由题意，对每个结点vi，有 deg(vi)2（i5）。,则对任两点vi，vj（i，j5）均有 deg(vi)deg(vj)22451 可知此图一定有一条哈密尔顿路，本题有解。,23,谢谢大家！,24,