有向图与无向图-文档资料

1、1离散数学CH7图的基本概念1无向无向图及有向图图及有向图2 图论的起源图论的起源图论是组合数学的图论是组合数学的一个分支一个分支, ,它起源它起源于于17361736年欧拉的第年欧拉的第一篇关于图论的论一篇关于图论的论文，这篇论文解决文，这篇论文解决了著名的了著名的 “哥尼哥尼斯堡七桥问题斯堡七桥问题” ，从而使欧拉成为，从而使欧拉成为图论的创始人。图论的创始人。31.哥尼斯堡七桥问题 哥尼斯堡哥尼斯堡位于前苏联的加里位于前苏联的加里宁格勒，历史上曾经是德国宁格勒，历史上曾经是德国东普鲁士省的省会，普雷格东普鲁士省的省会，普雷格尔河横穿城堡，河中有尔河横穿城堡，河中有两个两个小岛小岛，共有，

2、共有七座桥七座桥连接两岸连接两岸和小岛。和小岛。 问题：问题： 在所有桥都只能走一在所有桥都只能走一遍的前提下，如何才能把这遍的前提下，如何才能把这个地方所有的桥都走遍？个地方所有的桥都走遍？4哥尼斯堡七桥问题尼斯堡七桥问题解决方式解决方式莱昂哈德莱昂哈德欧拉欧拉（Leonhard EulerLeonhard Euler）在）在17351735年圆满地年圆满地解决了这一问题，证明这种方法并不存在，也顺带解解决了这一问题，证明这种方法并不存在，也顺带解决了决了一笔画问题一笔画问题。他在圣彼得堡科学院发表了图论史。他在圣彼得堡科学院发表了图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平上第一篇

3、重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数。，则这一点的线数必须是偶数。 /wiki/File:Konigsberg_bridges.png 5图论的起源欧拉最后给出任意一种河欧拉最后给出任意一种河桥图能否全桥图能否全部走一次的部走一次的判定法则判定法则。如果通。如果通奇数座奇数座桥的桥的地方地方不止两个不止两个，那么满足要求的路线便不，那么满足要求的路线便不

4、存在了。如果只有存在了。如果只有两个地方两个地方通奇数座桥，通奇数座桥，则可从其中任何一地出发找到所要求的路则可从其中任何一地出发找到所要求的路线。若线。若没有一个地方没有一个地方通奇数座桥，则从任通奇数座桥，则从任何一地出发，所求的路线都能实现，他还何一地出发，所求的路线都能实现，他还说明了怎样快速找到所要求的路线。说明了怎样快速找到所要求的路线。不少数学家都尝试去解析这个事例。而这不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的些解析，最后发展成为了数学中的图论图论。6 欧 拉 图定义定义 一个图一个图, ,如果能够从一点出如果能够从一点出发发, ,经过每条边一次且仅一次

5、再经过每条边一次且仅一次再回到起点回到起点, ,则称为则称为欧拉图欧拉图 欧拉在论文中给出并证明了判欧拉在论文中给出并证明了判断欧拉图的充分必要条件定理断欧拉图的充分必要条件定理, ,并证并证明了七桥图不是欧拉图。明了七桥图不是欧拉图。7 从这个问题可以看出：图图：图用点代表各个事物图用点代表各个事物, ,用边代用边代表各个事物间的二元关系。表各个事物间的二元关系。 所以，图是研究集合上的二元所以，图是研究集合上的二元关系的工具，是建立数学模型的一关系的工具，是建立数学模型的一个重要手段。个重要手段。8 2、一百多年以后 “七桥七桥”问题以后，图论的研究停滞了一问题以后，图论的研究停滞了一百多

6、年，直到百多年，直到18471847年，基尔霍夫用年，基尔霍夫用“树树”图解决了电路理论中的求解联立方程图解决了电路理论中的求解联立方程的问题，十年后凯莱用的问题，十年后凯莱用 “树树” 图计算有图计算有机化学中的问题。在这一时期流行着两机化学中的问题。在这一时期流行着两个著名的图论问题：哈密尔顿回路问题个著名的图论问题：哈密尔顿回路问题和和 “四色猜想四色猜想” 问题。问题。93.哈密尔顿回路问题 18561856年年, ,英国数学家哈密尔顿设计英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个了一个周游世界的游戏，他在一个正十二面体的二十个顶点上标上二正十二面体的二十个顶点上标上二十个著

