离散数学第6章-图论课件.ppt

1Chapter 6 图论图论n图论是一个古老的数学分支是一个古老的数学分支,它以它以图为研究研究对象。象。图论中的中的图是由若是由若 干干给定的点及定的点及连接两点的接两点的线所所构成的构成的图形，形，这种种图形通常用来描述某些事物之形通常用来描述某些事物之间的某种特定关系，用点代表事物，用的某种特定关系，用点代表事物，用连接两点接两点的的线表示相表示相应两个事物两个事物间具有具有这种关系种关系.n图论近年来近年来发展十分迅速展十分迅速,应用相当广泛用相当广泛,渗透到渗透到许多学科多学科,诸如运筹学、信息如运筹学、信息论、控制、控制论、网、网络理理论、博弈、博弈论、化学、生物学、物理学、社会科学、化学、生物学、物理学、社会科学、语言学言学,特特别是是计算机科学等算机科学等,图论得到广泛的得到广泛的应用用,同同时图论本身也得到了充分的本身也得到了充分的发展展.例例：有有7个个人人围围桌桌而而坐坐，如如果果要要求求每每次次相相邻邻的的人人都都与与以以前前完完全全不不同同，试试问问不不同同的的就就座方案共有多少种？座方案共有多少种？用用顶顶点点表表示示人人，用用边边表表示示两两者者相相邻邻，因因为为最最初初任任何何两两个个人人都都允允许许相相邻邻，所所以以任任何两点都可以有边相连。何两点都可以有边相连。21 12 23 37 76 64 45 53假定第一次就座方案是假定第一次就座方案是（1，2，3，4，5，6，7，1），那那么么第第二二次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续相邻，只能从图中删去这些边。续相邻，只能从图中删去这些边。41 12 23 37 76 64 45 551 12 23 37 76 64 45 561 12 23 37 76 64 45 571 12 23 37 76 64 45 581 12 23 37 76 64 45 591 12 23 37 76 64 45 5101 12 23 37 76 64 45 5111 12 23 37 76 64 45 512假定第二次就座方案是假定第二次就座方案是（1，3，5，7，2，4，6，1），那那么么第第三三次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续相邻，只能从图中删去这些边。续相邻，只能从图中删去这些边。131 12 23 37 76 64 45 5141 12 23 37 76 64 45 5151 12 23 37 76 64 45 5161 12 23 37 76 64 45 5171 12 23 37 76 64 45 5181 12 23 37 76 64 45 5191 12 23 37 76 64 45 5201 12 23 37 76 64 45 5211 12 23 37 76 64 45 5221 12 23 37 76 64 45 5231 12 23 37 76 64 45 5241 12 23 37 76 64 45 5251 12 23 37 76 64 45 5261 12 23 37 76 64 45 5271 12 23 37 76 64 45 5281 12 23 37 76 64 45 529假定第三次就座方案是假定第三次就座方案是（1，4，7，3，6，2，5，1），那那么么第第四四次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻，只只能能从从图图中中删删去去这这些些边边，只只留留下下7点点孤孤立立点点，所所以以该该问问题题只只有有三三个个就就座座方案。方案。30例例：一一个个班班级级的的学学生生共共计计选选修修A、B、C、D、E、F六六门门课课程程，其其中中一一部部分分人人同同时时选选修修D、C、A，一一部部分分人人同同时时选选修修B、C、F，一一部部分分人人同同时时选选修修B、E，还还有有一一部部分分人人同同时时选选修修A、B，期期终终考考试试要要求求每每天天考考一一门门课课，六六天天内内考考完完，为为了了减减轻轻学学生生负负担担，要要求求每每人人都都不不会会连连续续参参加加考考试试，试试设设计计一一个个考试日程表。考试日程表。31解解：以以每每门门课课程程为为一一个个顶顶点点，共共同同被被选选修修的的课课程程之之间间用用边边相相连连，得得图图，按按题题意意，相相邻邻顶顶点点对对应应课课程程不不能能连连续续考考试试，不不相相邻邻顶顶点点对对应应课课程程允允许许连连续续考考试试，因因此此，作作图图的的补补图图，问问题题是是在在图图中中寻寻找找一一条条哈哈密密顿顿道道路路，如如CEAFDB，就就是是一一个个符符合合要要求求的的考考试试课课程表。程表。32A AF FE ED DC CB B33A AF FE ED DC CB B34A AF FE ED DC CB B35A AF FE ED DC CB B36A AF FE ED DC CB B37A AF FE ED DC CB B38A AF FE ED DC CB B39A AF FE ED DC CB B40 图论最早处理的问题是哥尼斯堡城图论最早处理的问题是哥尼斯堡城PregelPregel河上的河上的七桥问题七桥问题：河中有两个岛屿：河中有两个岛屿,人们架设了七座桥把河人们架设了七座桥把河岸和两个小岛连接起来岸和两个小岛连接起来,有人打算在每座桥上通过一有人打算在每座桥上通过一次然后返回出发点次然后返回出发点,但没有获得成功但没有获得成功.后来有人请教当时的大数学家后来有人请教当时的大数学家欧拉欧拉,欧拉用图论的方法证明这个欧拉用图论的方法证明这个问题无解问题无解,同时他提出并解决了更同时他提出并解决了更为一般的问题为一般的问题,从而奠定了图论的从而奠定了图论的基础基础,欧拉也被誉为欧拉也被誉为“图论之父图论之父”.ABCD41 后来后来,英国数学家哈密尔顿在英国数学家哈密尔顿在18561856年提出年提出“周游世界周游世界”的的问题：一个正十二面体问题：一个正十二面体,20,20个顶点分别表示世界上个顶点分别表示世界上2020个大城市个大城市,要求从某个城市出发要求从某个城市出发,经过所有城市一次而不重复经过所有城市一次而不重复,最后回到出最后回到出发地发地.这也是图论中一个著名的问题这也是图论中一个著名的问题.“四色问题四色问题”也是图论中的著名问题：地图着色时也是图论中的著名问题：地图着色时,国境国境线相邻的国家需要着上不同的颜色线相邻的国家需要着上不同的颜色,最少需要几种颜色？最少需要几种颜色？19761976年年,美国人阿佩尔和哈肯用计算机运行美国人阿佩尔和哈肯用计算机运行12001200个小时个小时,证明证明4 4种颜种颜色就够了色就够了.但至今尚有争议但至今尚有争议.42436.1 图的基本概念图的基本概念n哥尼斯堡哥尼斯堡(Kningsberg)七七桥问题:n问题是是:是否可从某一个地方出是否可从某一个地方出发，经过七座七座桥，每座每座桥只只经过一次，然后又回到原出一次，然后又回到原出发点点.ABCDABCD44n程序程序调用的用的图论模型模型:ne8:v3可可调用用v2;e1:v2可可调用用v1;e4:v5可可调用用v5自身自身.451.图的定的定义n定定义 图图G主要由主要由2部分部分组成成:q(1)节点集合点集合V,其中的元素称其中的元素称为节点节点q(2)边集合集合E,其中的元素称其中的元素称为边边n通常将通常将图G记为G=(V,E).46 几点几点说明明:q(a)节点又可以称点又可以称为点、点、顶点或点或结点点,常用一个常用一个实心点或空心心点或空心点表示点表示,为了方便可以在了方便可以在这些符号的旁些符号的旁边或内部写上表意名或内部写上表意名称称.q(b)边及其表示及其表示.n无向无向边?b3=AB=BA=A,B(可重可重).n有向有向边(弧弧)?n所有所有边都是无向都是无向边的的图称称为无向图无向图,所有所有边都是有向都是有向边的的图称称为有向图有向图.ABv2v3b3e8A和和B称为端点称为端点47q(c)我我们讨论的的图不但与不但与节点位置无关点位置无关,而且与而且与边的形状和的形状和长短也无关短也无关.n有有n个个节点的点的图称称为n阶阶图图,有有n个个节点点m条条边的的图称称为(n,m)图图.n在在图G=(V,E)中中,称称V=的的图为空图空图,记为,若若 V 但但 E=的的图称称为零图零图,n 阶零零图可可记为Nn,仅一个一个节点的零点的零图称称为平凡图平凡图.47482.邻接接n定定义 设G=(V,E)是是图,对于任意于任意u,v V,若从若从节点点 u 到到节点点 v 有有边,则称称 u 邻接到邻接到 v 或称或称 u 和和 v 是是邻接的邻接的.n无向无向图?n有向有向图?n无向无向图的的两条两条边邻接接是指它是指它们有公共端点有公共端点.先驱元素先驱元素后继元素后继元素493.关关联n定定义 设G=(V,E)是是图,e E,e的两个端点分的两个端点分别为u和和v,则称称边e与与节点点u以及以及边e与与节点点v是是关联关联的的.n显然然,图的任意一条的任意一条边都关都关联两个两个节点点.n关关联相同两个相同两个节点的点的边称称为吊吊环,可可简称称环环(loop).n关关联的起点与的起点与终点都相同的点都相同的边称称为多重边多重边或平行或平行边,其其边数称数称为边的的重数重数.uuvuv504.简单图n(1)简单图n定义定义 设G=(V,E)是是图,若若G中既无吊中既无吊环又无多重又无多重边,则称称G是是简单图简单图.San FranciscoDenverLos AngelesNew YorkChicagoWashingtonDetroit51n(2)完全无向完全无向图n定定义 设G=(V,E)是是n阶简单无向无向图,若若G中任意中任意节点都与其余点都与其余n-1个个节点点邻接接,则称称G为n阶完全无向完全无向图图,记为Kn.K1K4K3K2K552n(3)补图n定定义 设G=(V,E)是是n阶简单无向无向图,由由G的所有的所有节点以及由能使点以及由能使G成成为Kn需要添加的需要添加的边构成的构成的图称称为G的的补图补图,记为n(u和和v在在G中不中不邻接接 u和和v在在 中中邻接接)53n作业作业 P162 习题习题6.1 953546.2 节点的度数节点的度数n边与与节点的点的关联次数关联次数n定定义 设G=(V,E)是无向是无向图,v V,称与称与节点点v关关联的所有的所有边的关的关联次数之和次数之和为节点点 v 的的度数度数,记为deg(v).n在任意在任意图中中,度数度数为0的的节点称点称为孤立点孤立点,度数度数为1的的节点称点称为悬挂点悬挂点.q一个一个环算算2度度deg(a)=2deg(b)=6deg(c)=4deg(d)=1deg(e)=0deg(f)=3deg(g)=4 a b g e c d f所有节点度数之和所有节点度数之和=2+4+3+4+6+1+0=20边数边数=10e为为孤立点孤立点.d为悬挂点为悬挂点.55n握手定理握手定理 在任何在任何(n,m)图G=(V,E)中中,其所有其所有节点点度数之和等于度数之和等于边数数m的的2倍倍,即即nCorollary 在任意在任意图G=(V,E)中中,度数度数为奇数的奇数的节点个数必点个数必为偶数偶数.nProof 偶数偶数偶数偶数偶数偶数5657n定定义 设G=(V,E)是有向是有向图,v V,n以以v为起点的起点的边的数目的数目为节点的点的出度出度,记为deg+(v),n以以v为终点的点的边的数目的数目为节点的点的入度入度,记为deg-(v),ndeg+(v)+deg-(v)为节点点v的的度数度数,记为deg(v).q一个一个环算算2度度a c b e d fdeg(a)=2deg(b)=2deg(c)=3deg(d)=2deg(e)=3deg(f)=0Total=12deg+(a)=4deg+(b)=1deg+(c)=2deg+(d)=2deg+(e)=3deg+(f)=0Total=12边数边数:12nTheorem 在任意有向图中在任意有向图中,所有节点的出度之和所有节点的出度之和等于入度之和等于入度之和.5859n定定义 若一个无向若一个无向图G的每的每节点度数均点度数均为k,则称称G为k-正则图正则图.n例例n例例 设无向无向图G是一个是一个3-正正则(n,m)图,且且 2n 3=m,求求 n 和和 m 各是多少各是多少?n解解 根据握手定理有根据握手定理有,3n=2m，n=6，m=9。60n定定义 对于无向于无向图G=(V,E),V=v1,v2,vn,称称deg(v1),deg(v2),deg(vn)为G的的度数序列度数序列.对于有向于有向图,还可以定可以定义其出度序列和入度序列其出度序列和入度序列.n例例 是否存在一个无向是否存在一个无向图G,其度数序列分其度数序列分别为q(1)7,5,4,2,2,1.q(2)4,4,3,3,2,2.n解解 q(1)由于序列由于序列7,5,4,2,2,1中中,奇数个数奇数个数为奇数奇数,根据握手根据握手定理的推定理的推论知知,不可能存在一个不可能存在一个图其度数序列其度数序列为7,5,4,2,2,1.q(2)因因为序列序列4,4,3,3,2,2中中,奇数个数奇数个数为偶数偶数,可以得到可以得到一个无向一个无向图,其度数序列其度数序列为4,4,3,3,2,2.n作业作业 P165 习题6.2 2,7616.3 子图、图的运算和图同构子图、图的运算和图同构1.子子图n可以通可以通过一个一个图的子的子图去考察原去考察原图的有关性的有关性质以以及原及原图的局部的局部结构构.n定定义 设G=(V,E)和和H=(W,F)是是图,若若W V且且F E,则称称H=(W,F)是是G=(V,E)的的子图子图;若若H=(W,F)是是G=(V,E)的子的子图且且W=V,则称称H=(W,F)是是G=(V,E)的的生成子图生成子图.62n例例 (一个一个图的子的子图较多多)n常常见的的4种种产生生G=(V,E)的子的子图的方式如下的方式如下:q(1)GW 设W V,则以以W为节点集合点集合,以两端点均属于以两端点均属于W的所有的所有边为边集合构成的子集合构成的子图,称称为由由W导出的子图导出的子图,记为GW.q(2)G W 设W V,导出子出子图GV W记为G W,是在是在G中去掉所有中去掉所有W中的中的节点点,同同时也要去掉与也要去掉与W中中节点关点关联的所有的所有边.通常将通常将G v记为G-v.63q(3)GF 设F E,则以以F为边集合集合,以以F中中边的所有端点的所有端点为节点集合构成的子点集合构成的子图,称称为由由F导出的子图导出的子图,记为GF.q(4)G F 设F E,则从从G中去掉中去掉F中的所有中的所有边得到的生得到的生成子成子图记为G F.642.图的运算的运算n定定义 q(1)并并q(2)交交q(3)差差q(4)环和和V1 V2E1 E2V1V2E1E2V1 V2E1E2653.图同构同构n由于由于图的拓扑性的拓扑性质,有可能两个表面上看起来不同有可能两个表面上看起来不同的的图本本质上是同一个上是同一个图,这就是就是图同构的同构的问题.n定定义：G1=(V1,E1)和和 G2=(V2,E2)，若存在双射若存在双射f：V1V2，使得使得G1 中有中有(a,b)当且当且仅当当G2中有中有(f(a),f(b)且重且重数相等数相等,则称称G1 和和 G2 同构同构.n直直观理解理解:G1 G2是指其中一个是指其中一个图仅经过下列两下列两种种变换可以可以变为另一个另一个图:q(a)挪挪动节点的位置；点的位置；q(b)伸伸缩边的的长短短.66n无向无向图同构的例子同构的例子:66n分子式分子式为C4H10的同分异构体：的同分异构体：n分子式分子式为C2H6O的同分异构体：的同分异构体：应用实例应用实例:判断化合物是否结构相同。判断化合物是否结构相同。6767两个图同构的必要条件：两个图同构的必要条件：节点个数相同节点个数相同 边的个数相同边的个数相同 对应节点的度数相同对应节点的度数相同 一个是完全图，另一个也是，等等一个是完全图，另一个也是，等等.破坏这些必要条件中的任何一个，两个图就不会同构。破坏这些必要条件中的任何一个，两个图就不会同构。6868aedcGHbaedcbG和和H是否同构是否同构?696970n有向有向图:对于两个有向于两个有向图同构的判断同构的判断,特特别要注意要注意边的方向的一致性的方向的一致性.n作作业 P168 习题6.3 1,5,6716.4 路与回路路与回路n1.路路n定定义 对于任意于任意图G=(V,E),n路的起点路的起点;终点点;路的路的长度度;n平凡路（一个平凡路（一个节点点长度度为0）.1u3452vu145v4323472n需要注意的是需要注意的是,有向图中的路须按边的方向走有向图中的路须按边的方向走,有有向向图中的路可称中的路可称为有向路有向路.73n定定义 两种特殊的路两种特殊的路:n一种是一种是节点不重复的路点不重复的路,称称为路径路径.n一种是一种是边不重复的路不重复的路,称称为轨迹轨迹.nv3e3v2e2v2是一条从是一条从v3到到v2的的轨迹迹,但不是路径但不是路径.n显然然,路径是路径是轨迹迹,但但轨迹不一定是路径迹不一定是路径.v3e3v2e2v2v1e5v3e3v2742.回路回路n定定义 起点与起点与终点相同的点相同的(长度度 1 1)路称路称为回路回路,n除起点重复一次外除起点重复一次外,别的的节点均不重复的回路称点均不重复的回路称为圈或圈或环,n边不重复的回路称不重复的回路称为简单回路回路.n长度度为0的路不称的路不称为回路回路.显然然,节点点v到到v的的边是一是一个个长度度为1的圈的圈.1u3452v23432u14u7475nTheorem 在在n阶图G=(V,E)中中,若存在从若存在从节点点v0到到vl的一条路的一条路,则必存在一条从必存在一条从v0到到vl的的长度度 n-1的的路径路径.nTheorem 在在n阶图G=(V,E)中中,若存在从若存在从节点点v0到到v0的的简单回路回路,则存在一条从存在一条从v0到到v0的的长度度 n 的的圈圈.n定定义qu到到v的的距离距离d(u,v):最短路径的最短路径的长度度证明证明 如果该路不是路径如果该路不是路径,说明含有回路说明含有回路,删去所有回路删去所有回路(包包括吊环括吊环)即可得到路径即可得到路径.1u3452vd(u,3)=？76n有有n个个节点的圈称点的圈称为n阶圈阶圈,记为Cn.n在在n-1阶圈圈Cn-1的内部放置一个的内部放置一个节点点,并使之与并使之与Cn-1的每个的每个节点点邻接接,这样得到的得到的图称称为n阶轮图,记为Wn.C3C4C5C6W4W5W7W677nTheorem 在无向在无向图G=(V,E)中中,若任意若任意v V有有deg(v)2,则G中必存在圈中必存在圈.n证 不妨不妨设G是是简单图.在在G中中选取一条最取一条最长的路径的路径L:v0v1vl,由于由于L是最是最长路径路径,与与v0邻接的所有接的所有节点必在点必在L上上.由于由于deg(v0)2,除了除了v1,存在存在vi(2 i l)与与v0邻接接,则v0v1viv0是是G中的一个圈中的一个圈.n作业作业 P170 习题6.4 1,4(1)(2).786.5 图的连通性图的连通性n定定义 在任何在任何图G=(V,E)中中,若从若从节点点u到到v存在一存在一条路条路,则称称u可达可达v.n备注注 由于由于节点点v到到v总存在一条存在一条长度度为0的路的路,因此因此任意任意节点点v可达可达v自身自身.791.无向无向图的的连通性通性n定定义 设 G=(V,E)是无向是无向图,对于于 G 中任意两个中任意两个节点点 u 和和 v 均可达均可达,则称称 G 是是连通图连通图.nTheorem 去掉去掉简单回路上的回路上的边或度或度为1的的节点点,图的的连通性不通性不变.a b c e a c e f W6d是是abcdef否否cabdegf是是80n定定义 设G=(V,E)是无向是无向图,G中极大的中极大的连通子通子图称称为G的的连通分支连通分支,图G的的连通分支数通分支数记为w(G).n备注注 图G的的连通分支通分支满足足3 个条件个条件:q(1)连通分支是通分支是G的子的子图；q(2)该子子图本身是本身是连通通图；q(3)在在该子子图中再添加原中再添加原图的任意的任意边或或节点都不点都不连通通.abdcefgh3 个连通分支个连通分支.81nTheorem 设G=(V,E)是无向是无向图,则G是是连通通图当且当且仅当当w(G)=1.qG是非是非连通通图当且当且仅当当w(G)2.82833.有向有向图的的连通性通性n有向有向图的的连通性分下述通性分下述3种情形分种情形分别讨论.n定定义 设G=(V,E)是有向是有向图,u,v V 均均相互相互可达可达,则称称G为强连通图强连通图.n定定义 设G=(V,E)是有向是有向图,对于任意于任意u,v V,从从u可达可达v或者或者从从v可达可达u,则称称G为单向连通图单向连通图.n定定义 设G=(V,E)是有向是有向图,若不考若不考虑边的方向是一个无向的方向是一个无向连通通图,则称有向称有向图G为弱连通图弱连通图,简称有向称有向图G连通通.84n强连通通图 单向向连通通图 弱弱连通通图.n但反但反过来均不成立来均不成立!n特特别地，平凡地，平凡图是是强连通通图。85nTheorem 设G=(V,E)是有向是有向图,则G强连通当且通当且仅当当G中存在一条回路中存在一条回路,它通它通过所有所有节点点.nTheorem 设G=(V,E)是有向是有向图,则G单向向连通当通当且且仅当当G中存在一条路中存在一条路,它通它通过所有所有节点点.n作业作业 P175 习题6.5 3.866.6 图的矩阵表示图的矩阵表示n将一个将一个图画出来是最直画出来是最直观的表示的表示图的方式的方式.n学学习图的矩的矩阵表示的必要性：表示的必要性：便于使用便于使用计算机存算机存储和和处理理图,借助于完善的矩借助于完善的矩阵理理论(线性代数知识之一线性代数知识之一!)研究研究图的有关性的有关性质。87 图的的邻接矩接矩阵n邻接矩接矩阵：表示的是：表示的是图中任意两个中任意两个节点点间的的邻接接关系关系.n定定义 G=(V,E),对节点点编号号V=v1,v2,vn.其中其中aij是是vi邻接到接到vj的的边数数,i,j=1,2,n.a b c d e f abcdefFromToW6dbacefv1,v2行行 列列0 1 0 0 1 11 0 1 0 0 10 1 0 1 0 10 0 1 0 1 11 0 0 1 0 11 1 1 1 1 0880 1 1 0 1 0 1 0 0 0 1 1 0 0 1 0v1v4v3v2v1v4v3v20 2 0 1 2 0 2 1 0 2 0 1 1 1 1 1A=A=8990n备注注q无向无向图的的邻接矩接矩阵是是对称矩称矩阵.q一个一个图与其与其邻接矩接矩阵是一一是一一对应的的.q从一个从一个图G的的邻接矩接矩阵A(G)容易得出每个容易得出每个节点的度数点的度数.G为无向图：为无向图：G为有向图：为有向图：v1v2v3v4A2=1 2 3 10 0 0 10 0 1 00 0 0 1A3=1 2 4 30 0 1 00 0 0 10 0 1 0(1)v1v1v1v2v3 (2)v1v1v1v2v3(3)v1v2v3v4v3 (4)v1v2v3v4v3(5)v1v1v3v4v3 (6)v1v1v1v1v3 A4=1 2 6 40 0 1 00 0 0 10 0 1 0A=1 2 1 00 0 1 00 0 0 10 0 1 0从从 v1 到到 v3 长度为长度为4的路有多少条的路有多少条?例例919192n从从图的的邻接矩接矩阵可以得出从可以得出从节点点vi到到vj长度度为l(l 1)的路的数目的路的数目.nTheorem 设A是是图G的的邻接矩接矩阵,则Al中中(i,j)位置位置元素元素为从从节点点vi到到vj长度度为l(l 1)的路的数目的路的数目.n证 对 l 归纳.l=1,显然然.nAl=Al-1A:9293n例例 如如图q(1)v2到到v5的的长度度为1,2,3,4的路各有多少条的路各有多少条?q(2)G 中中长度度为3的路有多少条的路有多少条,其中有多少回路其中有多少回路?q(3)G 是哪是哪类连通通图?路：路：20强连通图强连通图94n作业作业 P179 习题6.6 2,694