《第8章___图论.ppt》由会员分享，可在线阅读，更多相关《第8章___图论.ppt（205页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第7章 图论主要内容 n7.1图的基本概念n7.2路径和回路n7.3图的矩阵表示n7.4二部图n7.5平面图n7.6树n7.7有向树n7.8运输网络n1736年29岁的欧拉向圣彼得堡科学院递交了哥尼斯堡的七座桥的论文，在解答问题的同时，开创了数学的一个新的分支-图论与几何拓扑。也由此展开了数学史上的新进程。问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。七桥问题和欧拉定理。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为“欧拉定理”。图论的起源n第一个图论问题Knisbergssev
2、enbridgeproblem(哥尼斯堡七桥问题)图论起源Euler 1736年：柯尼斯堡七桥问题，年：柯尼斯堡七桥问题，在在哥尼斯堡哥尼斯堡的的一个公园里，有七座桥将一个公园里，有七座桥将普雷格尔普雷格尔河中两个岛及岛河中两个岛及岛与河岸连接起来，问是否可能从这四块陆地中任一与河岸连接起来，问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？块出发，恰好通过每座桥一次，再回到起点？环游世界与Hamilton问题n十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？Hamilton圈（环球旅行游戏）圈（环球旅行游戏）地
3、图着色与四色问题n任意一张地图，最少需要用多少颜色來着色，才能让相邻的两块涂上不同的颜色？1852年提出四色猜想1879年A.Kempe宣布证明了四色定理1890年Heawood发现Kempe的错误1976年美国数学家K.Appel及W.Haken在计算机的辅助下解決n四色问题是世界近代三大数学难题之一。地图四色定理(Fourcolortheorem)最先是由一位叫古德里（FrancisGuthrie）的英国大学生提出来的。德摩尔根（AugustusDeMorgan，18061871）1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。一个多世纪以来，数学家们为证明这条
4、定理绞尽脑汁，所引进的概念与方法刺激了拓扑学与图论的生长、发展。1976年美国数学家阿佩尔（K.Appel）与哈肯（W.Haken）宣告借助电子计算机获得了四色定理的证明，又为用计算机证明数学定理开拓了前景。图论的应用n广播频道与着色问题当两个广播电台距离太近时,若给它们相同的频道会产生干扰。如何设置每个电台的频道,使得它们既不相互干扰,又使频道总数最少?AB广播频道与着色问题n图的点着色(Coloring)药品存放与无关集n化学药品存放问题某些药品放置太近可能爆炸，有两个实验室，最多能有多少药品能放在一起碰!药品存放与无关集配对问题与匹配(Matching)n配对问题有一些机器人要分配任务，
5、并不是所有机器人都能够完成所有的任务，要求每个机器人都要分配一项工作，怎么分？ABCcba电灯管道与覆盖集(Covering)问题n电灯管道问题某座办公大楼平面图如下,每道走廊都装设了电灯,其开关可设于此走廊两端的转角口其中之一。要使安裝了开关的转角口越少越好,要怎么安裝?信息流传与广播问题(Broadcasting)n信息流传问题班上有一件事情要宣布，班长想打电話告訴全班。但若他一个个打似乎太慢了。假设一个班有五十人，打一通电话需要一分钟，那总共就需要四十九分钟。但若是他打了第一个电话后，便请第一个同学再打给別人；第二通电话打了之后，又再请第二个同学打给別人；依此类推，但问题是，也许某些同学
6、沒有某些同学的电话，那么这时，怎样在最短时间內打完所有电话？5 5次次6 6次次计算机网络与连通度(Connectivity)问题n计算机网络断线问题一公司内有多部计算机并连成网络,我们想知道其网络设计得好不好。考虑若有某线路毁损后,所有的机器是否仍可彼此互通?进一步,讨论该网络设计可保证在同时至多有几条线路毁损后仍互通?7.1 图的基本概念 n7.1.1图n定义7.11一个图G是一个三重组V(G):vertexset(顶点或结点集合)，非空有限集E(G):edgeset(边集合)，有限集G是从边集E到结点偶对集合上的函数图也可以用二元组来描述例nV(G)=a,b,c,dnE(G)=e1,e2
7、,e3,e4,e5,e6,e7nG(e1)=(a,b),G(e2)=(a,c),G(e3)=(b,d),G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d),G(e7)=(b,b)图的图形表示G=n结点偶对可以是有序的,也可以是无序的n若边e所对应的偶对是有序的,则称e是有向边有向边简称弧,a叫弧e的始点,b叫弧e的终点n若边e所对应的偶对(a,b)是无序的,则称e是无向边na,b统称为e的端点n称e是关联于结点a和b的n结点a和结点b是邻接的，记为a Adj b(若a和b不邻接，记为a NAdj b)n有向图n无向图无向图n混合图例G=a,b,c,d,e,f,无向图图中的一
8、些基本概念n不与任何结点邻接的结点称为弧立结点弧立结点n全由孤立结点构成的图称为零图零图n关联于同一结点的一条边称为自回路自回路n平行边平行边有向图中,同始点和同终点的边无向图中,两结点间的多条边两结点间平行边的条数称为边的重数n定义8.12含有平行边的图称为多重图非多重图称为线图无自回路的线图称为简单图简单图nn个顶点m条边的简单图记为(n,m)图例abcdfeababcde(6,9)图(5,0)图赋权图n定义7.13赋权图G是一个三重组或四重组,其中V是结点集合,E是边的集合,f是定义在V上的函数,g是定义在E上的函数例nV=v1,v2,v3n E=e1,e2=(v1,v2),(v2,v3
9、)nf(v1)=5,f(v2)=8,f(v3)=11ng(e1)=4.6,g(e2)=7.57.1.2 结点的次数n定义8.14与顶点v相关连的边的条数叫做v的次数(度)，用deg(v)表示,或简记为d(v)n孤立结点的次数为零n握手定理定理8.11设G是一个(n,m)图,它的结点集合为V=v1,v2,vn,则n定理7.12在图中,次数为奇数的结点必为偶数个证明证明 设图设图G G中，奇数度结点集为中，奇数度结点集为V V1 1，偶数度结点，偶数度结点 集为集为V V2 2，边数为，边数为m m，则则 于是于是 因为因为 和和2m2m均为偶数，所以均为偶数，所以也也必必为为偶偶数数。由由于于当
10、当v v V V1 1时时，deg(v)deg(v)均均为为奇奇数数，因此因此|V|V1 1|必为偶数。必为偶数。思考题n我们把有p个顶点的图称为p阶图，考虑以下几个问题p阶简单图中顶点的最大度数是多少？证明：在任何p(p2)阶简单图中，至少有两个顶点具有相同的度n设G是一个有19条边的图，且图中顶点的度至少是3，那么G的阶最大是多少？n说明下面的序列中哪些不可能是图的度序列，哪些不可能是简单图的度序列(1,3,3,3,3,3,4,4,5)(7,6,5,4,3,2,2)(6,6,5,4,3,3,1)(2,4,4,3,3)正则图n定义7.15各结点的次数均相同的图称为正则图,各结点的次数均为k时
11、称为k正则图彼得森彼得森(Petersen)图图思考：是否存在奇数阶奇数度正则图？思考：是否存在奇数阶奇数度正则图？7.1.3 图的同构n定义7.1.6设G=和G=是两个图,若存在从V到V的双射函数,使对任意a、bV,a Adjb当且仅当(a)Adj(b),并且a,b和(a),(b)有相同的重数,则称G和G是同构的，记为G G。两图同构是相互的:GGGG.两图同构时不仅结点之间要有一一对应关系,而且要求这种对应关系保持结点间的邻接关系.例1234GabcdGf:V(G)V(G)f(1)=a,f(2)=b,f(3)=c,f(4)=dx,y V(G),若xAdj y,则f(x)Adjf(y)123
12、456HabcdefH1a,2b,3c,4d,5e,6f两图同构的必要条件n结点数相等n边数相等n度数相同的结点数相等n注意注意：不是充分条件GG思考题n下图中G=（V，E）与G=（V，E）同构吗？7.1.4 图的运算n定义7.17设图G1=和图G2=(1)G1与G2的并,定义为图G3,其中V3=V1V2,E3=E1E2,记为G3=G1G2(2)G1与G2的交,定义为图G3,其中V3=V1V2,E3=E1E2,记为G3=G1G2(3)G1与G2的差,定义为图G3,其中E3=E1-E2,V3=(V1-V2)E3中边所关联的顶点,记为G3=G1-G2(4)G1与G2的环和,定义为图G3,G3=(G
13、1G2)-(G1G2),记为G3=G1G2n两种操作(1)删去图G的一条边e(2)删去图G的一个结点v7.1.5 子图与补图n定义8.18设G=和G=是两个图(1)若VV，EE，则称G是G的子图，记作GG；若VV，EE，则称G是G的真子图；(2)若V=V，EE，则称G是G的生成子图(3)若子图G中没有孤立结点,G由E唯一确定,则称G为由边集E导出的子图(4)若在子图G中,对V中的任意二结点u、v,当uvE时有uvE,则G由V唯一确定,此时称G为由结点集V导出的子图V 导出的子图导出的子图G 是以是以V 为其结点集为其结点集,所有所有在在G中同时关联于中同时关联于V 中两点的边为其边集中两点的边
14、为其边集完全图n定义7.19无向图中，n阶n-1-正则图称为完全图,记为KnK1K2K3K4K5提问：提问：n阶完全图有多少条边？阶完全图有多少条边？补图n定义7.110设G和H是Kn的两个生成子图，若E(G)E(H)=,E(G)E(H)=E(Kn),则称图H与图G互补,记为H=Gc或H=G或HK4GGH自补图n若图H是图G的补图，且G H，则称G为自补图n例GH自补图的阶只可能是自补图的阶只可能是4k，或，或4k+1证明：设(n,m)图G是自补图，则G的边数为n(n-1)/2-m=m n(n-1)=4m思考题n用红色和蓝色的笔给K6的边着色。对于任何一种随意的涂边方式，总有一个所有边被涂上红
15、色的K3，或一个所有边被涂上蓝色的K3n推论:任何6人的人群中,或者有3人互相认识,或者有3人彼此陌生fabc7.2 路径和回路n7.2.1路径和回路设viG,viAdj vi+1(00n-1),则：顶点序列v0v1.vn称为一条v0到vn的长度为n的通通道道(路径路径)。若v0=vn，则称它为闭通道闭通道(回路回路)没有重复边的通道称为迹迹(简单路径简单路径)，闭迹成为圈圈(简单回路简单回路)。完全没有重复顶点的通道称为路径路径(基本路径基本路径)，闭路径称为初等圈初等圈(基本回路基本回路)通常，用k-通道表示长度为k的通道例v1v2v3v4v5是一条4-路径v1v2v3v4v3是一条4-通
16、道v1v2v3v4v5v6v3v7是一条7-迹v1v2v3v4v5v6v3v7v1是一个圈（闭迹）n两顶点之间有通道iff两顶点之间有路径定理7.21在一个具有n个结点的简单图G=中,如果从v1到v2有一条通道,则从v1到v2有一条长度不大于n-1的路径证明：假定从v1到v2存在一条通道(v1,vi,v2),如果其中有相同的结点vk,如(v1,vi,vk,vk,v2),则删去从vk到vk的这些边,它仍是从v1到v2的路径,如此反复地进行直至(v1,vi,v2)中没有重复结点为止，得到一条路径。路径的长度比所经结点数少1,图中共n个结点,故路径长度不超过n-1。n定理7.22在一个具有n个结点的
17、简单图G=中,如果经v1有一条简单回路,则经v1有一条长度不超过n的基本回路。n定义7.23在图G=中,从结点vi到vj最短路径的长度叫从vi到vj的距离,记为d(vi,vj)。若从vi到vj不存在路径,则d(vi,vj)=7.2.2 连通图n定义7.24设G=是图,且vi、vjV。如果从vi到vj存在一条路径,则称vj从vi可达。vi自身认为从vi可达n定义7.25在无向图G中,如果任两结点可达,则称图G是连通的(connected),称G为连通图连通图；称G的极大连通子图G(没有包含G的更大的子图G是连通的)是G的连通分图(简称分图，或连通支，简称支)。n仅有一个孤立结点的图定义它为连通图
18、割点和桥n定义:设图G是连通图，若SV(G)，且G-S不连通或为孤立点，则称S为G的点分离集点分离集(割点集)；若LE(G)，且G-L不连通，则称L为G的线分离集线分离集(割边集)；n特殊的，若uV(G)，且G-u不连通，则称u为G的割点割点(cut-node).若eE(G)，且G-e不连通，则称u为G的割边割边(cut-edge)(桥桥,bridge).abcdefghijkln(n,n-1)连通图至少有一个奇度顶点(n1)n若图G恰有两个奇度顶点，则必有连接这两顶点的路径n若图G中顶点的最小度数大于等于2，则图G必含圈n至少有n条边的n阶图必含圈n若图G中顶点的最小度数大于等于k，则G有k
19、长路n简单连通非完全图G中，必有顶点u,v,w,使得u Adj v,v Adj w,u NAdj wn若图G不连通，则图G的补图连通思考题n顶点x是连通图G的割点，iffu,vG，使得连接u和v的路径都经过xn边e是G的桥，iff e不包含在G的任一圈中n若连通图中每个顶点的度为偶数，则G无桥n设G是n阶简单图(n3)，如果u,vG有deg(u)+deg(v)n-1那么G是连通的思考题n定理：n阶连通图至少有n-1条边证明：对n行数学归纳法(1)n=1时，一阶连通图有0条边n=2时，二阶连通图有1条边n=3时，三阶连通图至少有2条边(2)假设k阶连通图至少有k-1条边，k3，现考虑k+1阶连通
20、图G，取G中一非割点u，由G的连通性可知deg(u)1，而G-u是k阶连通图，它至少有k-1条边，故G至少有k条边n定理7.23设G是任一(n,m)无向简单图,是其分图个数,则n-m证明：设n1,n2,n和m1,m2,m是G的每一个分图的顶点数和边数由于各分图都是连通子图，所以有mini-1则mi(ni-1)，即mn-n*7.2.3赋权图中的最短路径7.2.4 欧拉(Euler)路径和欧拉回路n定义7.4.1通过于图G的每条边一次且仅一次的路径，称为欧拉路径欧拉路径；通过图G的每条边一次且仅一次的回路称为欧拉回路欧拉回路。由欧拉回路构成的图，称为欧拉图欧拉图n定理7.24无向连通图G具有一条欧
21、拉路径当且仅当G具有零个或两个奇数次数的顶点证明：必要性。如果图具有欧拉路径,那么顺着这条路径画出的时候,每次碰到一个顶点,都需通过关联于这个顶点的两条边,并且这两条边在以前未画过。因此,除路径的两端点外,图中任何顶点的次数必是偶数。如果欧拉路径的两端点不同,那么它们就是仅有的两个奇数顶点,如果它们是重合的,那么所有顶点都有偶数次数,并且这条欧拉路径成为一条欧拉回路。必要性得证充分性。从两个奇数次数的顶点之一开始(若无奇数次数的顶点,可从任一点开始),构造一条欧拉路径。以每条边最多画一次的方式通过图中的边。对于偶数次数的顶点,通过一条边进入这个顶点,总可通过一条未画过的边离开这个顶点。因此,这
22、样的构造过程一定以到达另一个奇数次数顶点而告终(若无奇数次数的顶点,则以回到原出发点而告终)。如果图中所有边已用这种方法画过,显然,这就是所求的欧拉路径。如果图中不是所有边被画过,我们去掉已画过的边,得到由剩下边组成的一个子图,这个子图的顶点次数全是偶数。并且因为原来的图是连通的,因此,这个子图必与我们已画过的路径在一个点或多个点相接。由这些顶点中的一个开始,我们再通过边构造路径,因为顶点次数全是偶数,因此,这条路径一定最终回到起点。我们将这条路径已构造好的路径组合成一条路径。如果必要,这一论证重复下去,直到我们得到一条通过图中所有边的路径,即欧拉路径。n推论无向连通图G为欧拉图的充要条件是G
23、的每一结点的度均为偶数n下图中的各图是否可以一笔画出？NYYN思考题n有2k个奇度点的连通图至少需要几笔才能画下来？n令C(G)表示图G的分图数，若G是Euler图，则uG，C(G-u)deg(u)/27.2.5 哈密尔顿(Hamilton)路径与哈密尔顿回路n通过图G的每个结点一次且仅一次的路称为哈密尔顿路径哈密尔顿路径。通过图G的每个结点一次且仅一次的回路称为哈密尔顿回路哈密尔顿回路（哈密尔顿环）。具有哈密尔顿回路的图称为哈密哈密尔顿图尔顿图哈路哈路哈环哈环哈环哈环无无n定理7.26若G=是哈密尔顿图,则对V的每个非空真子集S均成立:(G-S)S这里|S|表示S中的顶点数,(G-S)表示G
24、删去顶点集S后得到的图的连通分图个数。证明：设C是图的一条哈密尔顿回路,则对于S中的任一顶点v1，C-v1是一条包含G中除v1外的所有顶点的路径。若再取S中的顶点v2，则(C-v1-v2)2，由数学归纳法原理可得(C-S)S又C-S是G-S的一个生成子图，故(G-S)(C-S)SHamilton图的必要条件例n注意注意：是必要条件，非充分条件n推论若图G=含有哈密尔顿路径，则对于V的任意一个真子集S，有(GS)|S|+1思考题n若G有度为1的顶点，G是否可能是Hamilton图n若G有割点，G是否可能是Hamilton图n若G有桥，G是否可能是Hamilton图n定理设G=是具有n个顶点的简单
25、无向图,若在G中每一对顶点的次数之和大于等于n-1,则在G中存在一条哈密尔顿路径。证明：前面已证这样的图是连通的，故G中任意两点之间有路径，设P=v1v2vm是G中最长的一条路径(长度为m-1)可证明它就是一条Hamilton路径，即n=m假若不然，若mn，我们可以按以下方法构造一条m长路径：在mn时，由P的最长性可知，v1，vm只能与P中的点邻接，分两种情况讨论情况1：若v1Adj vm，则v1v2vmv1是一个m长的圈情况2：若v1NAdj vm,设v1只与vi1,vi2,vik邻接,其中2ijm-1那么vm必与vi1-1,vi2-1,vik-1之一,比如说vj-1邻接,否则与vm邻接的顶
26、点不超过m-1-k个,即deg(v1)+deg(vm)k+m-1-kn-1矛盾Hamilton图的充分条件vmv1vjvj-1uxu1uR+1umuR-1uRu2现在已经构造得到一个m长的圈，重新标记图的顶点使这个圈为u1u2umu1因为G连通，且前面假设mn，所以G中必有一个不属于该圈的顶点ux与该圈的某一个顶点邻接于是G有一条m长路径uxuRuR+1umu1u2uR-1，与P是最长路矛盾n定理7.27设G=是具有n个顶点的简单无向图,若在G中每一对顶点的次数之和大于等于n,则在G中存在一条哈密尔顿回路。证明：已证明这样的图中有哈密尔顿路径P=v1v2vnvnv1vjvj-1情况1：若v1A
27、dj vn，则v1v2vnv1是一个Hamilton圈情况2：若v1NAdj vn,设v1只与vi1,vi2,vik邻接,其中2ijn-1那么vn必与vi1-1,vi2-1,vik-1之一,比如说vj-1邻接,否则与vn邻接的顶点不超过n-1-k个,即deg(v1)+deg(vn)k+n-1-kn在这种情况下v1v2vj-1vnvn-1vjv1是一个Hamilton圈n注意注意：定理7.27的条件是充分的但非必要n推论7.27在简单无向图中,若每一顶点的度数大于等于n/2(n3),则该图是哈密尔顿图Hamilton图对编码的一个应用n把圆周等分成2n个扇形,每一扇形代表一个n位二进制串用以表示
28、旋转指针的位置.当n=3时右下图是一例.由于交界附近会出现误差,自然要求相邻二数尽可能接近,即要求相邻二数只有一位不同n此问题可归结为求立方图G=V,E,V=000,001,111,ijk,uvwE当且仅当条件成立,的一条Hamilton路.(解存在但不唯一)111110101100000010011 001000001011111110100101010练习n已知关于a，b，c，d，e，f和g的下述事实：a讲英语；b讲英语和汉语；c讲英语、意大利语和俄语；d讲日语和汉语；e讲德国和意大利语；f讲法语、日语和俄语；g讲法语和德语试问这七个人应如何排座位，才能使每个人都能和他身边的人交谈？BCD
29、EFGA英英法德俄意日汉解：结点为客人;会共同语言的2结点相邻接.则问题归结为求此图的一条Hamilton回路货郎问题(TSP)nTraveling Salesman Problem巡回售货员问题一个售货员希望去访问n个城市的每一个,开始和结束于v1城市。每两城市间都有一条直接通路,我们记vi城市到vj城市的距离为W(i,j),问题是去设计一个算法,它将找出售货员能采取的最短路径给定带权完全图G=，对在V中任意三点vi,vj,vk满足W(i,j)+W(j,k)W(i,k)求最短Hamilton路径TSP问题的复杂性n最原始的方法找出所有可能的旅行路线，从中选取路径长度最短的简单回路abcd25
30、8731序号路径长度1abcda182abdca113acbda234abdba115adbca236adcba18可能的解有可能的解有(n-1)!/2个个，(n-1)!/22n-2，(n4)NP完全问题(NP_Complete)nnon-deterministic polynomial非确定性多项式(NP)nP问题可以由一个确定型图灵机在多项式表达的时间内解决的问题nNP问题在给定肯定解的情况下，可在多项式时间内验证的问题nNP完全问题NP中“最难”的问题TSP无法在多项式表达的时间内解决练习n请画出满足以下条件的图是Euler图，但不是Hamilton图不是Euler图，但是Hamilto
31、n图既是Euler图，又是Hamilton图既不是Euler图，又不是Hamilton图7.3 图的矩阵表示n定义7.31设图G=，其中V=v1，v2，vn，n阶方阵A=（aij），称为G的邻接矩阵。其中第i行j列的元素 例下图的邻接矩阵是：v1v2v3v4v5A(n)的元素的意义n设G的邻接矩阵为A，则矩阵A(l)（l=1，2，）的第i行j列的元素aij(l)表示图G中连接结点vi到vj长度为l的通道的数目n例:由矩阵的乘法运算，图的邻接矩阵A的各次幂如下：v1v2v3v4v5n利用邻接矩阵可知判断G中任意两个结点是否相可达n对l=1，2，n1。依次检查A(l)的（i，j）项元素aij(l)
32、（ij）是否为0，若都为0，那么结点vi与vj不可达，否则vi与vj之间有路径计算结点vi与vj之间的距离n若aij(1)，aij(2)，aij(n-1)中至少有一个不为0，则可断定vi与vj可达，使aij(l)0的最小的l 即为d(vi,vj)n定义7.32设图G=，其中V=v1，v2，vn，n阶方阵A=（Pij），称为G的可达性矩阵。其中第i行j列的元素 例下图的可达性矩阵如下：v1v2v3v4v5可达性矩阵的计算n通过对图G的邻接矩阵A进行运算可得到G的可达性矩阵P。其方法如下：1.由A计算A2，A3，An2.计算B=A+A2+An3.将矩阵B中非零元素改为1，所得到的矩阵即为可达性矩阵
33、P练习n设图G=，其中V=v1，v2，vn，邻接矩阵(1)deg（v1）=？deg（v2）=？()(2)图G是否完全图？（）(3)v1到v2长为3的路有几条？（）deg（v1）=2，deg（v2）=3N47.4 二部图n定义7.41若无向图G=的顶点集合V可以划分成两个子集X和Y,使G中的每一条边e的一个端点在X中,另一个端点在Y中,则称G为二二部图部图或偶图。二部图可记为G=,X和Y称为互补结点子集。n定义7.42二部图G=中,若X的每一顶点都与Y的每一顶点邻接,则称G为完全二部图,记为Km,n,这里m=X,n=Y例v1v2v3v4v5v6v7v1v2v3v4v5v6K3,3K2,4v1v2
34、v3v4v5v6二部图G=，则练习n下列图中哪些是二部图？是是v1v2v3v5v7v8v4v6(a)(b)v1v2v3v4v5(c)v1v4v8v5v2v3v7v6是是n定理7.41无向图G=为二部图的充分必要条件为G中所有回路的长度均为偶数证明：必要性:若G=X,E,Y为二部图,C=(v0,v1,v2,vk,v0)为任一回路,不妨设v0X,则v0,v2,v4,X,v1,v3,v5,Y,k必为奇数,不然,不存在边(vk,v0)。C中共有k+1条边,故C是偶数长度的回路。充分性:不妨设G为任何回路长度均为偶数的连通图.取定v0V后,定义V的一个划分:X=v|d(v0,v)是偶数(易见v0X);Y
35、=V-X用反证法证Y(X)中的任二点不相邻接.若vi,vjY(vi,vj)E,则d(v0,vi),d(v0,vj)都为奇数,由此推出G中有过v0,vi,vj的长为奇数的回路的矛盾.匹配n定义7.43给定一个二部图G=,如果E的子集M中的边无公共端点,则称M为二部图G的一个匹配匹配。含有最多边数的匹配称为G的最大匹配最大匹配(不唯一)。含有G的每一点的匹配称为完美匹配完美匹配(不唯一)v1v2v3v4v5v6v7v8v9v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8交替链n定义7.44如果二部图G中的一条链由不属于匹配M的边和属于M的边交替组成,且链的两端点不是M中边的端点,那
36、么称此链为G中关于匹配M的交替链x1x2x3x4y1y2y3y4y5x2y1x3y4标记法求交替链n首先把X中所有不是M的边的端点用()加以标记,然后交替进行以下所述的过程和。.选一个X的新标记过的结点,比如说xi,用(xi)标记不通过在M中的边与xi邻接且未标记过的Y的所有结点。对所有X的新标记过的结点重复这一过程.选一个Y的新标记过的结点,比如说yi,用(yi)标记通过M的边与yi邻接且未标记过的X的所有结点。对所有Y的新标记过结点重复这一过程。x1x2x3x4y1y2y3y4y5(*)(x2)(x2)(y1)(y3)(x3)(1)把x2标记(*)(2)从x2出发,应用过程,把y1和y3标
37、记(x2)(3)从y1出发,应用过程,把x3标记(y1)。从y3出发,应用过程,把x4标记(y3)(4)从x3出发,应用过程,把y4标记(x3),因y4不是M中边的端点,说明已找到了一条交替链,即(x2,y1,x3,y4)求最大匹配n找出一条关于匹配M的交替链n把中属于M的边从M中删去,而把中不属于M的边添到M中,得到一新集合M,此M也是G的匹配添入的边自身不相交添入的边不与M中不属于的边相交n反复进行这样的过程,直至找不出关于M的交替链为止例x1x2x3x4y1y2y3y4y5取一个初始匹配M=x1y5,x3y1,x4y3用标记法从点x2开始求得一条交替链:=(x2y1x3y4)用调整匹配M
38、:将中属于M的边删去并将其中不属于M的其它边添加到M中，形成M因对M用标记法只能从y2开始,但都不能求出M的任何交替链,故判定M是一个最大匹配M=x1y5,x3y1,x4y3M=x2y1,x1y5,x3y4,x4y3练习n某教研室有4位教师:A,B,C,D.A能教课程5;B能教1,2;C能教1,4;D能教课程3.能否适当分配他们的任务,使4位教师担任4门不同课并且不发生安排教师教他不能教的课的情况?ABCD12345思考题n若mn，Km,n是否是Hamilton图，若m=n呢？解：若mn，Km,n不是Hamilton图不妨设mn，|X|=m,|Y|=n则(G-Y)=m|Y|=n若m=n，Km,
39、n是Hamilton图任意两点的度数之和为2n7.5 平面图n7.5.1平面图一工厂有A、B、C三个车间和L、M、N三个仓库,因为工作需要车间与仓库间将设专用车道,为了避免车祸,车道最好没有交点,问这可能吗?ABCLMNABCLMN线相交处没有顶点的交叉叫假交叉假交叉n一印刷电路板的设计如下图，但现在只剩下一层板子了，能否做到呢？改变图的连线方式去掉一个图所有所有假交叉的过程叫平面嵌入平面嵌入n定义7.51一个无向图G=,如果能平面嵌入，就称之为平面图平面图。K5和K3,3都不是平面图K5和K3,3是两个最简单、但是非常重要的非平面图称一个图中本质上不能去掉的假交叉个数为图的交叉数交叉数，交叉
40、数加1叫做这个图的厚度厚度(thickness)平面图的面(face)n也叫区域(region)n平面图G的面是G中的边所包围的区域，它不再被G的边分成子区域。其中面积无限的区域称为无限面无限面。面积有限的区域称为有限面有限面。包围该面的边所构成的闭通道称为这个面的边界边界(Boundary)，它的长度称为该面的次数次数（deg(r)r1的边界：v1v2v3v1 3次面r2的边界：v2v4v5v8v5v3v26次面r3的边界：v1v2v4v6v7v7v6v4v5v3v110次面v1v2v3v4v5v6v7r1r2r3v8平面图中所有面的次数之平面图中所有面的次数之和等于边数的两倍和等于边数的两
41、倍98R1R2R3R4R5G3v1v2v3v4v5v6v7v8v9Boundary of R1:v1v2v3Boundary of R5:v1v2v3v4v5v6v7v97.5.2 欧拉公式n欧拉1750年提出任何一个凸多面体的顶点数n,棱数m和面数k满足公式:n-m+k=2n适用范围不限于凸多面体n可推广到平面图的情况n定理7.51对任何连通平面图G，若G有n个顶点，m条边，k个面 n-m+k=2v1v2v3v4v5v6v7r1r2r3v8证明：对边数进行归纳。(i)当m=0时,图只有一个顶点没有边,因此,n=1,m=0,k=1,欧拉公式成立。(ii)当m=1时,有两种情况:(1)这条边是自
42、回路,此时n=1,m=1,k=2(2)这条边不是自回路,此时n=2,m=1,k=1显然,这两种情况,欧拉公式都成立。(iii)设m=p(p1)时欧拉公式成立,现考虑有p+1条边，k个面的n阶连通平面图G.分两种情况讨论：(1)若G有1度点u，则G-u是一有p条边，k个面的n-1阶连通平面图由归纳假设，有(n-1)-p+k=2,即n-(p+1)+k=2，欧拉公式成立(2)若G没有1度点，在有限面的边界中取一边e，则G-e是一有p条边，k-1个面的n阶连通平面图，由归纳假设，有n-p+(k-1)=2,即n-(p+1)+k=2，欧拉公式成立总之，欧拉公式对所有有p+1条边的连通平面图成立思考题n若G
43、是无向平面(n,m)图，有个分图，k个面，证明：n m+k=+1n定理7.52，3若G是一个有n(n3)个顶点，m条边的简单连通平面图，且每个面的次数都不小于L(L3)，那么m(n-2)L/(L-2)证明：有欧拉公式得，图G有m-n+2个面，由于每个面的次数不小于L，且所有面的次数之和为2m，所以2mL(m-n+2)化简得m(n-2)L/(L-2)n容易证明(n-2)L/(L-2)是关于L单调下降的所以对阶大于2的简单平面图可取L=3，得到m 3n-6对二部图来说，L4，有m 2n-4n推论7.52K5是非平面图证明：n=5,m=10,结果3n-6m不成立n推论7.53K3,3不是平面图证明：
44、n=6,m=9,结果2n-4m不成立n*7.5.3库拉托夫斯基(Kuratowski)定理定义7.52K5和K3,3称为库拉托夫斯基图v1v2v3v4v5v6n定义7.53两个图G1和G2称为在2度顶点内同构的(或称同胚),如果它们是同构的,或者通过反复插入和(或)除去2度顶点,它们能变换成同构的图。n图G中相邻顶点u,v之间的初等收缩由下面方法给出;删除边(u,v),用新的顶点w取代u,v,使w关联u,v关联的一切边(除(u,v)外)eabcdfghijabcdeabcdghijen定理7.54(库拉托夫斯基定理)一个图是平面图,当且仅当它不包含任何在2度顶点内和库拉托夫斯基图同构的子图。n
45、定理图G是平面图G没有可以边收缩到K5或K3,3的子图eabcdfghijG=G-(j,g),(d,c)，则G与K3,3同胚eabcdfghij思考题n以下哪些图可以作平面嵌入练习n证明：顶点数不少于4的简单连通平面图中，至少有3个顶点之度不大于5nn(n3)个顶点k个面的简单连通平面图中有k2n-4n少于30条边的简单平面图至少有一个顶点的度不大于4图的着色n7.5.4对偶图将平面图G嵌入平面后,通过以下手续(简称D过程):(1)对图G的每个面Di的内部作一顶点且仅作一顶点v*i;(2)经过每两个面Di和Dj的每一共同边界e*k作一条边e*k=(v*i,vj)与ek相交;(3)当且仅当ek只
46、是面Di的边界时,v*i恰存在一自回路与ek相交。所得的图称为图G的对偶图,记为GG与G*的关系n平面图G的对偶图G*是平面图n若连通平面图G是(n,m)图，则它有m-n+2个面，则G*是(m-n+2,m)图，有n个面nG中面的次数为G*中面中点的度数nG的圈对应着G*的割（边）集n通过对偶图，面着色可转换为点着色n若平面图G的对偶图G*与G同构，则称G为自对偶图自对偶图。如果(n,m)图是自对偶图，则m=2(n-1)7.5.5 五色问题n引理在简单连通平面图中至少有一个顶点v0,其次数d(v0)5证明：用反证法设(n,m)图G是简单连通平面图，所有顶点的次数不小于6则m3n-6又2m=d(v
47、)6n，即m 3n，矛盾故存在v0,其次数d(v0)5五色定理n定理7.55用5种颜色可以给任一简单连通平面图G=正常着色证明：对图的顶点数作归纳(i)当n5时,显然成立(ii)假设k个顶点时成立,考虑k+1阶简单连通平面图G.由引理知图G至少存在一顶点v0其次数d(v0)5.显然G-v0是k阶简单连通平面图，由归纳假设，可用5种颜色进行着色。假设已用红、黄、蓝、绿、黑5种颜色对G-v0着好了色，现在考虑对G中顶点v0的着色若d(v0)5，显然可用它的邻接顶点所着颜色之外的一种颜色对v0进行着色，即G可以用5种颜色着色若d(v0)=5，显然只需要考虑与v0邻接的顶点被着以不同的5种颜色的情况进
48、行讨论令W1=x|xG,且x着红色或蓝色，W2=x|xG,且x着黄色或绿色，考虑W1导致的G的导出子图n若v1和v3分属于的两个不同连通分图，那么将v1所在分图的红蓝色对调,并不影响图G-v0的正常着色。然后将v0着上红色,即得图G的正常着色v0v1v2v3v4v5v0v2v3v4v5v1若v1和v3属于的同一分图中,则v1和v3之间必有一条顶点属于红蓝集的路径P,它加上v0可构成回路C:(v0,v1,P,v3,v0)v0v2v3v4v5v1由于C的存在,将黄绿集分为两个子集,一个在C内,另一个在C外,于是黄绿集的导出子图至少有两个分图,一在C内,一在C外。于是问题转化为的类型,对黄绿集按的办
49、法处理,即得图G的正常着色。证毕。思考题n设G是至少有一条边的图，那么什么情况下可以用2种颜色对G进行着色iff G不含奇数长的简单回路n(8,13)简单连通平面图是否可以只用2种颜色着色7.6 树n7.6.1无向树n定义7.61连通而无简单回路的无向图称为无无向向树树，简称树树。树中次数为1的顶点称为树树叶叶。次数大于1的顶点称为分分枝枝点点或内内部部结点结点。n定义7.62一个无向图的诸连通分图均是树时,称该无向图为森林森林,树是森林n定理7.61无向图T是树,当且仅当下列5条之一成立。(1)无简单回路且m=n-1。这里m是边数,n是顶点数(2)连通且m=n-1(3)无简单回路,但增加任一
50、新边,得到且仅得到一条基本回路(4)连通但删去任一边,图便不连通(n2)(5)每一对顶点间有唯一的一条基本路径。(n2)证明(1)：树(1)，即证n阶无圈图恰有n-1条边对n作归纳。(i)n=1时,m=0,显然m=n-1(ii)假设n=k时命题成立,现证明n=k+1时也成立。由于树是连通而无简单回路,所以至少有一个次数为1的顶点v,在T中删去v及其关联边,便得到k个顶点的连通无简单回路图。由归纳假设它有k-1条边。再将顶点v及其关联边加回得到原图T,所以T中含有k+1个顶点和k条边,符合公式m=n-1。所以树是无简单回路且m=n-1的图。于是得出矛盾。所以T是连通且m=n-1的图。证明(2)：