第十四部分图的基本概念.ppt
第十四章 图的基本概念,第四部分：图论,七桥问题,问题 寻找走遍哥尼斯堡（KÖnigsberg）城的7座桥，且只许走过每座桥一次，最后又回到原出发点 求解 1736年瑞士大数学家欧拉（LeonhardEuler）发表了关于“哥尼斯堡七桥问题”的论文（图论的第一篇论文）。他指出从一点出发不重复的走遍七桥，最后又回到原来出发点是不可能的。,图论,图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究，如1736年欧拉（L.Euler)所解决的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题,棋盘上马的行走路线问题,在中国象棋中，马走“日”字，即每步从 1×2 矩形的一个顶点跳到相对的顶点。如图，马从M（3，2）一次只能跳到A、B、C、D、E、F、G、H中的任何一个位置。 问题：马能否从棋盘上任意一点出发，不重复、不遗漏地走遍整个棋盘（即每一点都走到并且只到一次）？,棋盘上马的行走路线问题,将马目前所在位置涂成白色，用涂色的方法，将棋盘上的点分为黑、白相间的两类,环游世界各国的问题,英国数学家哈密顿于1859年以游戏的形式提出：把一个正十二面体的二十个顶点看成二十个城市，要求找出一条经过每个城市恰好一次而回到出发点的路线。这条路线就称“哈密顿圈”。一百多年来，对哈密顿问题的研究，促进了图论的发展。,四色猜想,问题：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色 用数学语言表示，即：“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字”,图论,图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的作用,第十四章 图的基本概念,第一节：图 第二节：通路、回路、图的连通性 第三节：图的矩阵表示和运算,第一节：图,无序积：设A，B为任意的两个集合，称 a,b | aA且bB 为A与B的无序积，记做A&B 无向图：一个无向图G是一个二重组, 其中V(G)为有限非空结点（或叫顶点）集合, E(G)是边的集合，它是无序积V&V的多重子集，其元素为无向边，简称边。 有向图：一个有向图G是一个二重组, 其中V(G)为有限非空结点（或叫顶点）集合, E(G)是边的集合，它是笛卡儿乘积V×V的多重子集，其元素为有向边，简称边。,下面定义一些专门名词： （）通常用G表示无向图，D表示有向图，但G也可以泛指图。V(G)，E(G)分别表示G的顶点集和边集。|V(G)|,|E(G)|分别表示G的顶点数和边数， 若|V(G)|n，则称G为n阶图。 （）若|V(G)|,|E(G)|均为有限数，则称G为有限图。 （）若图G中，边集为空，则称之为零图， 若G为n阶图，则称之为n阶零图，记为Nn， N1称为平凡图。 （4）顶点集为空的图记为空图。,第一节：图,一些定义,（5）称顶点或边用字母标定的图为标定图，否则成为非标定图。另外，将有向边改为无向边后的图称为原图的基图。 （6）设G=为无向图，ek=(vi,vj)E,则称vi,vj为ek的端点， ek与vi或ek与vj是彼此关联的。 若vivj，则称ek与vi或ek与vj的关联次数为1， 若vi=vj，则称ek与vi的关联次数为2，并称为环。任意的vlV，若vlvi且vlvj，则称ek与vl的关联次数为0。,一些定义,（7）设无向图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相邻。,一些定义,（8）设无向图G=，对所有的vV称 为v的邻域，记为NG(v)， 并称NG(v) v为v的闭邻域，记为 。 称 为v的关联集，记为IG(v) 。 设有向图G=，对所有的vV ，称 为v的后继元素。称 为v的先驱元素。称两者之并为v的邻域，记为ND(v) 。 称ND(v) v，v的闭邻域。,一些定义,定义14.3 在无向图中，关联一对顶点的无向边如果多于一条，则称这些边为平行边，平行边的条数称为重数。 在有向图中，关联一对顶点的有向边如果多于一条，并且这些边的始点和终点相同，则称这些边为平行边。 含平行边的图称为多重图，即不含平行边也不含环的图称为简单图。,一些定义,非多重图称为线图。 由定义可见，简单图是没有环和平行边的图。,一些定义,定义14.4：在无向图中，任意点其作为边的端点次数之和称为该点的度数，记为dG(v). 在有向图中，对于任何结点v，以v为始点的边的条数，称为结点v的引出次数(或出度)，记作d+(v)；以v点为终点的边的条数称为v的引入次数(或入度)，记作d(v)；结点的v的引入次数和引出次数之和称为v的次数（度数），用d (v)表示。 由定义可见:度数d (v)d+(v)d(v)。 定义：最大度，最小度，最大出度，最大入度，最小入度，最小出度，悬挂点，悬挂边,例 1,例： d (a)(引入)+(引出)=5 d（b） d（c） d（1） d（2） d（3）,以后为了叙述方便，我们将具有n个结点和m条边的图简称为（n,m）图,握手定理,定理14.1（握手定理）：设G是（n, m）无向图，它的顶点集合v1,v2,vn，于是有,证明：在无向图中引入一条边，总的次数增， 若有m条边，则总次数为2m。 （此定理也可推广到有向图和混合图） 定理14.1 在有向图中，则为：,例 2,d（a）， d（b）， d（c）， d（d）, m，2md d + ,例 3,例：若图有n个顶点,（n+1）条边，则中至少有一个顶点的度数。 证明：设中有n个结点分别为v1,v2,vn，则由握手定理： d（vi）（n+1） 而顶点的平均度数为： d（vi）(n+1)/n=2+1/n2 顶点中至少有一个顶点的度数,握手定理的推论,推论：在图中，度数为奇数的顶点必定有偶数个。 证明：设度数为偶数的顶点有n1个,记为vei(i=1,2,n1),度数为奇数的顶点有n2个，记为voi(i=1,2,n2)。由上一定理得 因为度数为偶数的各顶点次数之和为偶数。所以前一项度数为偶数；若n2为奇数，则第二项为奇数，两项之和将为奇数，但这与上式矛盾。故n2必为偶数。 问题：是否在一个部门的25个人中间，由于意见不同，每个人恰好与5个人意见一致？,可图化、可简单图化,设G=为一个n阶无向图，Vv1,v2,vn，称d(v1),d(v2)d(vn) 为G的度数列。对于顶点标定的无向图，它的度数列是唯一的。 反之，对于给定的非负整数列d=(d1,d2,dn),若存在以Vv1,v2,vn为顶点集的n阶无向图G，使得d(vi)=di，则称d是可图化的。 特别的，如果所得图是简单图，则称d是可简单图化的。,可图化的判断定理,定理14.3 设非负整数列d=(d1,d2,dn), 则d是可图化的当且仅当 证明：必要性显然 充分性：构造性证明 定理14.4 设G为任意n阶无向简单图，则(G) n-1,可图化,例：判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？ (5,5,4,4,2,1) (5,4,3,2,2) (3,3,3,1) (d1,d2,dn), d1d2dn1, 且 为偶数 (4,4,3,3,2,2),同构的定义,定义14.5：设，和，是两个图，若存在从到一双射函数：，使得对任意的a,bV,a,b E当且仅当g(a),g(b) ，并且a,b和g(a),g(b)有相同的重数，则称和同构。 讨论定义： （1）和是同构的,它们的顶点必须是一一对应的； （2）且对无向图而言，还要保持顶点之间的邻接关系和边的重数； （3）且对有向图而言，不但要保持顶点之间的邻接关系，而且还应保持边的方向和边的重数。 图的同构关系可以看作是全体图集合上的二元关系，并且此关系是等价关系。,例4,例： 存在一双射函数:1,2,3,4a3,a4,a2,a1， 其中：顶点的一一对应： g(1)= a3; g(2)= a4; g(3)= a2; g(4)= a1; 边的一一对应： g; g; g; g,例 5,例:下面给出二个无向图，试求出同构函数,：1,2,3,4,5,6 a1,a2,a3,a4,a5,a6 边的对应为： g(i,j)(g(i),g(j)ai,aj,同构的性质,两图同构的必要条件： （1）顶点数相等； （2）边数相等； （3）度数相同的顶点数相等。 但这不是充分条件。如下图,完全图,定义14.6：在个顶点的有向图G=中，如果每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称G为有向完全图；在个顶点的无向图G=中，每二个顶点之间均有一条边连接，则称G为无向完全图。,特殊图,定义14.7：所有顶点均具有同样度数的简单无向图为正则图，各顶点的度数均为k时称为k正则图。,子图的定义,定义14.8:设=,=是二个图， (a)若，则称是的子图； (b)若，并且，则称是的真子图； (c)若，,则称是的生成子图（支撑子图）。 (d)若子图G中没有孤立顶点，G由E唯一确定，则称G为由边集E导出的子图。 (e)若在子图G中，对中的任意二顶点u,v，当u,vE时有u,vE，则G由唯一确定，此时称G为由顶点集导出的子图。,例 6,例：图如下 的真子图 生成子图：,E=,导出的子图,由V=a,b,d,e导出的子图,例 7,例 画出4阶3边的所有非同构的无向简单图。 解：由握手定理可知，该无向简单图各顶点度数之和为6，最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负数，每个整数均大于等于0且小于等于3，并且奇数的个数为偶数。有三种情况 3，1，1，1； 2，2，1，1； 2，2，2，0 将每种度数列所有非同构的图都画出来即可得所要求的全部非同构图。,补图,定义14.9:设无向简单图G= 有n个顶点，无向简单图H= 也有同样的顶点，而E是由n个顶点的完全图的边删去E所得，则图H称为图G的补图。 自补图：H与G同构,例 8,例：试画出5个顶点三条边和5个顶点七条边的简单无向图。 解： 5个顶点三条边的图,5个顶点七条边的图（为5顶点三条边的补图）,图的操作,关于图的四种操作： （1）删去中的一条边e； （2）删去中的一个顶点（即是删去顶点和与有关联的所有边）。 （3）设边e=(u,v)E，用Ge表示从G中删除e后，将e的两个端点u,v用一个新的顶点w代替，使w关联e以外u,v关联的所有边，称为e的收缩。 （4）设u,vV，用G(u,v)表示在u,v之间加一条边(u,v)，称为新加边。,第十四章 图的基本概念,第二节：通路、回路、图的连通性,14.2 通路和回路,定义14.11: 在有向图中，从某一顶点出发经过某些点边交替序列到达终点，此序列称为通路。 而经过的各条边之间没有相同的通路称为简单通路。 如果通路中顶点各不相同且边也各不相同，则称为初级通路或路径。 如果通路的起点和终点重合，称此通路为回路。没有相同边的回路称为简单回路，没有相同边也没有相同点（除起始点和终止点外）的回路称为圈。,14.2 通路和回路,讨论： （1）从一个顶点到某一顶点的通路（若有的话）不一定是唯一的； （2）通路的表示方法： (a)边点序列表示法： 设，为一有向图，viV，则通路可以表示成：（v1,e1,v2,e2,v3,vk-1,en,vk） (b)也可仅用边的序列表示 (c)顶点表示法(在简单图中)：（ v1, v2 , vk） (3)无向图中的以上术语的定义完全类似，不再重复。,例 1,例：给出有向图,求起始于,终止于的通路。 P1=(1,2,3)=(,) P2=(1,2,3,4,3) P3=(1,4,3) P4=(1,2,4,1,2,3) P5=(1,2,4,1,4,3) P6=(1,1,2,3), 可见： （1）从1到3有无限条通路，中间有回路； （2）上例中的P1 ，P2， P3， P5为简单通路。,通路的性质,定义:通路P中边的条数称为通路P的长度（路长）。长度为0的通路定义为一个单独的顶点。 定理14.5:设图，是中的顶点数（即），如果从v1到v2(v1v2)有一条通路，则从v1到v2有一条长度不大于n-1的通路。 推论:设图，是中的顶点数（即），如果从v1到v2(v1v2)有一条通路，则从v1到v2有一条长度不大于n-1的初级通路（路径）。,通路和回路的性质,定理14.6：在阶图中，从vi到vi如果存在一条回路的话，则从vi到vi一定存在一条长度小于或等于的回路。 推论：在阶图中，从vi到vi如果存在一条简单回路的话，则从vi到vi一定存在一条长度小于或等于的初级回路。,通路和回路,例： 1. 无向完全图Kn（n3）中有几种非同构的圈？ 2. 无向完全图K3的顶点依次标定为a，b，c. 在定义意义下K3中有多少 不同的长度为3的圈？,14.3 图的连通性,定义14.12：设无向图=，且vi,vjV，若从vi到vj存在一条通路的话，则称vi，vj是连通的。一般认为vi到自身是连通的。 由定义可见：连通的概念与vi到vj之间的通路多少、通路长度、是什么样的通路没有任何关系。,14.3 图的连通性,连通性一定满足： （）自反性： vi到vi一定是连通的。 （）可传递性： vi到vj连通，vj到vk连通，那么vi到vk连通。 （）对于有向图而言，既不一定对称，也不一定反对称。 若vi到vj存在一条通路的话，则vj到vi未必存在一条通路。 （连通性对无向图满足自反、对称和可传递性）,连通图,定义14.12：对于无向图中的任何顶点来讲，若任何二个顶点是相互连通的，则称此图是连通的，否则称为非连通图或分离图。,连通分支,定义14.13：设无向图G=，V关于顶点之间的连通关系的商集V/=V1,V2, Vk，Vi为等价类，称导出子图GVi(i=1,2,k)为G的连通分支，连通分支数k常记为p(G)。 一个无向图或者是一个连通图，或者是由若干个连通分支组成,距离,定义14.14: 在无向图G=中，从顶点vi到vj最短通路（短程线）的长度，叫做从vi到vj的距离，记为d(vi, vj) 。若从vi到vj不存在通路，则d(vi, vj) = 注意：在无向图中，有以下性质： 1) d(vi, vj) 0 2) d(vi, vi) = 0 3) d(vi, vj)=d(vj, vi) 4) d(vi, vj) +d(vj, vk) d(vi, vk),点割集、割点,定义14.15 设无向图 G= 。若存在 使得p(G-V) p(G)，且有任意的 均有p(G-V) =p(G)，则称V为G的点割集。若是单个点，则称割点。 定义14.16 设无向图 G= 。若存在 使得p(G-E) p(G)，且有任意的 均有p(G-E) =p(G)，则称E为G的边割集。若是单个边，则称割边或者桥。 点连通度 k-连通图 注意：若G是k-连通图，则在G中删除任何k-1个顶点后，所得图一定还是连通的 边连通度 r边-连通图,点连通度、边连通度的关系,对于任何无向图G，有,距离,定义14.19：设有向图=，且vi,vjV，若从vi到vj存在一条通路的话，则称vi可达vj。一般认为vi到自身是可达的。若vi可达vj并且vj可达vi，则称vi,vj相互可达。 定义14.20: 在有向图G=中，从顶点vi到vj最短通路（短程线）的长度，叫做从vi到vj的距离，记为d(vi, vj) 。若从vi到vj不存在通路，则d(vi, vj) =。,连通性,定义14.22：在有向图中，它的基图若是连通的，则称此有向图为弱连通的；若图中任何顶点偶对中至少有一点到另一顶点是可达的，则称此图是单向连通的；如果任两顶点均是互相可达的，则称是强连通的。 讨论定义： （1）强连通的一定是单向连通的和弱连通的； （2）单向连通的一定是弱连通的； （3）弱连通的既可能不是单向连通的，更可能不是强连通的。,连通性,强连通的 单向连通的 弱连通的,图的连通性,定理14.8 设有向图D=，Vv1,v2,vn 。D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。 证明：充分性显然 必要性（构造性证明） 定理14.9 设D是n阶有向图。D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。,二部图,定义14.23:如果无向图的顶点集V分成两个子集X,Y,(即满足XY=,XY=V),使得G中任意一边的两个端点分属于X和Y,则称G为二部图,X和Y称为互补顶点子集,常记图为G=。 定义:若二部图G=中X的每个顶点与Y的每个顶点都有且只有一条边相关联,称G为完全二部图,记为Km,n,其中|X|=m,|Y|=n。,例 4,子集X=a,b,Y=x,y,z,这是一个二部图。,这是完全二部图K2,3。,二部图,此两图均是K3,3因而是同构的 定理14.10:无向图G是二部图的充要条件是G的所有回路的长度均为偶数。,第十四章 图的基本概念,第三节：图的矩阵表示和运算,图的矩阵表示,矩阵是研究图的有关性质的最有效的工具之一，可运用图的矩阵运算求出图的通路、回路和其它一些性质。 前面讨论图的图解表示法的优点是直观，但缺点是： （1）在结点较多时，用图表示十分繁杂，甚至没法表示； （2）计算机中难以贮存。 本节讨论用矩阵表示图能较好的克服以上二大缺点。,图的矩阵表示,定义14.23 设无向图G，V=v1,v2,vn，E=e1,e2,em，令mij为顶点vi与边ej的关联次数，则称(mij)n×m为G的关联矩阵，记做M(G)。 1） M(G)每列元素之和均为2。 2） M(G)第i行元素之和为vi的度数。 3）各顶点的度数之和等于边数的2倍 4）第j列与第k列相同当且仅当边ej和ek是平行边。 5） 当且仅当vi是孤立点,图的矩阵表示,定义14.24 设有向图D中无环，V=v1,v2,vn，E=e1,e2,em， 令mij 1 vi为ej的始点 0 vi与ej不关联 1 vi为ej的终点 则称(mij)n×m为G的关联矩阵，记做M(D)。 1）M(D)中所有元素之和为0。 2）M(D)中，-1的个数等于+1的个数，都等于边数m。 3）第i行中，+1的个数等于d+(vi)，-1的个数等于d-(vi)。 4）平行边所对应的列相同。,图的矩阵表示,定义14.25：设D，是有向图，其中V=v1,v2,vn，并假定各结点已经有从v1到vn的排列次序。定义一个n×n的矩阵A，并把其中各元素aij表示成： aij = vi邻接到 vj 边的条数 则称矩阵A为图G的邻接矩阵。 例：设图D，如下图所示，其中 V=v1,v2, v3,v4,图的矩阵表示,讨论定义： （1）若图D的邻接矩阵中的元素为0和1，又称为布尔矩阵。 （2）图D的邻接矩阵中的元素的次序是无关紧要的，只要进行行和行、列和列的交换，则可得到相同的矩阵。,图的矩阵表示,（3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵； 若图是自反的，则主对角线的元素均为1； 若图是对称的，则对于i和j有aij=aji，主对角线的元素不论。,图的矩阵表示,（4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0； （5）在有向图的邻接矩阵中： 行中1的个数就是行中相应顶点的出度 列中1的个数就是列中相应顶点的入度,d+(1)=1,d-(1)=2 d+(2)=2,d-(2)=2 d+(3)=3,d-(3)=1 d+(4)=1,d-(4)=2,A(D)中所有元素之和为D中长度为1的通路的条数 对角线元素之和为D中长度为1的回路的条数 考虑：A(D)的n次幂表示什么？,图的矩阵表示,图的矩阵表示,*矩阵的计算（有向图中）： 设：,令,其含义为： 若ai1×a1j1，则表示有i1j长度为2的通路； A2表示i和j之间具有长度为2的不同通路的条数，,A3表示i和j之间具有长度为3的不同通路的条数， A4表示i和j之间具有长度为4的不同通路的条数。,例,从21有二条长度为2的通路；,从31有二条长度为3的通路;,从21有二条长度为4的通路；,图的矩阵表示,定理14.11：设，|V|=，A为G的邻接矩阵，则Am的元素表示（i ,j）之间具有长度为m的不同通路数，（i ,j）表示矩阵Am中的一个记入值。（长度为m的路径条数） 推论：设，|V|=，二个顶点之间的距离d(vi,vj)可以从A1,A2, An中去求得，当（i ,j）记入值不为零且矩阵的幂次最小时，这个幂次即是d(vi,vj) 。 由推论1可以求得一个图的距离矩阵。,例,图的矩阵表示,推论：Bn = A1A2An表示i到j之间的长度小于等于n的所有通路数， A1表示长度为1的通路数。 An表示长度为n的通路数。 （注意：Bn是A1,A2, An中各对应位数字相加之和）,图的矩阵表示,定义14.27：设D，是有向图，其中|V|=，假定D中各结点是有序的，定义一个n×n矩阵P，它的元素为：,则P称为图D的可达性矩阵。,图的矩阵表示,讨论定义： 可达性矩阵中的元素为0和1，它是布尔矩阵； 可达性矩阵只能表示vi到vj有无通路，而不能指明存在的所有通路，这和邻接矩阵是不相同的； 可达性矩阵P并没有表达出每一个元素自身可达的概念，若实际情况需要，可规定：主对角线上的元素均用1表示（自己到自己是可达的）,图的矩阵表示,下面介绍可达性矩阵的求法： 其方法是：若Bn-1中（i ,j）是非“0”元素，则对应的Pi,j=1，否则Pi,j =0。 例：,图的矩阵表示,由定义：若,由B3可得：,表示任何结点之间是可达的。,图的运算,定义14.29：设图G1=和图G2= （）G1和G2的并，定义为图G3= ，其中E3E1E2, V3为E1E2中边关联的顶点集，记为G3G1G2。 （）G1和G2的交运算定义为图G3= ，其中，E3E1E2, V3为E1E2中边关联的顶点集，记为G3G1 G2。 （）G1和G2的差运算定义为图G3= ，其中，E3E1E2, V3为E3中边所关联的顶点集，记为G3G1G2。 （）G1和G2的环和运算定义为G3= ， G3=(G1G2)(G1G2)，记为G1 G2 。,作业,5，6，11，14，17 21，23，25，33，40 44，46，47,