7、名城市的名字，要求游戏者十个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市从一个城市出发，经过每一个城市一次且仅一次，然后回到出发点。一次且仅一次，然后回到出发点。10哈密尔顿回路图 此路线称为：此路线称为：哈密尔顿回路哈密尔顿回路， 而此图称为：而此图称为：哈密尔顿图哈密尔顿图。114、“四 色 猜 想” 问 题 人们在长期为地图人们在长期为地图( (平面图平面图) )上色时发上色时发现，最少只要四种颜色，就能使得现，最少只要四种颜色，就能使得有相邻国界的国家涂上不同的颜色有相邻国界的国家涂上不同的颜色 四色猜想的证明一直没有解决，四色猜想的证明一直没有解决，直到一百多年后，在计算

8、机出现以直到一百多年后，在计算机出现以后，于后，于19761976年用计算机算了年用计算机算了12001200多多小时，才证明了四色猜想问题小时，才证明了四色猜想问题。12 5、又过了半个世纪 四色猜想问题出现后，图论的研四色猜想问题出现后，图论的研究又停滞了半个世纪，直到究又停滞了半个世纪，直到19201920年年科尼格科尼格写了许多关于图论方面的论写了许多关于图论方面的论文，并于文，并于19361936年发表了第一本关于年发表了第一本关于图论的书。此后图论从理论上到应图论的书。此后图论从理论上到应用上都有了很大发展。特别是计算用上都有了很大发展。特别是计算机的出现使图论得到飞跃的发展。机的

9、出现使图论得到飞跃的发展。13 学好图论十分重要 图论是组合数学的一个分支，与其它数学分支图论是组合数学的一个分支，与其它数学分支如群论、矩阵论、集合论、概率论、拓扑学、数如群论、矩阵论、集合论、概率论、拓扑学、数值分析等有着密切的联系值分析等有着密切的联系 。 图论给含有二元关系的系统提供了数学模型，图论给含有二元关系的系统提供了数学模型，因而在许多领域里都具有越来越重要的地位，并因而在许多领域里都具有越来越重要的地位，并且在物理、化学、信息学、运筹学等各方面都取且在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。得了丰硕的成果。 从二十世际从二十世际50 50 年代以来，由于计算机的

10、迅速发年代以来，由于计算机的迅速发展，有力地推动了图论的发展，使得图论成为数展，有力地推动了图论的发展，使得图论成为数学领域里发展最快的分支之一。学领域里发展最快的分支之一。14第第7 7章章 图的概念图的概念本章学习：本章学习：1.1. 无向无向图及有向图图及有向图2.2. 通路、回路、图的连通性通路、回路、图的连通性3.3. 图的矩阵表示图的矩阵表示4.4. 最短路径及关键路径最短路径及关键路径 15今日内容无向图及有向图无向图及有向图图的一些相关概念图的一些相关概念度度握手定理握手定理子图相关概念子图相关概念图同构图同构16预备知识有序积有序积: A: AB= |xAyBB= |xAyB

11、有序对有序对: : 无序积无序积: A&B= (x,y) |xAyB: A&B= (x,y) |xAyB无序对无序对: (x,y)=(y,x): (x,y)=(y,x)多重集多重集: a,a,a,b,b,ca,b,c: a,a,a,b,b,ca,b,c重复度重复度: a: a的重复度为的重复度为3, b3, b的为的为2, c2, c的为的为1 1171 1、无序积、无序积：A&BA&B设设A A、B B为两集合，称为两集合，称a,b|aAbBa,b|aAbB为为A A与与B B 的无序积，记作的无序积，记作A&BA&B。为方便起见，将无序对为方

12、便起见，将无序对a,ba,b记作记作 ( a, b)( a, b)。 ( a, b)( a, b)(b, a)(b, a)例：例：设设A=a,b, B=c,d, A=a,b, B=c,d, 则则A&BA&B？ A&AA&A？ A&B=( a, c), (a,d),( b,c),( b,d)A&B=( a, c), (a,d),( b,c),( b,d) A&A=( a, a ),( a, b),( b, b) A&A=( a, a ),( a, b),( b, b)182 2、无向图、无向图一个一个无向图无向图G G是一个二元组是

