图的基本概念及其矩阵表示

《图的基本概念及其矩阵表示》由会员分享，可在线阅读，更多相关《图的基本概念及其矩阵表示（128页珍藏版）》请在金锄头文库上搜索。

1、离散数学大连理工大学软件学院陈志奎2/128第9章 图的基本概念及其矩阵表示论3/128图论（Graph Theory）是数学的一个分 支。它以图为研究对象。图论中的图是由若 干给定的点及连接两点的线所构成的图形， 这种图形通常用来描述某些事物之间的某种 特定关系，用点代表事物，用连接两点的线 表示相应两个事物间具有这种关系。图论起源于著名的柯尼斯堡七桥问题。 在柯尼斯堡的普莱格尔河上有七座桥将河中 的岛及岛与河岸联结起来，如下图所示，A 、B、C，D表示陆地。 4/128图论的起源 哥尼斯堡七桥问题 ：17世纪的东普鲁士有 一座哥尼斯堡（Konigsberg）城，城中有一 条普雷格尔（Pre

2、gel）河，全城共有七座桥 将河中的岛及岛与河岸联结起来，如下图所 示，a,b,c,d表示陆地。从四块陆地的任何一块出发，怎样通过 且仅通过每座桥一次，最终回到出发地点？5/128图论的起源1736年瑞士大数学家列昂哈德欧拉 （Leonhard Euler）解决了这一问题，他 用了科学研究中最一般的方法抽象。 用四个字母a,b,c,d表示四块陆地，并用7 条线表示7座桥，从而将七桥问题抽象为 图的问题，寻找经过图中每边一次且仅一 次的回路，后来人们把有这样回路的图称 为欧拉图。6/128图论的起源欧拉证明了这个问题没有解，并且推广 了这个问题，给出了对于一个给定的图可以 某种方式走遍的判定法则

3、。这项工作使欧拉 成为图论的创始人。 欧拉被称为图论之父，1736年也被称为 “图论元年”。图论部分共分为三章：图的基本概念及 其矩阵表示，几种图的介绍，树。本章将首 先讨论图论中的一些基本概念，继之阐述图 的基本性质，而后介绍图的矩阵表示方法。7/128主要内容 图的基本概念 子图和图的运算 路径、回路、连通性 图的矩阵表示 欧拉图 哈密尔顿图 二部图、平面图 网络 树基础知识特殊图8/1289.1图的基本概念 图是由一些顶点和连接这些顶点的一 些边所组成的离散结构。 根据连接顶点对的边的种类和数目的 不同，图有多种类型。几乎每一门可 以想到的学科，都有用图模型来解决 的问题。9/128图的

