《离散数学教学课件 ppt 作者 陈志奎 第九章 图的基本概念及其矩阵表示》由会员分享，可在线阅读，更多相关《离散数学教学课件 ppt 作者 陈志奎 第九章 图的基本概念及其矩阵表示（91页珍藏版）》请在金锄头文库上搜索。
1、,第九章 图的基本概念及其矩阵表示,离散数学 陈志奎主编 人民邮电出版社,前言,图论（Graph Theory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。,前言,图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有7座桥将河中的岛及岛与河岸联结起来，如下图所示，a、
2、b、c、d表示陆地。 从4块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？1736年瑞士大数学家列昂哈德欧拉（Leonhard Euler）解决了这一问题，他用了科学研究中最一般的方法抽象。用四个字母a，b，c，d表示4块陆地，并用7条线表示7座桥，从而将七桥问题抽象为图的问题，寻找经过图中每边一次且仅一次的回路，后来人们把有这样回路的图称为欧拉图。,图论的起源,前言,图是建立和处理离散数学模型的一种重要工具。图论是一门应用性很强的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立
3、图论模型来解决。随着计算机科学的发展，图论的应用也越来越广泛，同时图论也得到了充分的发展。这里将主要介绍与计算机科学关系密切的图论的内容。 图论部分共分为三章：图的基本概念及其矩阵表示，几种图的介绍，树。,图论的起源,图的基本概念,主要内容,子图和图的运算,路径、回路和连通性,图的矩阵表示,9.1 图的基本概念,图是用于描述现实世界中离散客体之间关系的有用工具。在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点a指向点b的有向线段来代表客体a和b之间的二元关系aRb，这样，集合上的二元关系就可以用点的集合V和有向线的集合E构成的二元组（V，E）来描述。同样的方法也可
4、以用来描述其他的问题。 当我们考察交通路线时，可以用点来代表城市，用线来表示两城市间有道路通达；当研究计算机网络时，可以用点来表示计算机及终端，用线表示它们之间的信息传输通道。在这种表示法中，点的位置及线的长短和形状都是无关紧要的，重要的是两点之间是否有线相连。从图的这种表示方式中可以抽象出图的数学概念来。,6,图的定义,9.1 图的基本概念,定义9.1 设一个三元组 ， ， ，其中 是一个非空的节点集合， 是有限的边集合，如果 是从边集合 E 到点集合 V 中的无序偶映射，即 ，则称 为无向图。 在无向图中，如果 ，则称 e 连接 和 ， 和 既是 e 的起点，也是 e 的终点，也称 和 为
5、点邻接。如果两条不同的边 和 与同一个结点连接，则称 和 为边邻接。,7,图的定义,9.1 图的基本概念,定义9.1 设一个三元组 ， ， ，其中 是一个非空的节点集合， 是有限的边集合，如果 是从边集合 E 到点集合 V 中的有序偶映射，即 ，则称 为无向图。 在有向图中，如果 ，则称e连接 和 ，分别称 和 是 e 的起点和终点，也称 和 邻接。,8,图的定义,9.1 图的基本概念,无论是无向图还是有向图，都统称为图，其中 V 的元素称为图G的结点，E的元素称为图G的边，图G的结点数目称为图的阶。 我们可以用几何图形表示上面定义的图。用小圆圈表示结点。在无向图中，若 ，就用连接结点 和 的
6、无向线段表示边 g。在有向图中，若 ，就用 指向 的有向线段表示边 e。,9,图的定义,9.1 图的基本概念,例9.1 无向图 和有向图 分别示于图9.1和图9.2。在图9.1中， 连接 和 ， 和 邻接， 和 邻接。在图9.2中， 和 分别是 的起点和终点， 与 邻接。,10,图9.1,图9.2,9.1 图的基本概念,定义9.3 设图 ， e1和e2是G的两条不同的边。 （1）如果与e1连接的两个结点相同，则称e1为自回路或环。 （2）如果 ，则称e1与e2平行。 （3）如果图G没有自回路，也没有平行边，则称G为简单图。 （4）如果图G没有自回路，有平行边，则称G为多重边图。 （5）如果图G
7、既有自回路，又有平行边，则称G为伪图。,11,在有向图中，如果两条边连接的结点相同，但方向相反，它们也不是平行边。,9.1 图的基本概念,12,例9.2 中国主要城市通讯图如图9.3所示：当数据量很小时，可采用单线通讯如图（a）所示；数据量很大时，两点之间往往要连接多条线路如图（b）所示。为了诊断本地故障也可采用自环连接如图（c）所示；有时数据可以不是双向传输，沈阳只接收数据不发送数据如图（d）所示（有向图允许有自环）；数据量大时也可采用多重有向图如图（e）所示。,9.1 图的基本概念,简单图是一类非常重要的图。在某些图论著作中，把我们定义的简单图称为图，而把允许有平行边的图称为多重边图，把我
8、们定义的图称为伪图。 从图的定义可以看出，图的最本质的内容是结点和边的关联关系。两个表面上看起来不同的图，可能表达了相同的结点和边的关联关系。如图9.4的两个图，不仅结点和边的数目相同，而且结点和边的关联关系也相同。为了说明这种现象，我们引进两个图同构的概念。,13,9.1 图的基本概念,定义9.4 设图 和 。如果存在双射 和双射 ，使得对于任意的 ， 都满足 则称G与 同构，记作 ，并称f和g为G和 之间的同构映射，简称同构。 两个同构的图有同样多的结点和边，并且映射 保持结点间的邻接关系，映射 保持边之间的邻接关系。,14,同构映射,9.1 图的基本概念,定义9.5 设 。 （1）如果
9、G 是无向图，G 中与 v关联的边和与 v 关联的自回路的数目之和称为 v 的度（Degree），记为 。 （2）如果 G 是有向图，G 中以 v为起点的边的数目称为 v 的出度（Out Degree），记为 ；G 中以 v 为终点的边的数目称为 v 的入度（In Degree），记为 ；v 的出度与入度之和称为 v的度（Degree），记为 ，显然 =,15,节点的度,在计算无向图中结点的度时，自回路要考虑两遍，因为自回路也是边。,9.1 图的基本概念,例9.3 在图9.5所示的无向图中， ， ， ， 。在图9.6所示的有向图D中 ， 1， 图9.5 图9.6 显然，每增加一条边，都使图中所
10、有结点的度数之和增加2。,16,9.1 图的基本概念,定理9.1 在无向图中，所有节点的度数之和等于边数的2倍。 证明：因为每条边（包括环）给图带来两度，图有m条边，所以图共有2m度，等于图的所有结点的度数之和。 定理9.2 在有向图中，所有顶点的度数之和等于边的2倍；所有顶点的入度之和等于所有节点的出度之和，都等于边数。 证明：因为每条边（包括环）给图带来两度（一个出度和一个入度），图有 m 条边，所以图共有 2m 度（m个入度和 m 个出度），等于图的所有结点的度数之和。,17,9.1 图的基本概念,18,9.1 图的基本概念,定义9.6 度数为奇数的结点称为奇结点，度数为偶数的结点称为偶
11、结点。 推论9.1 任何图都有偶数个奇结点。 证明：设 ， ，则 因为 是偶数，所以 也是偶数， 而 中每个点 v 的度 均为奇数，因此 为偶数。,19,9.1 图的基本概念,定义9.7 设 是图 的结点集，称 为 G 的度序列。如图9. 5的度序列为 3,4,4,1,0，图9.6的度序列是 3,4,3,2。 定义9.8 度为0的结点称为孤立结点，度为1的结点称为端点。,20,9.1 图的基本概念,定义9.9 定义以下图： （1）结点都是孤立结点的图称为零图。 （2）一阶零图称为平凡图。 （3）由n个顶点v1,v2,vn(n3)以及边v1,v2,v2,v3,vn-1,vn,vn,v1组成的图（Cn）称为圈图，如图9.7。,21,图的定义,图9.7 圈图,9.1 图的基本概念,定义9.9 定义以下图： （4）对n来说，当给圈图Cn添加一个顶点，并且把这个新顶点与Cn里的n个顶点逐个连接，可以得到轮图（Wn），如图9.8。 图9.8 轮图,22,图的定义,9.1 图的基本概念,定义9.9 定义以下图： （5）所有结点的度均为自然数 的无向图称为 度正则图，如图9.9。 3度、4度正则图,23,图的定义,9.1 图的基本概念,定义9.9 定义以下图： （6）设 ，如果 n 阶简单无向图 G是 n-1 度正则图，则
