图的基本概念 无向图及有向图

离散数学,CH7图的基本概念1无向图及有向图,1,图论的起源,图论是组合数学的一个分支,它起源于1736年欧拉的第一篇关于图论的论文，这篇论文解决了著名的“哥尼斯堡七桥问题”，从而使欧拉成为图论的创始人。,1.哥尼斯堡七桥问题,哥尼斯堡位于前苏联的加里宁格勒，历史上曾经是德国东普鲁士省的省会，普雷格尔河横穿城堡，河中有两个小岛，共有七座桥连接两岸和小岛。问题：在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？,哥尼斯堡七桥问题解决方式,莱昂哈德欧拉（LeonhardEuler）在1735年圆满地解决了这一问题，证明这种方法并不存在，也顺带解决了一笔画问题。他在圣彼得堡科学院发表了图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数。,图论的起源,欧拉最后给出任意一种河桥图能否全部走一次的判定法则。如果通奇数座桥的地方不止两个，那么满足要求的路线便不存在了。如果只有两个地方通奇数座桥，则可从其中任何一地出发找到所要求的路线。若没有一个地方通奇数座桥，则从任何一地出发，所求的路线都能实现，他还说明了怎样快速找到所要求的路线。不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的图论。,5,欧拉图,定义一个图,如果能够从一点出发,经过每条边一次且仅一次再回到起点,则称为欧拉图欧拉在论文中给出并证明了判断欧拉图的充分必要条件定理,并证明了七桥图不是欧拉图。,从这个问题可以看出：,图：图用点代表各个事物,用边代表各个事物间的二元关系。所以，图是研究集合上的二元关系的工具，是建立数学模型的一个重要手段。,2、一百多年以后,“七桥”问题以后，图论的研究停滞了一百多年，直到1847年，基尔霍夫用“树”图解决了电路理论中的求解联立方程的问题，十年后凯莱用“树”图计算有机化学中的问题。在这一时期流行着两个著名的图论问题：哈密尔顿回路问题和“四色猜想”问题。,3.哈密尔顿回路问题,1856年,英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正十二面体的二十个顶点上标上二十个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市一次且仅一次，然后回到出发点。,哈密尔顿回路图,此路线称为：哈密尔顿回路，而此图称为：哈密尔顿图。,4、“四色猜想”问题,人们在长期为地图(平面图)上色时发现，最少只要四种颜色，就能使得有相邻国界的国家涂上不同的颜色四色猜想的证明一直没有解决，直到一百多年后，在计算机出现以后，于1976年用计算机算了1200多小时，才证明了四色猜想问题。,5、又过了半个世纪,四色猜想问题出现后，图论的研究又停滞了半个世纪，直到1920年科尼格写了许多关于图论方面的论文，并于1936年发表了第一本关于图论的书。此后图论从理论上到应用上都有了很大发展。特别是计算机的出现使图论得到飞跃的发展。,学好图论十分重要,图论是组合数学的一个分支，与其它数学分支如群论、矩阵论、集合论、概率论、拓扑学、数值分析等有着密切的联系。图论给含有二元关系的系统提供了数学模型，因而在许多领域里都具有越来越重要的地位，并且在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。从二十世际50年代以来，由于计算机的迅速发展，有力地推动了图论的发展，使得图论成为数学领域里发展最快的分支之一。,第7章图的概念本章学习：1.无向图及有向图2.通路、回路、图的连通性3.图的矩阵表示4.最短路径及关键路径,14,今日内容,无向图及有向图图的一些相关概念度握手定理子图相关概念图同构,15,预备知识,有序积:AB=|xAyB有序对:无序积:A.E是无序积V.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)=4d(v2)=4d(v3)=3d(v4)=1d(v5)=0,30,d+(v1)=2d+(v2)=1d+(v3)=3d+(v4)=1d+(v5)=1,d-(v1)=1d-(v2)=3d-(v3)=0d-(v4)=3d-(v5)=1,d(v1)=3d(v2)=4d(v3)=3d(v4)=4d(v5)=2,31,最大(出/入)度,最小(出/入)度,在无向图G中，最大度:(G)=maxdG(v)|vV(G)最小度:(G)=mindG(v)|vV(G)在有向图D中，最大出度:+(D)=maxdD+(v)|vV(D)最小出度:+(D)=mindD+(v)|vV(D)最大入度:-(D)=maxdD-(v)|vV(D)最小入度:-(D)=mindD-(v)|vV(D)简记为,+,+,-,-,32,握手定理（图论基本定理）,定理7.1设图G=为无向图或有向图，V=v1,v2,vn,|E|=m，则说明任何无向图中，各顶点度数之和等于边数的两倍。证明G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。推论：任何图中，度为奇数的顶点个数为偶数。,33,问题研究,问题：在一个部门的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的度数列。对于顶点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列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是可图化的当且仅当,证明必要性。由握手定理显然得证。充分性。由已知条件可知，d中有偶数个奇数度点。奇数度点两两之间连一边，剩余度用环来实现。,例7.1：(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？为什么？解：1.由于这两个序列中，奇数度顶点个数均为奇数，由握手定理的推论可知，它们都不能成为图的度数序列。2.显然，图G中的其余顶点度数均为2时G图的顶点数最少.设G图至少有x个顶点.由握手定理可知，34+2(x-4)=210解得: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)/2,K5,3阶有向完全图,4阶竞赛图,正则图,定义设G为n阶无向简单图，若vV(G)，均有d(v)k，则称G为k-正则图。举例n阶零图是0-正则图n阶无向完全图是(n-1)-正则图彼得森图是3-正则图说明n阶k-正则图中，边数mkn/2。当k为奇数时，n必为偶数。,子图,定义设G，G为两个图(同为无向图或同为有向图)，若VV且EE，则称G是G的子图，G为G的母图，记作GG。若VV或EE，则称G为G的真子图。若VV，则称G为G的生成子图。设G为一图，V1V且V1，称以V1为顶点集，以G中两个端点都在V1中的边组成边集E1的图为G的V1导出的子图，记作GV1。设E1E且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)为自补图(2)和(3)互为补图,在下图中，(1)是(2)的补图，当然(2)也是(1)的补图，就是说，(1)，(2)互为补图。同样，(3)，(4)互为补图。,51,图的同构,在图论的研究中，我们更关心的是图的结构,而这种结构与顶点与边的具体元素或与图的图形的画法无关.对此,我们引进同构的概念.,52,图同构(graphisomorphism),定义7.10:设两个无向（有向）图G1=,G2=,若存在双射f:V1V2,满足uV1,vV1,e=(u,v)E1e=(f(u),f(v)E2(e=E1e=E2)并且e与e的重数相同，则称G1与G2同构,记作G1G2说明:同构的图,其图论性质完全一样,53,图的同构,54,55,(2)(3)(4)(5)和(6)不同构,因为在(6)中有三个彼此不邻接的顶点,而在(5)找不到三个彼此不邻接的顶点.,图同构课例:,56,判断两个图同构的必要条件是:顶点数相同;边数相同;对应顶点的度数也相同.,57,例7.2,(1)画出4阶3条边的所有非同构的无向简单图。由握手定理可知，所画的无向简单图各顶点度数之和为236，最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数的个数为偶数。将这样的整数列排出来只有下面三种情况：,(1)2，2，1，1(2)3，1