离散数学图论习题课PPT学习教案

1、会计学1离散数学图论习题课离散数学图论习题课第1页/共48页 图图 通路与回路通路与回路 图的连通性图的连通性 欧拉图欧拉图 汉密尔顿图汉密尔顿图 无向树及其性质无向树及其性质 平面图的基本性质平面图的基本性质 欧拉公式欧拉公式 平面图的对偶图平面图的对偶图 地图着色与平地图着色与平面图着色面图着色 平面图的判断平面图的判断 图的矩阵表示图的矩阵表示 无向树及其性质无向树及其性质 根树及其应用根树及其应用 无向树及其性质无向树及其性质图论的结构图第2页/共48页第3页/共48页n(1) 灵活运用握手定理及其推论，n(2) 判断两个图是否同构，n(3) 画出满足某些条件的子图，补图等。第4页/共

2、48页n路)的类型。n(2) 求短程线和距离。n(3) 判断有向图连通的类型。第5页/共48页第6页/共48页无向图：无向图：有向图：有向图：且且第7页/共48页( , ),( , ),( , ),( , )Ea bb cc da e(1)( , ),( , ),( , ),( , ),( , )Ea bb ee ba ed e(2)( , ),( , ),( , ),( , )Ea bb ee dc c(3)多重图不是简单图第8页/共48页第9页/共48页为割边（或桥）n如果答案A正确，即删除边(a, d)后，得到的图是不连通图，但事实上它还是连通的。因此答案A是错误的。第10页/共48页f

3、，cf图是不连通的。第11页/共48页单向连通单向连通强连通强连通强连通强连通强连通强连通单向连通单向连通弱连通弱连通第12页/共48页8个1，故有82=4条边。度数之和等于2倍的边数。第13页/共48页第14页/共48页 1222234412222465012112220121222310010121100102210100100101000021432AAAA第15页/共48页n答：长度4的通路88条，其中22条为回路。n(6) 写出D的可达矩阵。n44的全1矩阵。第16页/共48页，从而此 k-1个结点中至少有两个同度数点。第17页/共48页 deg(vi) = 2m=20n解此不等式可

4、得n7，即G中至少有7个结点，7个结点时，其度数列为2,2,2,3,3,4,4，=4,=2。第18页/共48页n(2) n阶非连通的简单图的边数最多可为n-1阶连通图加上一个孤立点，所以边数为(n-1)(n-2)/2，最少为0。第19页/共48页n2)由 1)可知，自补图对应的完全图的边数为偶数。n 个结点的完全图Kn的边数为n(n-1)/2 ，所以n(n-1)/2=2m ，即n(n-1)=4m，因而nn为4的倍数，即n=4k，n或n-1为4的倍数，即n=4k+1，n即n=0,1 (mod 4)。第20页/共48页结点，不妨假设其中的三个结点为b，c，d，如图所示。若边(b，c)，(c，d)，

5、(b，d)中有一条在G中，那么这条边所关联的两个结点都与a邻接形成一个三角形；若边(b，c)，(c，d)，(b, d)都不在G中，则(b，c)，(c，d)，(b, d)形成一个三角形。第21页/共48页abcdbcdbcdbcd推论推论:任何任何6人的人群中，或者有人的人群中，或者有3人互相认识，或者有人互相认识，或者有3人彼此陌生。人彼此陌生。(当二人当二人x,y互相认识，边互相认识，边(x,y)着红色，着红色，否则着兰色。则否则着兰色。则6人认识情况对应于人认识情况对应于K6边有红边有红K3或者或者有兰有兰K3。)aaa第22页/共48页第23页/共48页补图的奇数结点个数也是相同的。第2

6、4页/共48页奇数，故这条回路的长度是奇数。第25页/共48页uG1vG2G1G2是G的连通分支，由于G中恰有两个奇度结点，因而当作为独立的图时，均有一个奇度结点，这与握手定理的推论相矛盾。第26页/共48页，和v在G中是连通的。nb)u和v属于同个结点子集Vi。可在另一个结点子集Vj中取一个结点w，由上可知边(u,w)及边(v,w)均在G 中，故邻接边(u,w)和(w,v)组成的路连接结点u和v，即u和v在G中也是连通的。n由此可知，当图G不是连通图时，G必是连通图。第27页/共48页ndeg ( vi ) + deg ( vj ) ( k - 1) + ( n - k) - 1 = n -

7、 2与题设矛盾，故图G是连通图。第28页/共48页盾；故图 G 是连通图。第29页/共48页第30页/共48页这10种状态。 若一种状态可以转移到另一种状态， 就在表示它们的两结点间连一条边， 这样就画出图。 本题就转化为找结点FWSH到结点的通路。 从图中得到两条这样的通路， 即有两种渡河方案。FWSH WHFWHHWFSHFSWSFS第31页/共48页第32页/共48页(1)(2)说明：欧拉图中，结点数和边数的奇偶说明：欧拉图中，结点数和边数的奇偶性既可以相同也可以相反。性既可以相同也可以相反。第33页/共48页n(3)当n=偶数时， Kn中每个结点度数=n-1为奇数，对应的有n/2对奇数

8、度结点，因此可以n/2笔画出。第34页/共48页AB第35页/共48页则问题归结为求此图的一条汉密尔顿回路。不难验证，此图有一条汉密尔顿回路是:(A,B,D,F,G,E,C,A)。按此回路安排席位可以使得每个人都可以和它两边的人直接交谈。BCDEFGA英英英英法法德德俄俄意意日日汉汉第36页/共48页数减1。n故此图中存在一条汉密尔顿路，因此游人可以经过每个风景点恰好一次而游完这5处。第37页/共48页n与题设矛盾。n所以，图G 为汉密尔顿图。第38页/共48页nG 不妨设C=vi1vi2vi3vi4vi5vi6vi1为其中一条，在这种回路上相邻两个结点代表的二人能相互合作。第39页/共48页v1v2v3v4v5v6v1为其中一条，在这种回路上每个结点代表的颜色都能与它相邻结点代表的颜色相搭配，于是让v1与v2,v3与v4,v5 与v6