《离散数学 图论.doc》由会员分享，可在线阅读，更多相关《离散数学 图论.doc（37页珍藏版）》请在金锄头文库上搜索。
1、第六章 图论基础图是建立和处理离散数学模型的一种重要工具。图论是一门应用性很强的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立图论模型来解决。随着计算机科学的发展，图论的应用也越来越广泛，同时图论也得到了充分的发展。这里将主要介绍与计算机科学关系密切的图论的内容。6.1 图的基本概念我们已知集合的笛卡尔积的概念，为了定义无向图，还需要给出集合的无序积的概念。任意两个元素a,b构成的无序对（Unordered pair）记作(a,b)，这里总有。设为两个集合，无序对的集合称为集合A与B的无序积（Un
2、ordered Product），记作。无序积与有序积的不同在于。例如，设，则,。为了引出图的定义，我们先介绍如下的例子。 MHBS图6.1-1starts=0,i =1i=1i=11?i=i+1s=s+1print sendNY图6.1-2例6.1-1 (1) 北京、上海、香港、澳门是中国的几个著名的城市，分别用字母表示为,城市的集合为，这些城市间现有的航空线的集合是。我们也可以将这些城市间的航空线关系用图6.1-1来表示。 的程序框图如图6.1-26.1.1 图的定义及相关概念定义6.1-1 一个无向图(Undirected Graph)G是一个有序二元组，记作，其中是一个非空集合，V中的
3、元素称为结点或顶点（Vertex）；E是无序积的多重子集（元素可重复出现的集合），称E为G的边集(Edge Set)，E中的元素称为无向边或简称边(Edge)。在一个图中，为了表示V和E分别是图G的结点集和边集，常将V记成，而将E记成。以上给出的是一个无向图的数学定义。它们可以用图形来表示，而这种图形有助于我们理解图的性质。在这种表示法中，每个结点用点来表示，每条边用线来表示，这样的线连接着代表该边端点的两个结点。例如,G的图形如图6.1-3所示。图6.1-4图6.1-3定义6.1-2一个有向图(Directed Graph)G是一个有序二元组，记作，其中V是一个非空的结点（或顶点）集；E是笛
4、卡尔积VV的多重子集，其元素称为有向边(Directed Edge)，也简称边或弧 (Arc)。对于一个有向图G，一般也可画出图形来表示。例如，其中,的图形为图6.1-4。给图的结点标以名称，如图6.1-3中的这样的图称为标定图(Labled graph)。同时也可对边进行标定，图6.1-3中, , , , , .当时,称和是的端点（或顶点）(End Point)，并称与和是关联的(Incidence)，而称结点与是邻接的(Adjacent)。若两条边关联于同一个结点，则称两边是邻接的(Adjacent)。无边关联的结点称为孤立点(Isolated point)；若一条边关联的两个结点重合，则
5、称此边为环(Ring)或自回路(Self circuit)。若，则称与（或）关联的次数是1;若，称与关联的次数为2；若不是的端点，则称与的关联次数为0（或称e与u不关联）。在图6.1-3中，, ,是的端点，与、的关联次数均为1，是孤立点，是环，与关联的次数为2。当是有向边时，又称是的始点(Initial Point)，是的终点(Terminal Point)。 如果图的结点集和边集都是有限集，则称图为有限图(Finite graph)，本书讨论的图都是有限图。若图中,为了方便起见，这样的图也称为图，有时也简称阶图。这时图称为零图(Null Graph)，图称为平凡图(Trivial Graph
6、)。关联于同一对顶点的两条边称为平行边(Parallel Edge)（若是有向边方向应相同），平行边的条数称为边的重数。不含平行边和环的图称简单图(Simple Graph)。在本书中除非特别声明，一般是指简单图。6.1.2 结点的度定义6.1-3 设为一无向图，,关联边的次数称为v的度数，简称度(Degree)，记作的d(v)。设为一有向图，,v作为边的始点的次数，称为v的出度(Out Degree)，记作；v作为边的终点的次数称为v的入度(In Degree)，记作；v作为边的端点的次数称为v的度数，简称度(Degree)，记作，显然。在图6.1-3中，；在图6.1-4中，,。称度为1的结
7、点为悬挂点(Hanging point)，与悬挂点关联的边称为悬挂边(Hanging edge)。如图6.1-3中，是悬挂点，是悬挂边。记, ,分别称为图的最大度(Max Degree)和最小度(Min Degree)。若是有向图，除了,，还有如下的定义最大出度最大入度最小出度最小入度图6.1-4中, , , .例6.1-2 在图6.1-3中而该图有条边，即结点度数和是边数的倍。事实上这是图的一般性质。定理6.1-1 设图为具有结点集的图，则 。若为奇数，则称为奇点，若为偶数，则称为偶点。推论 任一图中，奇点个数为偶数。证明设，则 ,因为是偶数，所以也是偶数，而中每个点的度均为奇数，因此为偶数
8、。对有向图，还有下面的定理。定理6.1-2设有向图， 则.以上两个定理及推论都很重要，要牢记并灵活运用。设是图的结点集，称为的度序列。如图6.1-3的度序列为，图6.1-4的度序列是。例6.1-3 图的度序列为，则边数是多少？； 能成为图的度序列吗？为什么？图有12条边，度数为的结点有个，其余结点度均小于，问图中至少有几个结点？解 由握手定理 ，所以由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度序列。由握手定理，度数为的结点有个占去18度，还有度由其余结点占有，其余结点的度数可为，当均为时所用结点数最少，所以应由个结点占有这度，即图中至少有个结点。例6.1-4 证明在
9、个人的集体中，总有两个人在此团体中恰有相同个数的朋友。解 以结点代表人，二人如果是朋友，则在代表他们的结点间连上一条边，这样可得无向简单图，每个人的朋友数即是图中代表他的结点的度数，于是问题转化为：阶无向简单图必有两个结点的度数相同。用反证法，设中每个结点的度数均不相同，则度序列为，说明图中有孤立点，而图是简单图，这与图中有度结点相矛盾。所以必有两个结点的度数相同。6.1.3 完全图和补图定义6.1-4 设是无向简单图，若每一对结点之间都有边相连，则称为完全图(Complete Graph)，具有个结点完全图记作。设为有向简单图，若每对结点间均有一对方向相反的边相连，则称为(有向)完全图，具有
10、个结点的有向完全图记作。例6.1-5 图6.1-5给出几个完全图的例子。由完全图的定义可知，无向完全图的边数为,而有向完全图的边数为.图6.1-5定义6.1-5 设为阶(无向)简单图，从 n阶完全图中删去的所有边后构成的图称为的补图(Complement of graph)，记作。类似地,可定义有向图的补图。例6.1-6 图6.1-6中是的补图。由补图的定义，显然有如下的结论： 与互为补图，即； 若为阶图，则，且。定义6.1-6 各结点的度数均为的无向简单图称为k-正则图(Regular graph)。图6.1-7所示的图称为彼得森（Petersen）图，是正则图。图6.1-6图6.1-76.
11、1.4 子图与图的同构定义6.1-7 设，是两个图。若，且，则称是的子图(Subgraph)。是的母图(Contained graph)，记作。若或，则称是的真子图(Proper subgraph)。若且，则称是的生成子图(Spanning subgraph)。若且，以为结点集，以图中两个端点均在中的边为边集的子图，称为由V1导出的导出子图(Induced subgraph)，记作。设，且，以为边集，以中的边关联的结点为结点集的图的子图，称为导出的边导出子图，记作。fbacdGbacdf图6.1-8bacfacdf例6.1-7 在图6.1-8中，均是的真子图，其中是的生成子图，是由导出的导出子
12、图，是由导出的边导出子图。由于在画图的图形时，结点的位置和边的几何形状是无关紧要的，因此表面上完全不同的图形可能表示的是同一个图。为了判断不同图形是否表示同一个图形，在此我们给出图的同构的概念。设有两个图，如果存在双射，使得当且仅当（或者当且仅当），且它们的重数相同，则称图G与G1同构(Isomorphism)，记作。图6.1-9定义6.1-8说明，两个图的结点之间，如果存在双射，而且这种映射保持了结点间的邻接关系和边的重数（在有向图时还保持方向），则两个图是同构的。例6.1-8 图6.1-9中，其中，,其中, , , ,。容易看出，两个图同构的必要条件是： 结点数相同； 边数相同； 度序列相
13、同。但这不是充分的条件，例如图6.1-10中图虽然满足以上3个条件，但不同构。图中的4个3度结点与中的4个3度结点的相互间的邻接关系显然不相同。图6.1-10H1H2习题6.16.1-1 画出下列各图的图形并求出各结点的度(出度、入度)：。6.1-2 下列各组数中，哪些能构成无向图的度序列？哪些能构成无向简单图的度序列？ 1,1,1,2,3; 2,2,2,2,2; 3,3,3,3; 1,2,3,4,5; 1,3,3,3.hgbifcdaej63125108947图6.1-116.1-bcdea14235图6.1-123 设图若G有三个3度结点，两个2度结点，三个1度结点，试问：G有多少条边？
14、6.1-4 图G有12条边，三个度为4的结点，其余结点的度均为3，问图G有多少个结点？6.1-5 图6.1-11中与同构吗？若两图同构，写出结点之间的对应关系；若不同构，则说明理由。6.1-6 图6.1-12中，G1与G2，同构吗？为什么？6.2图的连通性计算机网络中常见的一个问题是，网络中任何两台计算机是否可以通过计算机间的信息传递而使其资源共享？我们可以用图论的方法对这个问题进行研究，其中用结点表示计算机，用边表示通讯连线，因此，计算机的信息资源共享问题就变为，图中任何两个结点之间是否都有连接通路存在?6.2.1 通路在图论的研究中，经常要考虑这样的问题，如何从一个图中的给定结点出发，沿着一些边移动到另一个结点。这种由结点和边形成的序列就引出了路的概念。定义6.2-1 设是图,从图中结点到的一条通路或路径 (walk)是图的一个点、边的交错序列,其中(或者) , ,分别称为通路的起点(Initial Point)和终点(Terminal Point),而称为内点(Interior point),通路中包含的边数n称为通路的长度(Leng