13、一个二元组,即即G=,G=,其中其中: :. . V V是一个非空集合是一个非空集合, ,称为称为G G的的顶点集顶点集,V,V中元素中元素称为称为顶点顶点或或结点结点; ;. . E E是无序积是无序积V&VV&V的一个的一个多重子集多重子集, ,称称E E为为G G的的边边集集,E,E中元素称为中元素称为无向边无向边或简称或简称边边。用小圆圈表示用小圆圈表示V V中顶点中顶点, ,若若(a,b)E,(a,b)E,就在就在a,ba,b之间连之间连线段表示边线段表示边(a,b),(a,b),其中顶点的位置、连线的曲直及其中顶点的位置、连线的曲直及是否相交都无关紧要。是否相交都无

14、关紧要。19无向图示例 给定无向图G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). 203 3、有向图、有向图 一个一个有向图有向图D D是一个二元组是一个二元组, 即即D = ,D = ,其中：其中： . . V V同无向图中的顶点集同无向图中的顶点集; ; . . E E是笛卡儿积的是笛卡儿积的多重子集多重子集, ,其元素称为其元素称为有向边有向边, ,也简称也简称边边. .21有向图示例 给定有向图D=，其中 Va,b,c,d，E,。 22图的一些概念和规定G G表示无向图，但有

15、时用表示无向图，但有时用G G泛指图泛指图( (无向的或有向的无向的或有向的) )。D D只能表示有向图。只能表示有向图。V(G)V(G)，E(G)E(G)分别表示分别表示G G的顶点集和边集。的顶点集和边集。若若| |V(G)|V(G)|n n，则称则称G G为为n n阶图阶图。若若| |V(G)|V(G)|与与| |E(G)|E(G)|均为有限数，则称均为有限数，则称G G为为有限图有限图。 若边集若边集E(G)E(G)，则称则称G G为为零图零图，此时，又若，此时，又若G G为为n n阶图阶图，则称，则称G G为为n n阶零图阶零图，记作，记作N Nn n，特别地，称特别地，称N N1

16、1为为平凡图平凡图 在图的定义中规定顶点集在图的定义中规定顶点集V V为非空集，但在图的运算中为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空集的图为空图空图，并将，并将空图记为空图记为。 23标定图与非标定图、基图 将图的集合定义转化成图形表示之后，将图的集合定义转化成图形表示之后，常用常用e ek k表示表示无向边无向边( (v vi i,v ,vj j) )（或或有向边有向边 ），），并称顶点或边用字母标定的并称顶点或边用字母标定的图为图为标定图标定图，否则称为，否则称为非标定图非标定图。将有向图各有向边

17、均改成无向边后的无将有向图各有向边均改成无向边后的无向图称为原来图的向图称为原来图的基图基图。易知标定图与非标定图是可以相互转化易知标定图与非标定图是可以相互转化的，任何无向图的，任何无向图G G的各边均加上箭头就的各边均加上箭头就可以得到可以得到以以G G为基图的有向图为基图的有向图。 24关联与关联次数、环、孤立点 设设G G为无向图，为无向图，ek( (vi, ,vj)E)E，称称vi, ,vj为为ek的端点，的端点，ek与与vi或或ek与与vj是是彼此相关联彼此相关联的。的。若若vivj，则称则称ek与与vi或或ek与与vj的的关联次数关联次数为为1 1。若若vivj，则称则称ek与与

18、vi的的关联次数为关联次数为2 2，并称，并称ek为为环环。任意的任意的vlVV，若若vlvi且且vlvj，则称则称ek与与vl的的关关联次数为联次数为0 0。 25关联与关联次数、环、孤立点 设设D D为有向图，为有向图，ek EE，称称vi, ,vj为为ek的的端点端点。若若vivj，则称则称ek为为D D中的中的环环。无论在无向图中还是在有向图中，无边无论在无向图中还是在有向图中，无边关联的顶点均称为关联的顶点均称为孤立点孤立点。 26相邻与邻接 设无向图设无向图G GVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et( (vi，vj) )，则称则称vi与与vj是彼此相是

19、彼此相邻的邻的若若ek与与el至少有一个公共端点，则称至少有一个公共端点，则称ek与与el是彼此是彼此相邻的相邻的。 设有向图设有向图D DVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et ，则称则称vi为为et的始点的始点，vj为为et的终点，并称的终点，并称vi邻接到邻接到vj，vj邻接于邻接于vi。若若ek的终点为的终点为el的始点，则称的始点，则称ek与与el相邻相邻。27例：点边之间的关联次数例：点边之间的关联次数28例：点点、边边之间的相邻关系例：点点、边边之间的相邻关系29顶点的度数定义定义 设设G G为一无向图，为一无向图， vVV，称称v作作为边的端点次数之

