《离散数学 教学课件 ppt 作者 杨圣洪 张英杰 陈义明ch5图论》由会员分享，可在线阅读，更多相关《离散数学 教学课件 ppt 作者 杨圣洪 张英杰 陈义明ch5图论（72页珍藏版）》请在金锄头文库上搜索。
1、第五章 图论,杨圣洪,5.1图的概念与描述,由结点和连结两个结点的连线所组成的对象称为“图”。 至于结点的位置及连线的长度无紧要,形式定义：三元组(V(G),E(G),M(E,V)称为图。其中V(G)为点的集合(非空集)，E(G)是边集，M(E,V)=边与点连接关系。 常简化为二元组 (V(G),E(G)称为图。简记为G=(V,E)。,5.1图的概念与描述-邻接矩阵,对于有向图，如果从结点vi到结点vj之间有一条边，则a(i,j)=1，否则为0。 由于结点vi到vj有一条边，反过来vj到vi之间不一定有一条，故不一定对称。 对于无向图，如果结点vi到Vj有一条边，则a(i,j)=1，否则为0。
2、 由于Vi到Vj有一条边时，反过来Vj到Vi肯定也有一条边。故它是对称的。,可表示自环，不能表示重边,5.1图的概念与描述关联矩阵,关联矩阵表示结点与边之间的关联关系。 对于有向图： 如果Vi是ej的起点，则b(i,j)=1。 如果Vi是ej的终点，则b(i,j)=-1。 如果以上两种情况不存在，则b(i,j)=0。 对于无向图： 如果Vi到ej某个端点，则b(i,j)=1。 否则 b(i,j)=0。 该矩阵的行对应为“点”，列对应“边”， nm.,ej,Vi,ej,Vi,ej,Vi,ej,Vi,重边可表示，自环不可能表示,A,B,C,D,e1,e2,e3,e4,e5,e6,e7,a,b,c,
3、d,e1,e2,e3,e4,e5,e6,V=a, b, c, d E=e1,e2,e3,e4,e5,e6 |V|称为结点数，记为n 该值有限，有限图 |E|称为边数，记为m.该值有限。,有限图 无限图,如果每条边都有方向的，则为有向图。 如果每条边都没有方向，则为无向图。 某些边有方向，某些边没有方向，混合图,有向图 无向图,邻接,有向边e1=，A与D相邻,e1与A、D相关联。称A为D的直接前趋，D为A的后继。 点与点相邻,点与边关联 无向边e1=(a, b), a与b相邻，e1与a、b相关联。 只与一个结点关联的自环/自旋。某两个点之间有多条边为重边(多重图)。无环无重边简单图,度,某结点关
4、联边的条数，称为该点的度数： D(A)=5,d入(A) =1,d出(A) =4, 有向图 d入(A) +d出(A) =d(A)=5 “入”进入某结点的边，也称为“负边”，负度 “出”离开某结点的边，也称为“正边”，正度,各点度数和=边数的2倍,deg(v)=2|E|=2m (为偶数) 证明： 先去掉所有的边，每个点、整个图的度数为0 增加一条边e=(u,v)，使结点u与v的度数的各增加1 。 每增加一条边使整个图的度数增加2。 deg(v)=2|E| =2m(为偶数) 握手定理,左图=3+2+3+2=10,边数=5， 度数和10=边数的2倍(2*5) 右图=3+3+3+3=12 ，边数=6 度
5、数和12=边数2倍(2*6),图中度数为奇的结点有偶数个,用Vo表示度数为奇(odd)的结点集合，Ve为偶(even)的结点的集合,则有： edeg(v)+ odeg(v)= deg(v)=2m。 因Ve中每点度数均为偶数 edeg(v)为偶数，不妨记为2k odeg(v)=2m-2k=2(m-k) ，由于Vo中每个结点的度数为奇数，不妨依次记为2n1-1,2n2-1,2nt-1，t为个数 其和为 2(n1+n2+nt)-1-1-1=2n-t 2n-t=2(m-k) 个数 t=2(m-k)-2n=2(m-k-n),左图度数为奇的点有:A(5) B(3)共2个 右图度数为奇的点有:B(3),D(
6、3)共2个,有向图中出度(正度)和 =入度(负度)和,在有向图中，每条边都有起点、与终点。 每加一条边使起点的出度增加1，整图的出度增加1， 每加一条边使终点的入度增加1，整图的入度增加1 每边使整图的出度、入度各增加1 所有的边加起来，增加的出度和=入度和。,正度(出度)=4+1+1+2=8 负度(入度)=1+2+3+2=8 正度和=负度和,n个结点完全图Kn的边数=n(n-1)/2,Kn:n个结点的完全图 该图的任何两个结点之间都有边相连 每个点都与其它n-1个点之间有边相连 每个点度数为(n-1)，n个点的度数和n(n-1), 而整图的度数和为n(n-1)=边数2倍=2m n(n-1)=
7、2m，故边数m=n(n-1)/2 由组合学可知m=C(n,2) 证明了c(n,2)=n(n-1)/2 说明：简单图中点的度(n-1)，边数n(n-1)/2,边数= n(n-1)/2,非空简单图一定存在度相同的结点,证明:图G的结点数记为n。 由于它是简单图,无重复边与自环, 每点的度数取值范围是0n-1. 当没有度数为0的结点时,每点度数的取值范围是1n-1，根据鸽巢原则，这n个点中至少有2个点的度数相同。 当有度数为0的结点时,剔除所有度数为0的结点,对剩下来的结点所组成的图使用前面的证明.,3、2、2、3 3、3、3、3,例题某班有23人，班长说每个人恰好只与其他7个人关系密切，请问班长的
8、话可信吗？ 解：将以上问题用图表示，23个人则23个点表示，i号同学对应结点i，如果某两位同学关系密切，则对应的结点间用一条边相连。 “说每个人恰好只与其他7个人”，说明与每位同学相连的边数为7，即其度数为7，23位同学的度数和=23*7=161，由握手定理有161=2m， 一个奇数不可能等于一个偶数，显然矛盾，故班长的话不可信。 用图论来解决问题，关键是将问题中的对象表示为结点或边。.,5.2 图的连通性,定义 一个有向图中，从任意结点出发，若沿着边的箭头所指方向，连续不断向前走，能到达所有的结点，则此图连通。,否,是,5.2 图的连通性,定义一个无向图中，从任意结点出发，沿着边连续不断向前
9、走，能到达所有的结点，则此图是连通的,是,5.2 图的连通性,看图判断连通性，仅对结点数比较少的图可行，结点数较多时需要寻求更高效的方法。 前面求传递闭包时，如果某两个结点之间通过传递可达，则在这两点之间加上一条边(称为复合边)。 因此求完传递闭包后，如果某二个点之间有边相连，则表明这二个结点： 要么未求闭包之前是直接相连的， 要么这两个点之前不是直接连接,是通过传递可达。 图与其邻接矩阵，相当于关系图与其关系矩阵， 因此求传递闭包的方法可用来判断图的连通性， 即WarShall算法、邻接矩阵的逻辑幂次方运算。,例题 判断下图是是否连通,a(1,3)=0从结点1不能走到结点3，看图可知,其他0
10、类似 a(1,5)=1从结点1出发可达结点5，看图可知,其他1类似,例题 若求跨越1条边、2条边、n-1条边的路，究竟有多少条，则直接计算邻接矩阵的幂次方A、A2、A3、An-1。,5.3Euler问题,七桥问题：每桥仅走一次，回到家里,定义5.3.1 如果从某点出发，沿着边不断前行又回到起点，那么称沿途经过的边构成一个回路. 如下图中，a-b-d是一个回路，a-b-a是一个回路，a-b-d-c-a也是回路。 定义5.3.2 如果从某点出发，沿着边不断前行能走遍所有的边，但不回到起点则称为欧拉路。 定义5.3.3如果从某点出发，沿着边不断前行能走遍所有的边，并且回到起点则称为欧拉回路。存在欧拉
11、回路的图也称为欧拉图。,定理5.3.1 无向图G有欧拉回路所有结点度数为偶数. 定理5.3.2无向图G有欧拉路所有结点度数为偶数，或者只有2个结点度数为奇数。 左图中度数为：deg(a)=5、deg(b)=3、deg(c)=3、deg(d)=3，故没有欧拉回路，故七桥问题无解。 中图：deg(a)=deg(d)=3，有欧拉路没无回路 右图：deg(1)=2 deg(2)=4 deg(3)=4 deg (4)=2 deg(5)=2 故有欧拉回路，为欧拉图。,判断下面图能否可以一笔画出,5.4 哈密尔顿图,1859年，英国数学家哈密顿：用一个规则的实心十二面体，标出世界著名的20个城市,5.4 哈
12、密尔顿图 this,定义5.4.1 如果图中存在一条，经过所有结点一次也仅一次的路，则称为哈密尔顿路。 如果回到起点称为哈密尔顿回路。 存在哈密尔顿回路的图称为哈密尔顿图。 定义5.4.2 如果图中没有一个结点上有自旋，任意二个结点间最多一条边，则称为简单图。 定理5.4.1 设G是具有n结点的简单图，如果G中每一对结点度数和n-1，则G中存在一条哈密尔顿路。即存在一条经过所有点一次的路。 定理5.4.2 设G是具有n结点的简单图，如果G中每一对结点度数和n，则G中存在一条哈密尔顿回路。即存在一条经过所有点一次的回路。 充分而不必要！,5.4 哈密尔顿图,左n=5，任意2点和4有H路。 右n=
13、6，任意2点和5有H路 下图n=6，任意2点和=45，不满足条件但有回路。 充分条件(满足肯定是)，不必要(是不一定满足),5.4 哈密尔顿图,定理5.4.3 若图G=具有哈密尔顿回路，则对于结点集V的每个非空子集S，均有W(G-S)|S|。 当取S=1,5时上图变成了下图被分成了3块，即W(G-S)=3，而|S|=2，故不满足W(G-S)|S|，故不是H图。,5.4 哈密尔顿图,去掉1个结点后W(G-S)=1|S|。 去掉2个结点后W(G-S)=1|S|。 去掉3个结点后W(G-S)=1|S|。 去掉4个结点后W(G-S)=1|S|。 去掉5个结点后即W(G-S)=1|S|。 去掉6个结点后
14、W(G-S)4|S|。 均满足但不是H图，可用AB标记法检测.必要不充分,5.4 哈密尔顿图,如果有多条哈密尔顿回路，距离都已标在每条边上，哪条路最短呢？称为“旅行商问题TSP(Traveling Salesman Problem)”或货郎担问题。 如：1-2-3-4-5-1，路长为4+16+11+13+10=54 但是1-2-4-3-5-1，路长为4+3+11+4+10=31， 只能一一试探，其计算量相当大，是一个不可能在多项时间内解决的问题，称为NP(Non Polynomial)难问题,5.5 平面图与染色问题,定义5.5.1 如果一个简单图中任意两条边不在中间相交，仅在两个端点相交。
15、或将某些边拉长或缩短后，也可做到不在中间相交，也称为平面图，或可平面化的图，一律称为“平面图”。,5.5 平面图与染色问题,定义5.5.2 平面图中由边围成的封闭区域称为为面或域。 如下图中，有1-3-4-1围成的面1，1-2-4-1围成的面2，2-4-3-2围成的面3，还有1-3-2-1之外的广阔的外围空间也是一个面，所以该图共有4面。 定理5.5.1 平面图中面数=边数-点数+2。 如下图中，面数d=4、边数m=6、点数n=4， 显然有d=m-n+2。,5.5 平面图与染色问题,定义5.5.3 在点数大于3的平面图中，如果在不相邻的两个点之间添上一条边，新添边肯定与其他边相交，即变成非平面
16、图，则该图为极大可平面图。 如果所有点相邻(这种图称为完全图)，不可能再加边了，肯定为极大可平面图，如下图每个面的边数为3。 定理5.5.2 极大平面图中，3d=2m，m=3n-6，d=2n-4。,5.5 平面图与染色问题,证明：极大平面图中任何面的边只有3条(若超过3条如达4条则至少为四边形，还可添加边这与极大平图矛盾). 每条边均是面的边界线,是两个面的边界，故数各个面的边界数时,每边被数了2次，所有面的边界数和=2m。 极大平面图中每个面只有3条边，d个面共有3d条边，所以3d=2m。 将d=m-n+2代入有，3(m-n+2)=2m，故m=3n-6。 将m=3d/2代入d=m-n+2中，d=3d/2-n+2，故d=2n-4,5.5 平面图与染色问题,定理5.5.3 平面图中m3n-6，d2n-4 m=C(5,2)=10,点数n=5,3n-6=9,违反了m
