《图的基本概念无向图及有向图》由会员分享，可在线阅读，更多相关《图的基本概念无向图及有向图（61页珍藏版）》请在金锄头文库上搜索。
1、离散数学CH7 图的基本概念1无向无向图及有向图图及有向图1 图论的起源图论的起源图论是组合数学的图论是组合数学的一个分支一个分支, ,它起源它起源于于17361736年欧拉的第年欧拉的第一篇关于图论的论一篇关于图论的论文，这篇论文解决文，这篇论文解决了著名的了著名的 “哥尼哥尼斯堡七桥问题斯堡七桥问题” ，从而使欧拉成为，从而使欧拉成为图论的创始人。图论的创始人。哥尼斯堡七桥问题尼斯堡七桥问题解决方式解决方式莱昂哈德莱昂哈德欧拉欧拉（Leonhard Euler）在）在1735年年圆满地解决了地解决了这一一问题，证明明这种方法并不存在，也种方法并不存在，也顺带解决了解决了一笔画一笔画问题。他
2、在圣彼得堡科学院。他在圣彼得堡科学院发表了表了图论史上第一篇重要文献。欧拉把史上第一篇重要文献。欧拉把实际的抽象的抽象问题简化化为平面上的点与平面上的点与线组合，每一座合，每一座桥视为一条一条线，桥所所连接的地区接的地区视为点。点。这样若从某点出若从某点出发后最后再回到后最后再回到这点，点，则这一点的一点的线数必数必须是偶数。是偶数。 图论的起源欧拉最后欧拉最后给出任意一种河出任意一种河桥图能否全能否全部走一次的部走一次的判定法判定法则。如果通。如果通奇数座奇数座桥的的地方地方不止两个不止两个，那么，那么满足要求的路足要求的路线便不便不存在了。如果只有存在了。如果只有两个地方两个地方通奇数座通
3、奇数座桥，则可从其中任何一地出可从其中任何一地出发找到所要求的路找到所要求的路线。若。若没有一个地方没有一个地方通奇数座通奇数座桥，则从任从任何一地出何一地出发，所求的路，所求的路线都能都能实现，他，他还说明了怎明了怎样快速找到所要求的路快速找到所要求的路线。不少数学家都不少数学家都尝试去解析去解析这个事例。而个事例。而这些解析，最后些解析，最后发展成展成为了数学中的了数学中的图论。5 欧 拉 图定义定义 一个图一个图, ,如果能够从一点出如果能够从一点出发发, ,经过每条边一次且仅一次再经过每条边一次且仅一次再回到起点回到起点, ,则称为则称为欧拉图欧拉图 欧拉在论文中给出并证明了判断欧拉在
4、论文中给出并证明了判断欧拉图的充分必要条件定理欧拉图的充分必要条件定理, ,并证明并证明了七桥图不是欧拉图。了七桥图不是欧拉图。 从这个问题可以看出：图图：图用点代表各个事物图用点代表各个事物, ,用边代表用边代表各个事物间的二元关系。各个事物间的二元关系。 所以，图是研究集合上的二元所以，图是研究集合上的二元关系的工具，是建立数学模型的一关系的工具，是建立数学模型的一个重要手段。个重要手段。 2、一百多年以后 “七桥七桥”问题以后，图论的研究停滞了一问题以后，图论的研究停滞了一百多年，直到百多年，直到18471847年，基尔霍夫用年，基尔霍夫用“树树”图解决了电路理论中的求解联立方程图解决了
5、电路理论中的求解联立方程的问题，十年后凯莱用的问题，十年后凯莱用 “树树” 图计算有图计算有机化学中的问题。在这一时期流行着两机化学中的问题。在这一时期流行着两个著名的图论问题：哈密尔顿回路问题个著名的图论问题：哈密尔顿回路问题和和 “四色猜想四色猜想” 问题。问题。3.哈密尔顿回路问题 18561856年年, ,英国数学家哈密尔顿设计了英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正一个周游世界的游戏，他在一个正十二面体的二十个顶点上标上二十十二面体的二十个顶点上标上二十个著名城市的名字，要求游戏者从个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市一一个城市出发，经过每一个城
6、市一次且仅一次，然后回到出发点。次且仅一次，然后回到出发点。哈密尔顿回路图 此路线称为：此路线称为：哈密尔顿回路哈密尔顿回路， 而此图称为：而此图称为：哈密尔顿图哈密尔顿图。4、“四 色 猜 想” 问 题 人们在长期为地图人们在长期为地图( (平面图平面图) )上色时发上色时发现，最少只要四种颜色，就能使得现，最少只要四种颜色，就能使得有相邻国界的国家涂上不同的颜色有相邻国界的国家涂上不同的颜色 四色猜想的证明一直没有解决，四色猜想的证明一直没有解决，直到一百多年后，在计算机出现以直到一百多年后，在计算机出现以后，于后，于19761976年用计算机算了年用计算机算了12001200多多小时，才
7、证明了四色猜想问题小时，才证明了四色猜想问题。 5、又过了半个世纪 四色猜想问题出现后，图论的研四色猜想问题出现后，图论的研究又停滞了半个世纪，直到究又停滞了半个世纪，直到19201920年年科尼格科尼格写了许多关于图论方面的论写了许多关于图论方面的论文，并于文，并于19361936年发表了第一本关于年发表了第一本关于图论的书。此后图论从理论上到应图论的书。此后图论从理论上到应用上都有了很大发展。特别是计算用上都有了很大发展。特别是计算机的出现使图论得到飞跃的发展。机的出现使图论得到飞跃的发展。 学好图论十分重要 图论是组合数学的一个分支，与其它数学分支图论是组合数学的一个分支，与其它数学分支
8、如群论、矩阵论、集合论、概率论、拓扑学、数如群论、矩阵论、集合论、概率论、拓扑学、数值分析等有着密切的联系值分析等有着密切的联系 。图论给含有二元关系的系统提供了数学模型，图论给含有二元关系的系统提供了数学模型，因而在许多领域里都具有越来越重要的地位，并因而在许多领域里都具有越来越重要的地位，并且在物理、化学、信息学、运筹学等各方面都取且在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。得了丰硕的成果。从二十世际从二十世际50 50 年代以来，由于计算机的迅速发年代以来，由于计算机的迅速发展，有力地推动了图论的发展，使得图论成为数展，有力地推动了图论的发展，使得图论成为数学领域里发展最快
9、的分支之一。学领域里发展最快的分支之一。第第7 7章章 图的概念图的概念本章学习：本章学习：1.1.无向无向图及有向图图及有向图2.2.通路、回路、图的连通性通路、回路、图的连通性3.3.图的矩阵表示图的矩阵表示4.4.最短路径及关键路径最短路径及关键路径 14今日内容无向无向图及有向及有向图图的一些相关概念的一些相关概念度度握手定理握手定理子子图相关概念相关概念图同构同构15预备知识有序有序积: AB= |xAyB有序有序对: 无序无序积: A&B= (x,y) |xAyB无序无序对: (x,y)=(y,x)多重集多重集: a,a,a,b,b,ca,b,c重复度重复度: a的重复度的重复度为
10、3, b的的为2, c的的为1161 1、无序积、无序积：A&BA&B设设A A、B B为两集合，称为两集合，称a,b|aAbBa,b|aAbB为为A A与与B B 的的无无序序积积，记记作作A&BA&B。为方便起见，将无序对为方便起见，将无序对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
11、, a ),( a, b),( b, b) A&A=( a, a ),( a, b),( b, b)172 2、无向图、无向图一一个个无无向向图图G G是是一一个个二二元元组组,即即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,
12、b之之间间连连线线段段表表示示边边(a,b),(a,b),其其中中顶顶点点的的位位置置、连连线线的的曲曲直直及及是否相交都无关紧要。是否相交都无关紧要。18无向图示例无向图示例 给定无向图G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). 3 3、有向图、有向图 一个一个有向图有向图D D是一个二元组是一个二元组, 即即D = ,D = ,其中：其中： . . V V同无向图中的顶点集同无向图中的顶点集; ; . . E E是笛卡儿积的是笛卡儿积的多重子集多重子集, ,其元素称为其元素称
13、为有向边有向边, ,也简称也简称边边. .20有向图示例有向图示例 给定有向图D=，其中 Va,b,c,d，E,。 图的一些概念和规定图的一些概念和规定G表示无向表示无向图，但有，但有时用用G泛指泛指图( (无向的或有向的无向的或有向的) )。D只能表示有向只能表示有向图。V(G)，E(G)分分别表示表示G的的顶点集和点集和边集。集。若若| |V(G)|n，则称称G为n阶图。若若| |V(G)|与与| |E(G)|均均为有限数，有限数，则称称G为有限有限图。 若若边集集E(G)，则称称G为零零图，此，此时，又若，又若G为n阶图，则称称G为n阶零零图，记作作Nn，特特别地，称地，称N1为平凡平凡
14、图 在在图的定的定义中中规定定顶点集点集V为非空集，但在非空集，但在图的运算中的运算中可能可能产生生顶点集点集为空集的运算空集的运算结果，果，为此此规定定顶点集点集为空集的空集的图为空空图，并将，并将空空图记为。 标定图与非标定图、基图将将图的集合定的集合定义转化成化成图形表示之后，形表示之后，常用常用ek表示表示无向无向边( (vi,vj)（或或有向有向边 ），），并称并称顶点或点或边用字母用字母标定的定的图为标定定图，否，否则称称为非非标定定图。将有向将有向图各有向各有向边均改成无向均改成无向边后的无后的无向向图称称为原来原来图的的基基图。易知易知标定定图与非与非标定定图是可以相互是可以相
15、互转化化的，任何无向的，任何无向图G的各的各边均加上箭均加上箭头就就可以得到可以得到以以G为基基图的有向的有向图。 关联与关联次数、环、孤立点设G为无向无向图，ek(vi,vj)E，称称vi,vj为ek的端点，的端点，ek与与vi或或ek与与vj是是彼此相关彼此相关联的。的。若若vivj，则称称ek与与vi或或ek与与vj的的关关联次数次数为1 1。若若vivj，则称称ek与与vi的的关关联次数次数为2 2，并称，并称ek为环。任意的任意的vlV，若若vlvi且且vlvj，则称称ek与与vl的的关关联次数次数为0 0。 关联与关联次数、环、孤立点设D为有向有向图，ekE，称称vi,vj为ek的
16、的端点端点。若若vivj，则称称ek为D中的中的环。无无论在无向在无向图中中还是在有向是在有向图中，无中，无边关关联的的顶点均称点均称为孤立点孤立点。 相邻与邻接设无向无向图G，vi，vjV，ek，elE。若若 etE，使得使得et(vi，vj)，则称称vi与与vj是彼此相是彼此相邻的的若若ek与与el至少有一个公共端点，至少有一个公共端点，则称称ek与与el是彼此是彼此相相邻的的。 设有向有向图D，vi，vjV，ek，elE。若若 etE，使得使得et，则称称vi为et的始点，的始点，vj为et的的终点，并称点，并称vi邻接到接到vj，vj邻接于接于vi。若若ek的的终点点为el的始点，的始
17、点，则称称ek与与el相相邻。例：点边之间的关联次数例：点边之间的关联次数27例：点点、边边之间的相邻关系例：点点、边边之间的相邻关系28顶点的度数定定义 设G为一无向一无向图， vV，称称v作作为边的端点次数之和的端点次数之和为v的度数，的度数，简称称为度，度，记做做 dG(v)。在不在不发生混淆生混淆时，简记为d(v)。设D为有向有向图， vV，称称v作作为边的的始点次数之和始点次数之和为v的的出度出度，记做做d+D(v)，简记作作d+(v)。称称v作作为边的的终点次数之和点次数之和为v的的入度入度，记做做 d -D( (v)，简记作作d-(v)。称称d+(v)+d-(v)为v的度数的度数
18、，记做做d(v)。d(v1)=4d(v2)=4d(v3)=3d(v4)=1d(v5)=030d+(v1)=2d+ (v2)=1d+ (v3)=3d+ (v4)=1d+ (v5)=1d-(v1)=1d- (v2)=3d- (v3)=0d- (v4)=3d- (v5)=1d(v1)=3d (v2)=4d (v3)=3d (v4)=4d (v5)=231最大(出/入)度,最小(出/入)度在无向在无向图G中中，最大度: (G) = max dG(v) | vV(G) 最小度: (G) = min dG(v) | vV(G) 在有向在有向图D中，中，最大出度: +(D) = max dD+(v) | v
19、V(D) 最小出度: +(D) = min dD+(v) | vV(D) 最大入度: -(D) = max dD-(v) | vV(D) 最小入度: -(D) = min dD-(v) | vV(D) 简记为, , +, +, -, -32握手定理（图论基本定理）握手定理（图论基本定理）定理定理7.1 设图G=为无向图或有向图， V=v1,v2,vn,|E|=m，则说明说明任何无向图中，各顶点度数之和等于边数的两倍。证明证明G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。 推推论：任何图中，度为奇数的顶点个数为偶数。 33问题研究
20、问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。说明：明：(1)很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的关系。握手定理握手定理定理7.2 设有向图D=， V=v1,v2,vn,|E|=m，则 35度数列设G为一个一个n阶无向无向图，Vv1,v2,vn，称称d(v1)，d(v2)，d(vn)为G的的度数列度数列。对于于顶点点标
21、定定的无向的无向图，它的度数列是唯一的。，它的度数列是唯一的。反之，反之，对于于给定的非定的非负整数列整数列dd1,d2,dn，若存在若存在Vv1,v2,vn为顶点集的点集的n阶无向无向图G，使得使得d(vi)di，则称称d是是可可图化化的。的。特特别地，若所得地，若所得图是是简单图，则称称d是是可可简单图化化的。的。类似地，似地，设D为一个一个n阶有向有向图，Vv1,v2,vn，称称d(v1)，d(v2)，d(vn)为D的度数列，的度数列，另外称另外称d+(v1)，d+(v2)，d+(vn)与与d-(v1)，d-(v2)，d-(vn)分分别为D的的出度列出度列和和入度列入度列。度数列举例按顶
22、点的标定顺序，度数列为 4,4,2,1,3。度数列举例按字母顺序，度数列：5,3,3,3出度列：4,0,2,1入度列：1,3,1,2 (4，4，3，1，0) (3，4，3，4，2)练习：39可图化的充要条件定理设非负整数列d(d1，d2，dn)，则d是可图化的当且仅当证明 必要性。由握手定理显然得证。充分性。由已知条件可知，d中有偶数个奇数度点。奇数度点两两之间连一边，剩余度用环来实现。5331例例7.17.1：1.1.(3, 3, 2, 3), (5, 2, 3, 1, 4)(3, 3, 2, 3), (5, 2, 3, 1, 4)能成为图的度能成为图的度数序列吗？为什么？数序列吗？为什么？
23、 2.2.已知图已知图G G中有中有1010条边，条边，4 4个个3 3度顶点，其余顶点的度顶点，其余顶点的度数均小于等于度数均小于等于2 2，问，问G G中至少有多少个顶点？为中至少有多少个顶点？为什么？什么？解：解：1.1.由于这两个序列中，奇数度顶点个数均为奇数，由于这两个序列中，奇数度顶点个数均为奇数，由握手定理的推论可知，它们都不能成为图的度由握手定理的推论可知，它们都不能成为图的度数序列。数序列。2.2.显然，显然，图图G中的其余顶点度数均为中的其余顶点度数均为2时时G图的顶点图的顶点数最少数最少.设设G图至少有图至少有x个顶点个顶点.由握手定理可知，由握手定理可知，34+2(x-
24、4)=210解得解得:x=8所以所以G至少有至少有8个顶点。个顶点。41简单图与多重图定定义 在在无向无向图中，关中，关联一一对顶点的无向点的无向边如果多于如果多于1 1条，条，则称称这些些边为平行平行边，平行，平行边的条数称的条数称为重数重数。在在有向有向图中，关中，关联一一对顶点的有向点的有向边如果多于如果多于1 1条，条，并且并且这些些边的始点和的始点和终点相同点相同( (也就是它也就是它们的方向相的方向相同同) )，则称称这些些边为平行平行边。含平行含平行边的的图称称为多重多重图。既不含平行既不含平行边也不含也不含环的的图称称为简单图。43简单图与多重图示例完全图定定义7. .7 设G
25、为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全完全图，记做Kn(n1)。 设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D是n阶有向完全有向完全图。设D为n阶有向简单图，若D的基图为n阶无向完全图Kn，则称D是n阶竞赛图。完全图举例n阶无向完全无向完全图的的边数数为：n(n-1)/2n阶有向完全有向完全图的的边数数为：n(n-1)n阶竞赛图的的边数数为：n(n-1)/2K53阶有向完全图4阶竞赛图正则图定定义设G为n阶无向无向简单图，若，若vV(G)，均有均有d(v)k，则称称G为k-正正则图。
26、 举例例 n阶零零图是是0-0-正正则图n阶无向完全无向完全图是是( (n-1)-正正则图彼得森彼得森图是是3-3-正正则图说明明 n阶k-正正则图中，中，边数数mkn/2。当当k为奇数奇数时，n必必为偶数。偶数。子图定定义设G，G 为两个两个图( (同同为无向无向图或同或同为有向有向图) )，若，若V V且且E E，则称称G 是是G的的子子图，G为G 的的母母图，记作作G G。若若V V或或E E，则称称G 为G的的真子真子图。若若V V，则称称G 为G的的生成子生成子图。 设G为一一图，V1 V且且V1，称以称以V1为顶点点集，以集，以G中两个端点都在中两个端点都在V1中的中的边组成成边集
27、集E1的的图为G的的V1导出的子出的子图，记作作GV1。设E1 E且且E1，称以称以E1为边集，以集，以E1中中边关关联的的顶点点为顶点集点集V1的的图为G的的E1导出的子出的子图，记作作GE1。在上图中，在上图中，(2)，(3)均为均为(1)的子图；的子图；(3)是生成子图；是生成子图；(5)，(6)均为均为(4)的子图；的子图；(5)是生成子图；是生成子图；48导出子图举例在上在上图中，中，设G为(1)(1)中中图所表示，所表示，取取V1a,b,c，则V1的的导出子出子图GV1为(2)(2)中中图所示。所示。取取E1e1,e3，则E1的的导出子出子图GE1为(3)(3)中中图所示。所示。补
28、图定义7.9设G为n阶无向简单图，以V为顶点集，以所有为边集使G成为完全图Kn的添加边组成的集合的图，称为G的补图，记作G。若图GG，则称为G是自补图。(1)(1)为自补图为自补图(2)(2)和和(3)(3)互为补图互为补图在下图中，在下图中，(1)是是(2)的补图，当然的补图，当然(2)也是也是(1)的的补图，就是说，补图，就是说，(1)，(2)互为补图。同样，互为补图。同样，(3)，(4)互为补图。互为补图。51图的同构图的同构在在图论的的研研究究中中，我我们更更关关心心的的是是图的的结构构,而而这种种结构构与与顶点点与与边的的具具体体元元素素或或与与图的的图形的画法无关形的画法无关.对此
29、此,我我们引引进同构同构的概念的概念. .52图同构(graph isomorphism)定义7.10: 设两个无向（有向）图G1=,G2=, 若存在双射f:V1V2, 满足 uV1,vV1, e=(u,v)E1 e=(f(u),f(v)E2 (e=E1 e=E2 )并且e与e的重数相同， 则称G1与G2同构, 记作G1G2说明: 同构的图,其图论性质完全一样53图的同构图的同构5455(1) (2)(3) (4)(5)和和(6)不同构不同构,因为在因为在(6)中有三个彼此不邻接的顶点中有三个彼此不邻接的顶点,而在而在(5)找不到三个彼此不邻接的顶点找不到三个彼此不邻接的顶点.图同构课例图同构
30、课例:56判断两个图同构的必要条件是判断两个图同构的必要条件是:(1)顶点数相同顶点数相同;(2)边数相同边数相同;(3)对应顶点的度数也相同对应顶点的度数也相同.57例7.2(1)画出4阶3条边的所有非同构的无向简单图。由握手定理可知，所画的无向简单图各顶点度数之和为236，最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数的个数为偶数。将这样的整数列排出来只有下面三种情况：(1) 2，2，1，1(2) 3，1，1，1(3) 2，2，2，0 将每种度数列所有非同构的图都画出来即得所要求的全部非同构的图。 对于给定的正整数n和m(mn(n-1)/2)，构造出所有非同构的n阶m条边的所有非同构的无向(有向)简单图，这是目前还没有解决的难题。 (2)(2)画出画出3 3阶2 2条条边的所有非同构的有向的所有非同构的有向简单图由握手定理可知，所画有向简单图各顶点度数之和为4，最大出度和最大入度均小于或等于2。度数列及入度出度列为1,2,1入度列为 0,1,1 或 0,2,0 或 1,0,1出度列为 1,1,0 或 1,0,1 或 0,2,02,2,0入度列为 1,1,0出度列为 1,1,0作业P173 7.6 7.7 7.860Q & A61
