图的基本概念-无向图及有向图ppt课件.ppt

离散数学CH7 图的基本概念1无向无向图及有向图图及有向图1 图论的起源图论的起源图论是组合数学的图论是组合数学的一个分支一个分支, ,它起源它起源于于17361736年欧拉的第年欧拉的第一篇关于图论的论一篇关于图论的论文，这篇论文解决文，这篇论文解决了著名的了著名的 “哥尼哥尼斯堡七桥问题斯堡七桥问题” ，从而使欧拉成为，从而使欧拉成为图论的创始人。图论的创始人。1.哥尼斯堡七桥问题 哥尼斯堡哥尼斯堡位于前苏联的加里位于前苏联的加里宁格勒，历史上曾经是德国宁格勒，历史上曾经是德国东普鲁士省的省会，普雷格东普鲁士省的省会，普雷格尔河横穿城堡，河中有尔河横穿城堡，河中有两个两个小岛小岛，共有，共有七座桥七座桥连接两岸连接两岸和小岛。和小岛。 问题：问题： 在所有桥都只能走一在所有桥都只能走一遍的前提下，如何才能把这遍的前提下，如何才能把这个地方所有的桥都走遍？个地方所有的桥都走遍？哥尼斯堡七桥问题尼斯堡七桥问题解决方式解决方式莱昂哈德莱昂哈德欧拉欧拉（Leonhard Euler）在）在1735年圆满年圆满地解决了这一问题，证明这种方法并不存在，也顺带地解决了这一问题，证明这种方法并不存在，也顺带解决了解决了一笔画问题一笔画问题。他在圣彼得堡科学院发表了图论。他在圣彼得堡科学院发表了图论史上第一篇重要文献。欧拉把实际的抽象问题简化为史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数。点，则这一点的线数必须是偶数。 图论的起源欧拉最后给出任意一种河欧拉最后给出任意一种河桥图能否全部桥图能否全部走一次的走一次的判定法则判定法则。如果通。如果通奇数座奇数座桥的地桥的地方方不止两个不止两个，那么满足要求的路线便不存，那么满足要求的路线便不存在了。如果只有在了。如果只有两个地方两个地方通奇数座桥，则通奇数座桥，则可从其中任何一地出发找到所要求的路线可从其中任何一地出发找到所要求的路线。若。若没有一个地方没有一个地方通奇数座桥，则从任何通奇数座桥，则从任何一地出发，所求的路线都能实现，他还说一地出发，所求的路线都能实现，他还说明了怎样快速找到所要求的路线。明了怎样快速找到所要求的路线。不少数学家都尝试去解析这个事例。而这不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的些解析，最后发展成为了数学中的图论图论。5 欧 拉 图定义定义 一个图一个图, ,如果能够从一点出如果能够从一点出发发, ,经过每条边一次且仅一次再经过每条边一次且仅一次再回到起点回到起点, ,则称为则称为欧拉图欧拉图 欧拉在论文中给出并证明了判欧拉在论文中给出并证明了判断欧拉图的充分必要条件定理断欧拉图的充分必要条件定理, ,并证并证明了七桥图不是欧拉图。明了七桥图不是欧拉图。 从这个问题可以看出：图图：图用点代表各个事物图用点代表各个事物, ,用边代用边代表各个事物间的二元关系。表各个事物间的二元关系。 所以，图是研究集合上的二元所以，图是研究集合上的二元关系的工具，是建立数学模型的一关系的工具，是建立数学模型的一个重要手段。个重要手段。 2、一百多年以后 “七桥七桥”问题以后，图论的研究停滞了一问题以后，图论的研究停滞了一百多年，直到百多年，直到18471847年，基尔霍夫用年，基尔霍夫用“树树”图解决了电路理论中的求解联立方程图解决了电路理论中的求解联立方程的问题，十年后凯莱用的问题，十年后凯莱用 “树树” 图计算有图计算有机化学中的问题。在这一时期流行着两机化学中的问题。在这一时期流行着两个著名的图论问题：哈密尔顿回路问题个著名的图论问题：哈密尔顿回路问题和和 “四色猜想四色猜想” 问题。问题。3.哈密尔顿回路问题 18561856年年, ,英国数学家哈密尔顿设计了英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正一个周游世界的游戏，他在一个正十二面体的二十个顶点上标上二十十二面体的二十个顶点上标上二十个著名城市的名字，要求游戏者从个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市一一个城市出发，经过每一个城市一次且仅一次，然后回到出发点。次且仅一次，然后回到出发点。哈密尔顿回路图 此路线称为：此路线称为：哈密尔顿回路哈密尔顿回路， 而此图称为：而此图称为：哈密尔顿图哈密尔顿图。4、“四 色 猜 想” 问 题 人们在长期为地图人们在长期为地图( (平面图平面图) )上色时发上色时发现，最少只要四种颜色，就能使得现，最少只要四种颜色，就能使得有相邻国界的国家涂上不同的颜色有相邻国界的国家涂上不同的颜色 四色猜想的证明一直没有解决，四色猜想的证明一直没有解决，直到一百多年后，在计算机出现以直到一百多年后，在计算机出现以后，于后，于19761976年用计算机算了年用计算机算了12001200多多小时，才证明了四色猜想问题小时，才证明了四色猜想问题。 5、又过了半个世纪 四色猜想问题出现后，图论的研四色猜想问题出现后，图论的研究又停滞了半个世纪，直到究又停滞了半个世纪，直到19201920年年科尼格科尼格写了许多关于图论方面的论写了许多关于图论方面的论文，并于文，并于19361936年发表了第一本关于年发表了第一本关于图论的书。此后图论从理论上到应图论的书。此后图论从理论上到应用上都有了很大发展。特别是计算用上都有了很大发展。特别是计算机的出现使图论得到飞跃的发展。机的出现使图论得到飞跃的发展。 学好图论十分重要 图论是组合数学的一个分支，与其它数学分支图论是组合数学的一个分支，与其它数学分支如群论、矩阵论、集合论、概率论、拓扑学、数如群论、矩阵论、集合论、概率论、拓扑学、数值分析等有着密切的联系值分析等有着密切的联系 。 图论给含有二元关系的系统提供了数学模型，因图论给含有二元关系的系统提供了数学模型，因而在许多领域里都具有越来越重要的地位，并且而在许多领域里都具有越来越重要的地位，并且在物理、化学、信息学、运筹学等各方面都取得在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。了丰硕的成果。 从二十世际从二十世际50 50 年代以来，由于计算机的迅速发年代以来，由于计算机的迅速发展，有力地推动了图论的发展，使得图论成为数展，有力地推动了图论的发展，使得图论成为数学领域里发展最快的分支之一。学领域里发展最快的分支之一。第第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的重复度为的重复度为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, 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,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是笛卡儿积的是笛卡儿积的多重子集多重子集, ,其元素称为其元素称为有向边有向边, ,也简称也简称边边. .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为为平凡图平凡图 在图的定义中规定顶点集在图的定义中规定顶点集V为非空集，但在图的运算中为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空集的图为空图空图，并将，并将空图记为空图记为。 标定图与非标定图、基图 将图的集合定义转化成图形表示之后，将图的集合定义转化成图形表示之后，常用常用ek表示表示无向边无向边(vi,vj)（或或有向边有向边），），并称顶点或边用字母标定的并称顶点或边用字母标定的图为图为标定图标定图，否则称为，否则称为非标定图非标定图。将有向图各有向边均改成无向边后的无将有向图各有向边均改成无向边后的无向图称为原来图的向图称为原来图的基图基图。易知标定图与非标定图是可以相互转化易知标定图与非标定图是可以相互转化的，任何无向图的，任何无向图G的各边均加上箭头就的各边均加上箭头就可以得到可以得到以以G为基图的有向图为基图的有向图。 关联与关联次数、环、孤立点 设设G为无向图，为无向图，ek(vi,vj)E，称称vi,vj为为ek的端点，的端点，ek与与vi或或ek与与vj是是彼此相关联彼此相关联的。的。若若vivj，则称则称ek与与vi或或ek与与vj的的关联次数关联次数为为1。若若vivj，则称则称ek与与vi的的关联次数为关联次数为2，并称，并称ek为为环环。任意的任意的vlV，若若vlvi且且vlvj，则称则称ek与与vl的的关联关联次数为次数为0。 关联与关联次数、环、孤立点 设设D为有向图，为有向图，ekE，称称vi,vj为为ek的的端点端点。若若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的始点，则称的始点，则称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的度数的度数，记做，记做d(v)。d (v1)=4 d(v2)=4 d(v3)=3 d(v4)=1 d(v5)=0 30d+(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 31最大(出/入)度,最小(出/入)度在无向图在无向图G中中，最大度: (G) = max dG(v) | vV(G) 最小度: (G) = min dG(v) | vV(G) 在有向图在有向图D中，中，最大出度: +(D) = max dD+(v) | vV(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度。 推论：推论：任何图中，度为奇数的顶点个数为偶数。 12niid vm33问题研究问题：问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。说明：说明：(1)很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的关系。握手定理握手定理定理7.2 设有向图D=，V = v1, v2, vn,|E|=m，则 11nniiiidvdvm35度数列设设G为一个为一个n阶无向图，阶无向图，Vv1,v2,vn，称称d(v1)，d(v2)，d(vn)为为G的的度数列度数列。对于对于顶点标定顶点标定的无向图，它的度数列是唯一的。的无向图，它的度数列是唯一的。反之，对于给定的非负整数列反之，对于给定的非负整数列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的的出度列出度列和和入度列入度列。度数列举例按顶点的标定顺序，度数列为 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是可图化的当且仅当 n n1)2(mod0iid证明 必要性。由握手定理显然得证。充分性。由已知条件可知，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)能成为图的度能成为图的度数序列吗？为什么？数序列吗？为什么？ 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-4)=2 10 解得解得: x=8 所以所以G至少有至少有8个顶点。个顶点。41简单图与多重图 定义定义 在在无向图无向图中，关联一对顶点的无向边如果多于中，关联一对顶点的无向边如果多于1条条，则称这些边为，则称这些边为平行边平行边，平行边的条数称为，平行边的条数称为重数重数。在在有向图有向图中，关联一对顶点的有向边如果多于中，关联一对顶点的有向边如果多于1条，条，并且这些边的始点和终点相同并且这些边的始点和终点相同(也就是它们的方向相也就是它们的方向相同同)，则称这些边为，则称这些边为平行边平行边。含平行边的图称为含平行边的图称为多重图多重图。既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图。43简单图与多重图示例 完全图定义定义7.7 设G为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-正则图正则图。 举例举例 n阶零图是阶零图是0-正则图正则图n阶无向完全图是阶无向完全图是(n-1)-正则图正则图彼得森图是彼得森图是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中的边组成边集中的边组成边集E1的图的图为为G的的V1导出的子图导出的子图，记作，记作GV1。设设E1 E且且E1，称以称以E1为边集，以为边集，以E1中边关联的中边关联的顶点为顶点集顶点为顶点集V1的图为的图为G的的E1导出的子图导出的子图，记作，记作GE1。在上图中，在上图中，(2)，(3)均为均为(1)的子图；的子图；(3)是生成子图；是生成子图；(5)，(6)均为均为(4)的子图；的子图；(5)是生成子图；是生成子图；48导出子图举例在上图中，设在上图中，设G为为(1)中图所表示，中图所表示，取取V1a,b,c，则则V1的导出子图的导出子图GV1为为(2)中中图所示。图所示。取取E1e1,e3，则则E1的导出子图的导出子图GE1为为(3)中中图所示。图所示。补图定义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图的同构图的同构在图论的研究中，我们更关心的是图的结构在图论的研究中，我们更关心的是图的结构, 而而这种结构与顶点与边的具体元素或与图的图形这种结构与顶点与边的具体元素或与图的图形的画法无关的画法无关. 对此对此, 我们引进我们引进同构同构的概念的概念.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)找找不到三个彼此不邻接的顶点不到三个彼此不邻接的顶点.图同构课例图同构课例: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) 画出画出3阶阶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 & AQ & A61