20、和为为边的端点次数之和为v的度数，简称为度的度数，简称为度，记做，记做 dG( (v) )。在不发生混淆时，简记为在不发生混淆时，简记为d( (v) )。设设D DVE为有向图，为有向图， vVV，称称v作为边的作为边的始点次数之和始点次数之和为为v的的出度出度，记做，记做d+ +D( (v) )，简记作简记作d+ +( (v) )。称称v作为边的作为边的终点次数之和终点次数之和为为v的的入度入度，记做，记做 d -D( (v) )，简记作简记作d- -( (v) )。称称d+ +( (v)+)+d- -( (v) )为为v v的度数的度数，记做，记做d( (v) )。30d (v1)=4 d

21、(v2)=4 d(v3)=3 d(v4)=1 d(v5)=0 31d+(v1)=2d+ (v2)=1 d+ (v3)=3 d+ (v4)=1 d+ (v5)=1 d-(v1)=1d- (v2)=3 d- (v3)=0 d- (v4)=3 d- (v5)=1 d (v1)=3d (v2)=4 d (v3)=3 d (v4)=4 d (v5)=2 32最大(出/入)度,最小(出/入)度在无向图在无向图G G中中，最大度: (G) = max dG(v) | vV(G) 最小度: (G) = min dG(v) | vV(G) 在有向图在有向图D D中，中，最大出度: +(D) = max dD+(

22、v) | vV(D) 最小出度: +(D) = min dD+(v) | vV(D) 最大入度: -(D) = max dD-(v) | vV(D) 最小入度: -(D) = min dD-(v) | vV(D) 简记为, , +, +, -, -33握手定理（图论基本定理）握手定理（图论基本定理）定理定理7.1 7.1 设图G=为无向图或有向图， V = v1, v2, vn,|E|=m，则说明说明任何无向图中，各顶点度数之和等于边数的两倍。证明证明G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。 推论：推论：任何图中，度为奇数

23、的顶点个数为偶数。 12niid vm34问题研究问题：问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。说明：说明：(1)很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的关系。35握手定理握手定理定理7.2 设有向图D=， V = v1, v2, vn,|E|=m，则 11nniiiidvdvm36度数列设设G G为一个为一个n阶无

24、向图，阶无向图，V V v1 1, ,v2 2,vn ，称称d( (v1 1) )，d( (v2 2) )，d( (vn n) )为为G G的的度数列度数列。对于对于顶点标定顶点标定的无向图，它的度数列是唯一的。的无向图，它的度数列是唯一的。反之，对于给定的非负整数列反之，对于给定的非负整数列d d1 1, ,d2 2,dn ，若存在若存在V V v1 1, ,v2 2,vn 为顶点集的为顶点集的n阶无向图阶无向图G G，使得使得d( (vi) )di，则称则称d是是可图化可图化的。的。特别地，若所得图是简单图，则称特别地，若所得图是简单图，则称d是是可简单图化可简单图化的。的。类似地，设类似

