《图的基本概念及其矩阵表》由会员分享，可在线阅读，更多相关《图的基本概念及其矩阵表（128页珍藏版）》请在金锄头文库上搜索。
1、离散数学 大连理工大学软件学院 陈志奎,2/128,第9章 图的基本概念及其矩阵表示论,3/128,图论（Graph Theory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来，如下图所示，A、B、C，D表示陆地。,4/128,图论的起源,哥尼斯堡七桥问题 ：17世纪的东普鲁士有一座哥尼斯堡（Konigsberg）城，城中有一条普雷格尔（Prege
2、l）河，全城共有七座桥将河中的岛及岛与河岸联结起来，如下图所示，a,b,c,d表示陆地。,从四块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？,5/128,图论的起源,1736年瑞士大数学家列昂哈德欧拉（Leonhard Euler）解决了这一问题，他用了科学研究中最一般的方法抽象。用四个字母a,b,c,d表示四块陆地，并用7条线表示7座桥，从而将七桥问题抽象为图的问题，寻找经过图中每边一次且仅一次的回路，后来人们把有这样回路的图称为欧拉图。,6/128,图论的起源,欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使欧
3、拉成为图论的创始人。 欧拉被称为图论之父，1736年也被称为“图论元年”。 图论部分共分为三章：图的基本概念及其矩阵表示，几种图的介绍，树。本章将首先讨论图论中的一些基本概念，继之阐述图的基本性质，而后介绍图的矩阵表示方法。,7/128,主要内容,图的基本概念 子图和图的运算 路径、回路、连通性 图的矩阵表示 欧拉图 哈密尔顿图 二部图、平面图 网络 树,基础知识,特殊图,8/128,9.1图的基本概念,图是由一些顶点和连接这些顶点的一些边所组成的离散结构。 根据连接顶点对的边的种类和数目的不同，图有多种类型。几乎每一门可以想到的学科，都有用图模型来解决的问题。,9/128,图的种类,(1)
4、如果 ，则称 为无向图。 (2) 如果 ，则称 为有向图。,无论是无向图还是有向图，都统称为图，其中V的元素称为图G的结点，E的元素称为图G的边，图G的结点数目称为图的阶。,可以用几何图形表示上面定义的图。用小圆圈表示结点。在无向图中，若 ，就用连接结点v1和v2的无向线段表示边e。在有向图中，若 ，就用v1指向v2的有向线段表示边e。,10/128,图的基本概念,定义： 设无向图 ， ，,(1)如果 ，则称e与v1(或v2)互相关联。e连接v1和v2，v1和v2既是e的起点，也是e的终点，也称v1和v2为点邻接。 (2)如果两条不同的边e1和e2与同一个结点关联，则称e1和e2为边邻接。,也
5、就是说，共边的点称为点邻接；共点的边称为边邻接。,11/128,图的基本概念,定义：设有向图 。如果 ，则称e连接v1和v2，e与v1(或v2)互相关联，分别称v1和v2是e的起点和终点，也称v1和v2邻接。,例：无向图,e1连接v1和v2，v1和v2邻接，e1和e2邻接。,12/128,图的基本概念,例：有向图,v2和v1分别是e1的起点和终点，v2与v1邻接。,13/128,图的基本概念,定义： 设图 ,e1和e2是G的两条不同的边。,(1)如果与e1关联的两个结点相同，则称e1为自圈(或称环和回路)。 (2) 如果 ，则称e1与e2平行。 (3)如果图G没有自圈，也没有平行边，则称G为简
6、单图。 (4)如果图G没有自回路，有平行边，则称G为多重边图。 (5)如果图G既有自回路，又有平行边，则称G为伪图。,14/128,图的种类,例：中国主要城市通讯图,15/128,图的种类,16/128,度,定义： 。,如果G是无向图，G中与v关联的边和与v关联的自回路的数目之和称为v的度(或次)，记为 。 如果G是有向图，G中以v为起点的边的数目称为v的出度，记为 ；G中以v为终点的边的数目称为v的入度，记为 ；v的出度与入度之和称为v的度，记为 。,注意，在计算无向图中结点的度时，自回路要考虑两遍，因为自回路也是边。,17/128,度,例：计算下图中各结点的度。,18/128,度,定理：在
7、无向图中，所有节点的度数之和等于边数的2倍。,证：因为每条边给图G带来两度，设图G有m条边，所以图G共有2m度，等于图G的所有结点的度数之和。,定理：在有向图中，所有顶点的度数之和等于边的2倍；所有顶点的入度之和等于所有节点的出度之和，都等于边数。,度,例：结点的度。,19/128,20/128,结点,定义：度数为奇数的结点称为奇结点，度数为偶数的结点称为偶结点。,定理：任何图都有偶数个奇结点。,定义： 度为0的结点称为孤立结点，度为1的结点称为端点。,21/128,一些特殊的简单图,零图：结点都是孤立结点的图称为零图。,平凡图：一阶零图称为平凡图。,圈图（Cn(n3)）：是由n个顶点v1,v
8、2,vn以及边v1,v2,v2,v3,vn-1,vn,vn,v1组成的。,22/128,一些特殊的简单图,轮图：对来说，当给圈图Cn添加一个顶点，并且把这个新顶点与Cn里的n个顶点逐个连接，可以得到轮图Wn。,23/128,一些特殊的简单图,正则图： 所有结点的度均为自然数d的无向图称为d度正则图。,24/128,一些特殊的简单图,完全无向图：设 ，如果n阶简单无向图G是n-1度正则图，则称G为完全无向图，记为Kn。,注意：完全无向图的任意两个不同结点都邻接。,一至五阶完全无向图,25/128,一些特殊的简单图,注意：完全有向图的任意两个不同结点之间都有一对方向相反的有向边相连接。,完全有向图
9、：设 ，每个结点的出度和入度均为n-1的n阶简单有向图称为完全有向图。,一至三阶完全有向图,26/128,一些特殊的简单图,27/128,特殊类型的图的一些应用,局域网：在一座大楼里，像小型计算机和个人电脑这样的计算机，以及像打印机这样的外设，可以用局域网来连接。有三种常见的局域网拓扑结构。,28/128,图的同构,从图的定义可以看出，图的最本质的内容是结点和边的关联关系。两个表面上看起来不同的图，可能表达相同的结点和边的关联关系。,29/128,图的同构,实际中，利用图的同构可以研究是否有可能用同样的方式画两个图。例如化学里，表示过去已知化合物的图可以用来判定想象中的新化合物是否已经研究过了
10、。,30/128,图的同构,定义：设图 和 。如果存在双射 和双射 , 使得对于任意的 ， 都满足,则称G与G同构，记作 ，并称f和g为G和G之间的同构映射，简称同构。,31/128,图的同构,换一种更简单的方法来描述：设图 和图 ，若存在从到的双射函数f，对于V中所有的结点a和b来说，在G中有a到b的边当且仅当在G中有f(a)和f(b)的边，就说G与G同构。,也就是说，两个同构的图有同样多的结点和边，并且映射f保持结点间的邻接关系，映射g保持边之间的邻接关系。,图同构的直观含义，是将其中一个图经过旋转、平移、拉伸等变形后与另一个图完全重合。,32/128,图的同构,例：求证下图和同构。,证明
11、：两个图点、边的数目都相同。设函数f为f(u1)=v1,f(u2)=v4,f(u3)=v3,f(u4)=v2。G中相邻的点是u1与u2，u2与u4，u4与u3，u3与u1，对应的像点f(u1)=v1与f(u2)=v4,f(u2)=v4与f(u4)=v2, f(u4)=v2与f(u3)=v3,f(u3)=v3与f(u1)=v1在H中相邻。因此，二图同构。,33/128,图的同构,两个图同构必须满足的必要条件是：,(1)顶点个数相同 (2)边数相同 (3)度数相同的顶点个数相同 (4)K度顶点的导出子图同构,判定图的同构比较难，但是却可以通过上述四点证明图不同构。,34/128,图的同构,例：判断
12、下列两图是否同构。,35/128,图的同构,例：判断下列两图是否同构。,36/128,上面两个图不是同构的，因为左图中度结点都和两个度结点相关联，而右图中的度结点和一个度结点相关联还和一个度结点相关联。,37/128,图的同构,例：判断下列两图是否同构。,38/128,上面两个图是同构的。我们只要构造双射函数 f:a1,b1,c1,d1,e1,f1a2,b2,c2,d2,e2,f2 并且f(a1)=f2 ,f(b1)=b2 ,f(c1)=c2 f(d1)=d2 ,f(e1)=a2 ,f(f1)=e2 f是个双射函数,并且保持了边的邻接关系,39/128,图的同构,判定两个图是否同构，已知的最好
13、算法具有指数的最坏情形时间复杂度（对图的结点来说）。不过，解决这个问题的线性平均情形时间复杂度的算法已经找到，而且有希望找到判定两个图是否同构的多项式最坏情形时间复杂度算法。一个名叫NAUTY的最佳算法，目前可以在个人电脑上秒之内判定带有100个结点的两个图是否同构。,40/128,图模型,图可以用在各种模型里，用于不同的行业。,栖息地重叠图：顶点表示物种，若两个物种竞争（他们共享某些食物来源），则用无向边连接表示他们的顶点。,41/128,图模型,熟人图：可以用模型表示人与人之间的各种关系。顶点表示人，当两个人互相认识时，用一条无向边连接这两个人。据估计，世界上所有人的熟人图有超过60亿个顶
14、点和可能超过1万亿条边。,好莱坞图：好莱坞图用顶点表示演员，当两个顶点的演员共同出演一部电影时，就用一条无向边连接这两个顶点。根据无联网电影数据库，在2001年11月，好莱坞图有574724个顶点和超过1600万条边，这些顶点所表示的演员出现在292609部电影中。,42/128,43/128,图模型,循环赛图：每个队其其他所有队各有一次的比赛称为循环赛。其中每个顶点表示每个队，若a队击败b队，则有一条从a指向b的有向边。,44/128,图模型,合作图：合作图可以用来为学术论文的合作者关系建立模型。顶点表示某个文章的某个作者（人），如果两个人合作论文，则用无向边连接这两个人。已经发现在数学研究
15、论文上合作的合作图有超过337000个顶点和496000条边。,网络图：互联网可以用有向图来建模，用顶点表示网页，若有从网页a指向网页b的链接，则做一条从a指向b的有向边。网络图几乎是连续变化的，几乎每秒都有新页面产生而又有其他页面被删除。目前网络图有超过10亿个顶点和几百亿条边。许多研究者正在研究网络图的性质，以便更好的理解网络的特性。,45/128,图模型,优先图与并发处理：通过并发的执行某些语句，计算机程序可能执行的更快。但重要的是，要避免语句执行时还要用到尚未执行语句的结果。语句与前面语句的相关性可以表示成有向图。用顶点表示某个语句，若在a语句执行完之前不能执行b语句，则引出一个从a到b的有向边，这样的图称为优先图。,46/128,图模型,47/128,9.2子图和图的运算,定义：设 和 为图。,平凡生成子图：对于图 ，G本身以及零图 都是G的平凡生成子图。,48/128,子图,定义： 设图