4、种类(1) 如果 ，则称 为 无向图。 (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与同一个结点关 联，

5、则称e1和e2为边邻接边邻接。 也就是说，共边的点称为点邻接；共点的边称 为边邻接。 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没有自

6、圈，也没有平行边，则称G为简 单图。 (4)如果图G没有自回路，有平行边，则称G为多重 边图。(5)如果图G既有自回路，又有平行边，则称G为伪 图。14/128图的种类例：中国主要城市通讯图15/128图的种类类型边允许平行 边允许自环简单图无向否否多重图无向是否伪图无向是是有向图有向否是有向多重图有向是是16/128度定义： 。 (1)如果G是无向图，G中与v关联的边和与v关联 的自回路的数目之和称为v的度(或次)，记为。 (1)如果G是有向图，G中以v为起点的边的数目 称为v的出度，记为 ；G中以v为终点的 边的数目称为v的入度，记为 ；v的出度 与入度之和称为v的度，记为 。 注意，在计

7、算无向图中结点的度时，自回路要 考虑两遍，因为自回路也是边。 17/128度例：计算下图中各结点的度。18/128度定理：在无向图中，所有节点的度数之和等于边 数的2倍。 证：因为每条边给图G带来两度，设图G有m条 边，所以图G共有2m度，等于图G的所有结点的 度数之和。 定理：在有向图中，所有顶点的度数之和等于 边的2倍；所有顶点的入度之和等于所有节点的 出度之和，都等于边数。度 例：结点的度。19/12820/128结点定义：度数为奇数的结点称为奇结点奇结点，度数 为偶数的结点称为偶结点偶结点。 定理：任何图都有偶数个奇结点。 定义： 度为0的结点称为孤立结点孤立结点，度为1 的结点称为端

8、点端点。 21/128一些特殊的简单图零图：结点都是孤立结点的图称为零图零图。平凡图：一阶零图称为平凡图平凡图。圈图（Cn(n3)）：是由n个顶点v1,v2,vn以及边 v1,v2,v2,v3,vn-1,vn,vn,v1组成的。22/128一些特殊的简单图轮图：对来说，当给圈图Cn添加一个顶点 ，并且把这个新顶点与Cn里的n个顶点逐个连接 ，可以得到轮图Wn。23/128一些特殊的简单图正则图： 所有结点的度均为自然数d的无向 图称为d d度正则图度正则图。24/128一些特殊的简单图完全无向图：设 ，如果n阶简单无向图G是 n-1度正则图，则称G为完全无向图完全无向图，记为Kn。注意：完全无

9、向图的任意两个不同结点都邻接 。一至五阶完全无向图 25/128一些特殊的简单图注意：完全有向图的任意两个不同结点之间都 有一对方向相反的有向边相连接。 完全有向图：设 ，每个结点的出度和入度均 为n-1的n阶简单有向图称为完全有向图完全有向图。一至三阶完全有向图 26/128一些特殊的简单图27/128特殊类型的图的一些应用局域网：在一座大楼里，像小型计算机和个人 电脑这样的计算机，以及像打印机这样的外设 ，可以用局域网来连接。有三种常见的局域网 拓扑结构。28/128图的同构从图的定义可以看出，图的最本质的内容 是结点和边的关联关系。两个表面上看起来不 同的图，可能表达相同的结点和边的关联

10、关系 。29/128图的同构实际中，利用图的同构可以研究是否有可 能用同样的方式画两个图。例如化学里，表示 过去已知化合物的图可以用来判定想象中的新 化合物是否已经研究过了。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保

11、持结点间的邻接关系，映射g保 持边之间的邻接关系。 图同构的直观含义，是将其中一个图经 过旋转、平移、拉伸等变形后与另一个图完 全重合。32/128图的同构例：求证下图和同构。证明：两个图点、边的数目都相同。设函数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)

12、顶点个数相同(2)边数相同(3)度数相同的顶点个数相同(4)K度顶点的导出子图同构判定图的同构比较难，但是却可以通过上述四 点证明图不同构。34/128图的同构例：判断下列两图是否同构。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)

13、=c2 f(d1)=d2 ,f(e1)=a2 ,f(f1)=e2 f是个双射函数,并且保持了边的邻接 关系39/128图的同构判定两个图是否同构，已知的最好算法具 有指数的最坏情形时间复杂度（对图的结点来 说）。不过，解决这个问题的线性平均情形时 间复杂度的算法已经找到，而且有希望找到判 定两个图是否同构的多项式最坏情形时间复杂 度算法。一个名叫NAUTY的最佳算法，目前 可以在个人电脑上秒之内判定带有100个结 点的两个图是否同构。40/128图模型 图可以用在各种模型里，用于不同的行业。栖息地重叠图：顶点表示物种，若两个物种竞争（ 他们共享某些食物来源），则用无向边连接表示他 们的顶点。4

14、1/128图模型熟人图：可以用模型表示人与人之间的各种关 系。顶点表示人，当两个人互相认识时，用一 条无向边连接这两个人。据估计，世界上所有 人的熟人图有超过60亿个顶点和可能超过1万 亿条边。好莱坞图：好莱坞图用顶点表示演员，当两个 顶点的演员共同出演一部电影时，就用一条无 向边连接这两个顶点。根据无联网电影数据库 ，在2001年11月，好莱坞图有574724个顶点和 超过1600万条边，这些顶点所表示的演员出现 在292609部电影中。42/12843/128图模型循环赛图：每个队其其他所有队各有一次的比赛称 为循环赛。其中每个顶点表示每个队，若a队击败b 队，则有一条从a指向b的有向边。44/128图模型合作图：合作图可以用来为学术论文的合作者关 系建立模型。顶点表示某个文章的某个作者（人 ），如果两个人合作论文，则用无向边连接这两 个人。已经发现在数学研究论文上合作的合作图 有超过337000个顶点和496000条边。网络图：互联网可以用有向图来建模，用顶点表 示网页，若有从网页a指向网页b的链接，则做一 条从a指向b的有向边。网络图几乎是连续变化的 ，几乎每秒都有新页面产生而又有其他页面被删 除。目前网络图有超过10亿个顶点和几百亿条边 。许多研究者正在研究网络图的