25、地，设D D为一个为一个n n阶有向图，阶有向图，V V v1 1, ,v2 2,vn ，称称d( (v1 1) )，d( (v2 2) )，d( (vn) )为为D D的度数列，的度数列，另外称另外称d+ +( (v1 1) )，d+ +( (v2 2) )，d+ +( (vn) )与与d- -( (v1 1) )，d- -( (v2 2) )，d- -( (vn) )分别为分别为D D的的出度列出度列和和入度列入度列。37度数列举例按顶点的标定顺序，度数列为 4,4,2,1,3。38度数列举例按字母顺序，度数列：5,3,3,3出度列：4,0,2,1入度列：1,3,1,239 (4，4，3，

26、1，0) (3，4，3，4，2)练习：练习：40可图化的充要条件定理 设非负整数列d(d1，d2，dn)，则d是可图化的当且仅当 n n1)2(mod0iid证明 必要性。由握手定理显然得证。充分性。由已知条件可知，d中有偶数个奇数度点。奇数度点两两之间连一边，剩余度用环来实现。533141例例7.17.1： (3, 3, 2, 3), (5, 2, 3, 1, 4)(3, 3, 2, 3), (5, 2, 3, 1, 4)能成为图的度能成为图的度数序列吗？为什么？数序列吗？为什么？ 已知图已知图G G中有中有1010条边，条边，4 4个个3 3度顶点，其余顶点的度顶点，其余顶点的度数均小于等

27、于度数均小于等于2 2，问，问G G中至少有多少个顶点？为中至少有多少个顶点？为什么？什么？解：解：1.1.由于这两个序列中，奇数度顶点个数均为奇数，由于这两个序列中，奇数度顶点个数均为奇数，由握手定理的推论可知，它们都不能成为图的度由握手定理的推论可知，它们都不能成为图的度数序列。数序列。2.2.显然，显然，图图G中的其余顶点度数均为中的其余顶点度数均为2时时G图的顶点图的顶点数最少数最少. 设设G图至少有图至少有x个顶点个顶点. 由握手定理可知，由握手定理可知， 34+2(x-4)=2 10 解得解得: x=8 所以所以G至少有至少有8个顶点。个顶点。42简单图与多重图 定义定义 在在无向

28、图无向图中，关联一对顶点的无向边如果多于中，关联一对顶点的无向边如果多于1 1条条，则称这些边为，则称这些边为平行边平行边，平行边的条数称为，平行边的条数称为重数重数。在在有向图有向图中，关联一对顶点的有向边如果多于中，关联一对顶点的有向边如果多于1 1条，条，并且这些边的始点和终点相同并且这些边的始点和终点相同( (也就是它们的方向相也就是它们的方向相同同) )，则称这些边为，则称这些边为平行边平行边。含平行边的图称为含平行边的图称为多重图多重图。既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图。43简单图与多重图示例 44完全图定义定义7 7. .7 7 设G为n阶无向

29、简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图阶完全图，记做Kn(n1)。 设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D是n阶有向完全图阶有向完全图。设D为n阶有向简单图，若D的基图为n阶无向完全图Kn，则称D是n阶竞赛图阶竞赛图。45完全图举例n阶无向完全图的边数为：阶无向完全图的边数为：n( (n-1)/2-1)/2n阶有向完全图的边数为：阶有向完全图的边数为：n( (n-1)-1)n阶竞赛图的边数为：阶竞赛图的边数为： n( (n-1)/2-1)/2K53阶有向完全图4阶竞赛图46正则图定义定

30、义设设G G为为n阶无向简单图，若阶无向简单图，若vV(G)V(G)，均有均有d( (v) )k，则称则称G G为为k- -正则图正则图。 举例举例 n阶零图是阶零图是0- 0-正则图正则图n阶无向完全图是阶无向完全图是( (n-1)-1)-正则图正则图彼得森图是彼得森图是3- 3-正则图正则图说明说明 n阶阶k- -正则图中，边数正则图中，边数mkn/2/2。当当k为奇数时，为奇数时，n必为偶数。必为偶数。47子图定义定义设设G ，G 为两个图为两个图( (同为无向图同为无向图或同为有向图或同为有向图) )，若，若V V且且E E，则称则称G G 是是G G的的子子图图，G为为G 的的母图母

31、图，记作，记作G G。若若V V或或E E，则称则称G 为为G的的真子图真子图。若若V V，则称则称G 为为G的的生成子图生成子图。 设设G 为一图，为一图，V1 1 V且且V1 1，称以称以V1 1为顶为顶点集，以点集，以G中两个端点都在中两个端点都在V1 1中的边组成边集中的边组成边集E1 1的的图为图为G的的V1 1导出的子图导出的子图，记作，记作G V1 1 。设设E1 1 E且且E1 1，称以称以E1 1为边集，以为边集，以E1 1中边关联的中边关联的顶点为顶点集顶点为顶点集V1 1的图为的图为G的的E1 1导出的子图导出的子图，记作，记作G E1 1 。48在上图中，在上图中，(2

32、)，(3)均为均为(1)的子图；的子图；(3)是生成子图；是生成子图；(5)，(6)均为均为(4)的子图；的子图；(5)是生成子图；是生成子图；49导出子图举例在上图中，设在上图中，设G G为为(1)(1)中图所表示，中图所表示，取取V V1 1a,b,ca,b,c，则则V V1 1的导出子图的导出子图GVGV1 1 为为(2)(2)中图中图所示。所示。取取E E1 1ee1 1,e ,e3 3 ，则则E E1 1的导出子图的导出子图GEGE1 1 为为(3)(3)中图中图所示。所示。50补图定义7.9 设G为n阶无向简单图，以V为顶点集，以所有为边集使G成为完全图Kn的添加边组成的集合的图，称为G的补图，记作G。若图GG，则称为G是自补图。(1)(1)为自补图为自补图(2)(2)和和(3)(3)互为补图互为补图51在下图中，在下图中，(1)是是(2)的补图，