第一章图的基本概念节精选PPT.ppt

《第一章图的基本概念节精选PPT.ppt》由会员分享，可在线阅读，更多相关《第一章图的基本概念节精选PPT.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章图的基本概念节第1页，本讲稿共45页14 图的矩阵表示法定义：对于图G=(V,E)，构造一个矩阵 其中n|V|；1 (vi,vj)E；称A是图G的邻接矩阵邻接矩阵。0 否则；nnijaA=)(=ija第2页，本讲稿共45页2置换矩阵：相当于将单位矩阵中相应的行与行，或者列与列互换的矩阵。1 0 00 0 10 1 0P a11 a12 a13a21 a22 a23 a31 a32 a33 A a11 a12 a13a31 a32 a33a21 a22 a23PA a11 a13 a12a31 a33 a32a21 a23 a22(PA)P P就是一个置换矩阵第3页，本讲稿共45页3邻接矩

2、阵中图的性质：v1v2v3v40 1 1 01 0 1 11 1 0 00 1 0 0A 无向图的邻接矩阵是对称的！(1)A=(ij)nn中，第i行或第i列中非0元素的个数等于顶点vi的度。(无向图无向图)第4页，本讲稿共45页4v4v1v2v30 1 1 00 0 0 10 1 0 11 0 1 0A 竖入横出(2)A=(ij)nn中，第i列列中非0元素的个数等于顶点vi的入入度，第i行行中非0元素的个数等于顶点vi的出出度。(有向图)第5页，本讲稿共45页5(3)B=A2。a11 a12 a1na21 a22 a2n an1 an2 ann B=A2=a11 a12 a1na21 a22

3、a2n an1 an2 ann(bij)nnbij表示vi两步到达vj的路径数目第6页，本讲稿共45页6(4)有向图中：C=AAT。a11 a12 a1na21 a22 a2n an1 an2 ann C=(cij)=a11 a21 an1a12 a22 an2 a1n a2n ann cij表示以vi,vj为始始点的终终点数目。cij=ik jkvivjvk第7页，本讲稿共45页7(5)有向图中：D=ATA。a11 a12 a1na21 a22 a2n an1 an2 ann D=(cij)=a11 a21 an1a12 a22 an2 a1n a2n ann dij表示以vi,vj为终终点

4、的始始点数目。dij=ki kjvivjvk第8页，本讲稿共45页8图的同构定义：若两个图顶点数相同且相对应，对应顶点之间的边也相对应，则称两个图同构同构同构同构。G1(V1,E1)，G2(V2,E2)，G1G2若u1,v1V1，u2,v2V2，u1 u2，v1 v2，则(u1,v1)E1(u2,v2)E2。v1v2v3v4vavbvcvd第9页，本讲稿共45页9v1v2v3v4图G1vavbvcvd图G20 1 1 11 0 1 11 1 0 11 1 1 0A11 2 3 40 1 1 11 0 1 11 1 0 11 1 1 0A2a b c dv1vav2vbv3vcv4vd第10页，

5、本讲稿共45页10判别定理：图G1，G2同构的充要条件充要条件是：存在置换矩阵P，使得：A1PA2P。其中A1，A2分别是G1，G2的邻接矩阵。如何判断两图同构是图论中一个困难问题，下面我们来探讨一些判断同构的一些策略。第11页，本讲稿共45页11根据同构的定义可知，如果两个图G和H是同构的，则从G的顶点集到H的顶点集必须存在一个一一对应，这意味着G的顶点和H的顶点必能够完全匹配，所以G和H有相同的阶，因此讨论两个图是否相同，我们先考虑他们的阶是否相同。同理，根据定义，边也存在一一对应，因此，若两个图同构，则必有相同的边数。因此，若两个图的阶或边数不同，则它们一定不同构。第12页，本讲稿共45

6、页12定理：图G和H是同构图，则它们对应的顶点有相同的度。另一方面，即使两个图具有相同的阶和相同的变数，也不能确保它们同构。从以上定理可知，若两图同构，则它们具有相同的度序列。实际上，即便具有相同的度序列，也只是两个图同构的必要条件，而非充分条件。第13页，本讲稿共45页13举例：判断下面两图是否同构。1245e1e2e3e4e5e6e7图136abcdek1k2k3k4k5k6k7图2f以上2个图的度序列均为（4,3,3,2,1,1），事实上它们并不同构。为什么？第14页，本讲稿共45页14课堂练习1、判断下面两图是否同构，若同构写出对应关系，若不同构则写出理由。12345e1e2e3e4e

7、5e6e7图1abcdek1k2k3k4k5k6k7图2第15页，本讲稿共45页15课堂练习答案课堂练习答案解：同构。对应关系顶点对应：1a；2b；3e；4d；5c；边对应：e1k1；e2k2；e3k3；e4k4；E5k5；e6k6；e7k7；第16页，本讲稿共45页165 5 中国邮路问题中国邮路问题第17页，本讲稿共45页175 中国邮路问题 中国邮路问题中国邮路问题(Chinese postman problem)，是我国数学家管梅谷于1960年首次提出的。问题描述：设邮递员从邮局出发，遍历他所管辖的每一条街道，将信件送到后返回邮局，求所走的路径最短。第18页，本讲稿共45页18中国邮路

8、问题的图论模型为：设G=(V,E)是连通图，而且对于所有的eE都赋以权权c(e)0，求从点v0V出发，通过所有边至少一次最后返回v0的回路C，使得 达到最小。邮局v1v2v3v4v5v634521426351v0第19页，本讲稿共45页19问题分析：（1）如果道路正好是一个Euler图，则容易求解，用Fleury算法求出一个Euler回路即可；（2）如果不是Euler图，则加上如干重复边，使之变成Euler图，然后求Euler回路。现在问题的关键关键：如何加重复边！中国邮路问题是Euler回路的近似求解。第20页，本讲稿共45页20定理：设E*E是使W(E*)=达到最小 的重复边集合，当且仅当

9、对于Ga图的任一回任一回 路路 ，恒有W(E*)W(E()-E*)E*是重复边集合Ga是加重复边以后的Euler图E*=(v2,v3)E(C)=(v1,v2),(v1,v3)(v2,v3)(v2,v4)(v3,v4)v1v3v23234v42第21页，本讲稿共45页21中国邮路证明中国邮路证明证明：证明：必要性必要性必要性必要性。如若不然，假定存在一回路C使得 W(E(C)E*)W(E(C)E*)。这意味着E(C)E*部分的权超过其余部分的权，即E(C)E*部分的权。令 =E（C）E*，即 =(E(C)E*)(E(C)E*)=(E(C)E*)(E*E(C)由于假定W(E(C)E*)W(E(C)

10、E*)，故 W(E*)W()这与E*的假设相矛盾.必要性得到了证明.充分性证明。充分性证明。充分性证明。充分性证明。假定存在两个边集E(1)和E(2)作为重复的边，都满足定理的条件，现在只需证明W(E(1)=W(E(2)令 F*=E(1)E(2)，则图G*=（V，F*）没有度数为奇数的顶点。则F*=E(1)E(2)=C1 C2 Ch,则有W(E(Ci)E(1)W(E(Ci)E(1)，i=1，2，h但 E(Ci)E(1)=E(Ci)E(2)，故，W(E(Ci)E(1)W(E(Ci)E(2)同理，W(E(Ci)E(2)W(E(Ci)E(1)即：W(E(Ci)E(1)=W(E(Ci)E(2)所以，W

11、(E(1)=W(E(2)。充分性得证。第22页，本讲稿共45页22中国邮路构造算法设已经知道度为奇数的顶点为v1,v2,v2h第一步第一步：添加重复边添加重复边：i从1到h，引从v2i-1到v2i的链Pi，并对Pi的每条边附加1条重复边；第二步第二步：检查重复边检查重复边：检查图G的每条边，使得每条边最多有1条重复边，得到图G，G中重复边集记为E(0)；第23页，本讲稿共45页23第三步第三步：设初值k0；(a)若E(k)对于回路 有 ，则E(k1)=E(k)E()，kk1，转(a)；(b)输出E(k)，E(k)便是最优集。n 第四步第四步：用Fleury算法求出Eluer回路。第24页，本讲

12、稿共45页24中国邮路问题举例中国邮路问题举例 求出下图中以v1为起点的一条中国邮路。v1v2v3v4v6v5v751322325433第25页，本讲稿共45页25解：其中v2，v3，v4，v5，v6，v7顶点的度都是奇数，引入重复边。第一步第一步：添加重复边添加重复边：i从1到h，引从v2i-1到v2i的链Pi，并对Pi的每条边附加1条重复边；v1v2v3v4v6v5v751322325433E(0)=(v2,v3),(v4,v5),(v6,v7)第二步第二步：检查重复边检查重复边：检查图G的每条边，使得每条边最多有1条重复边，得到图G，G中重复边集记为E(0)；第26页，本讲稿共45页26

13、下面看回路 ：v2-v3-v7-v2 其中E()=(v2,v3),(v2,v7),(v3,v7)E(0)=(v2,v3),(v4,v5),(v6,v7)5 224 E(1)E(0)E()(v2,v7),(v3,v7),(v4,v5),(v6,v7)v1v2v3v4v6v5v751322325433第27页，本讲稿共45页27v1v2v3v4v6v5v751322325433E(1)=(v2,v7),(v3,v7),(v4,v5),(v6,v7)下面看回路 ：v4-v5-v6-v7-v4 其中E()=(v4,v7),(v4,v5),(v5,v6),(v6,v7)437 235 E(2)E(1)E

14、()(v2,v7),(v3,v7),(v4,v7),(v5,v6)第28页，本讲稿共45页28v1v2v3v4v6v5v751322325433E(2)=(v2,v7),(v3,v7),(v4,v7),(v5,v6)下面看回路 ：v3-v4-v7-v3 其中E()=(v3,v4),(v4,v7),(v3,v7)E(3)E(2)E()(v2,v7),(v3,v4),(v5,v6)224 3第29页，本讲稿共45页29最后利用Fleury算法求出一个Euler回路：v1-v2-v3-v4-v3-v7-v2-v7-v4-v5-v7-v6-v5-v6-v1代价一共是：41v1v2v3v4v6v5v75

15、1322325433E(3)=(v2,v7),(v3,v4),(v5,v6)第30页，本讲稿共45页30课后练习课后练习求下图中一条中国邮路：v1v2v3v4v5v6v11v10v9v8v7v129 95 53 34 44 48 87 75 56 64 46 64 42 24 45 53 36 6第31页，本讲稿共45页316 6 平面图平面图第32页，本讲稿共45页326 平面图平面图1、若图可以画在一个曲面上，任意两边都不相交（端点除外），称图G被嵌入在曲面上被嵌入在曲面上。2、如果曲面是平面称G是可平面图可平面图。3、如果图已经画在平面上，称图G为平面图平面图。图a图b图c可平面可平面图

16、图平面图平面图非平面图非平面图第33页，本讲稿共45页334、若有一个简单的平面图，再加一条边就是不可平面，则称之为最大平面图。最大平面图。再加一条边就不再加一条边就不是平面图了。是平面图了。第34页，本讲稿共45页345、平面图的边把图G所在的平面划分为若干个区域，每个区域称为图G的面面；6、包围每个面的回路称为面的边界边界；7、回路的边数称为面的次数次数。容易发现，平面图G每增加1条边，图G总的边数和面数都增加1。边界面第35页，本讲稿共45页358、欧拉公式定理（必要条件必要条件）：如果平面连通图G有n个顶点，m条边，d个区域，则 n nm md d2 2。证明：设图G是有n个顶点一棵树

17、，则mn1，d1，这时nmd2成立。G每增加1条边，即m增加1，这时d也增加1。所以(顶点数)(边数)(域数)2 不变。证毕。第36页，本讲稿共45页369、定理：若图G是简单的平面图，则图G至少有一个顶点的度小于小于6。证明：见教材p30第37页，本讲稿共45页3710、定理：最大平面图的顶点数n，边数m，域数d满足下列等式：m3n6，d2n4证明：见教材P30。11、对于一般平面图d1时（即不包含树）：m3n6，d 2n4结论结论：3个顶点和4个顶点的图一定一定是可平面图，5个顶点的图则不一定不一定是可平面图。第38页，本讲稿共45页3812、Kuratowski图K(2)图K(2)图又称

18、二部图二部图二部图是什么？如果图的顶点集可以分为两个互不相交的子集，子集内结点互不邻接，则此图称为二部图二部图。K(1)图第39页，本讲稿共45页3913、定理：K(1)，K(2)不是平面图。证明见教材P31。14、在K(1)，K(2)的边加上若干顶点所形成的图也不是平面图。与这些图同型的图分别叫K(1)型图和K(2)型图,统称K型图。第40页，本讲稿共45页4015、Kuratowski（库拉图斯基）定理：图G是平面图的充要条件充要条件是：G图不存在任何子图为K(1)图或K(2)图。证明较繁，在此不多述。根据Kuratowski定理，可以断定：所有树树都是平面图。第41页，本讲稿共45页41

19、16、设平面图G有n个顶点，m条边，d个面，分别为S1，S2，Sd，在每个Si面放置一个顶点v*i，如果Si和Sj面相邻，则用(v*i,v*j)连接(v*i点和v*j点，使(v*i,v*j)与面Si和Sj的公共边只相交一次，且G的其它边界无交点。这样得到的图G*称为G的对偶图对偶图。v1*v2*v3*v4*bacdefgh第42页，本讲稿共45页42思考题1.若连通平面图G1与G2同构，它们的对偶图G1*与G2*是否同构？2.若连通平面图G中有n个顶点，m条边，d个面，则其对偶图G*中的顶点数，边数，面数分别是什么？第43页，本讲稿共45页43课堂练习分别画出下图的对偶图。第44页，本讲稿共45页44第一章内容回顾图论的发展图论几个著名的问题图的基本概念两个回路问题图的矩阵表示法中国邮路问题平面图第45页，本讲稿共45页45