第7章 图的基本概念.doc

第7章 图的基本概念图论（graphic theory）的起源可追溯到18世纪，数学家欧拉1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。但直到20世纪中后期，尤其是计算机科学与技术的发展，图的理论研究和应用研究才得到广泛的重视，图论作为一个重要的数学分支，才真正确立了自己的地位。离散数学研究的图是不同于几何图形、机械图形的另一种数学结构,不关心图中顶点的位置、边的长短和形状, 只关心顶点与边的联结关系。 欧拉图的概念是瑞士数学家欧拉（LeonhardEuler）在研究哥尼斯堡（K nigsberg）七桥问题时形成的。在当时的哥尼斯堡城，有七座桥将普莱格尔（Pregel）河中的两个小岛与河岸连接起来（见图3.1（a），当时那里的居民热衷于一个难题：一个散步者从任何一处陆地出发，怎样才能走遍每座桥一次且仅一次，最后回到出发点？这个问题似乎不难，谁都想试着解决，但没有人成功。人们的失败使欧拉猜想：也许这样的解是不存在的，1936年他证明了自己的猜想。为了证明这个问题无解，欧拉用A，B，C，D四个顶点代表陆地，用连接两个顶点的一条弧线代表相应的桥，从而得到一个由四个顶点、七条边组成的图（见图3.1（b），七桥问题便归结成：在图3.1（b）所示的图中，从任何一点出发每条边走一次且仅走一次的通路是否存在。 欧拉指出，从某点出发再回到该点，那么中间经过的顶点总有进入该点的一条边和走出该点的一条边，而且路的起点与终点重合，因此，如果满足条件的路存在，则图中每个顶点关联的边必为偶数。图3.1（b）中每个顶点关联的边均是奇数，故七桥问题无解。欧拉阐述七桥问题无解的论文通常被认为是图论这门数学学科的起源。7.1 无向图及有向图1、无序积设A,B为两集合,称 a,baAbB为A与B的无序积,记作AB将无序对a,b记作(a,b).2、无向图定义7.1 一个无向图G是一个二元组,即 G,其中, (1)V是一个非空的集合,称为G的顶点集,V中元素称为顶点或结点； (2)E是无序积VV的一个多重子集,称E为G的边集,E中元素称为无向边或简称边.元素可重复出现的集合为多重集例如： G=,V=v1, v2, v3, v4, v5, E= (v1, v2),(v2, v2),(v2, v3),(v1, v3), (v1, v3),(v1, v4)G的图形为：3、有向图定义7.2 一个有向图D是一个二元组,即 D,其中, (1)V同无向图中的顶点集； (2)E是卡氏积的多重子集,其元素称为有向边,也简称边.有时用V(D),E(D)分别表示图D的顶点集和边集。例如： D=,V=v1, v2, v3, v4, v5, E= , ,G的图形为：4、几个概念：设G为一无向图或有向图 (1)若V,E都是有穷集合,则称G是有限图. (2)若Vn,则称G为n阶图 (3)若E,则称G为零图特别是,若此时又有V1,则称G为平凡图. 5阶图 零图 平凡图定义7.3 设ek(vi,vj)为无向图G中的一条边,称vi,vj为ek的端点, ek与vi(或vj)是彼此关联的. 无边关联的顶点称为孤立点.若一条边所关联的两个顶点重合,则称此边为环.定义7.4 设无向图G=,vi, vjV, ek,elE.(1)若存在一条边e以vi、vj为端点,即e=(vi, vj),则称vi, vj是彼此相邻的,简称相邻的(2)若ek, el至少有一个公共端点,则称ek, el是彼此相邻的,简称相邻的对有向图若ekvi,vj,除称vi, vj是ek的端点外,还称vi是ek的始点, vj是ek的终点,vi邻接到vj,vj邻接于vi.定义7.5 设G为一无向图,viV,称vi作为边的端点的次数之和为vi的度数,简称度,记作d(vi).称度数为1的顶点为悬挂顶点,它所对应的边为悬挂边.设D为一有向图,vjV, 称vj作为边的始点的次数之和,为vj的出度,记作d+(vj)； 称vj作为边的终点的次数之和,为vj的入度,记作d-(vj)； 称vj作为边的端点的次数之和,为vj的度数,简称度,记作d(vj). 显然d(vj)d+(vj)d-(vj).例： d(v1)3，d+(v1)2，d-(v1)1； d(v2)3，d+(v2)2，d-(v2)1； d(v3)5，d+(v3)2，d-(v3)3； d(v4)d+(v4)d-(v4)0； d(v5)1，d+(v5)0，d-(v5)1； 其中，v5是悬挂结点，为悬挂边。 对于图G,记 (G)maxd(v)vV, d (G)mind(v)vV, 分别称为G的最大度和最小度.若DV,E是有向图,除了(D),d(D)外,还有最大出度、最大入度、最小出度、最小入度定理7.1（握手定理） 设图G为无向图或有向图,Vv1,v2,.,vn,|E|=m(m为边数),则推论 任何图(无向的或有向的)中,度为奇数的顶点个数为偶数.定理7.2设有向图D,Vv1,v2,.,vn,Em,则设Vv1,v2,.,vn为图G的顶点集,称(d(v1),d(v2),.,d(vn)为G的度数序列.例： (1) (3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？ 答：不能，由握手定理易知。 (2) 已知图G中有10条边,4个3度顶点,其余顶点的度数均小于等于2.问G中至少有多少个顶点？为什么？答：至少有8个顶点。定义7.6 在无向图中,关联一对顶点的无向边如果多于1条,称这些边为平行边.平行边的条数称为重数. 在有向图中,关联一对顶点的有向边如果多于1条,且它们的始点与终点相同,则称这些边为有向平行边,简称平行边. 含平行边的图称为多重图.既不含平行边,也不含环的图称为简单图.定义7.7 设G=是n阶无向简单图,若G中任何顶点都与其余的n-1个顶点相邻,则称G为n阶无向完全图,记作Kn. 设D=为n阶有向简单图,若对于任意的顶点u,vV(uv),既有有向边,又有,则称D是n阶有向完全图.注：Kn均指无向完全图.定义7.8 设G=, G=是两个图.若VV,且EE,则称G是G的子图, G是G的母图,记做G G. 若G G且GG(即VV或E E),则G是G的真子图. 若GG且V=V则称G是G的生成子图. 设V1V ,且V1,以V1为顶点集,以两端点均在V1中的全体边为边集的G的子图,称为V1导出的导出子图. 设E1 E,且E1 ,以E1为边集,以E1中关联的顶点的全体为顶点集的G的子图称为E1导出的导出子图. 下图给出了图G以及它的真子图G和生成子图G。G是结点集v1,v2,v4,v5,v6的导出子图。定义7.9 设G=是n阶无向简单图.以V为顶点集,以所有能使G成为完全图Kn的添加边组成的集合为边集的图,称为G相对于完全图Kn的补图,简称G的补图,记作G . 有向简单图的补图可类似定义.观察下列图有何特点？J 图(a)、图(b)、图(c)和图(d)所表示的图形实际上都是一样的。 定义7.10 设两个无向图G1=,G2=,如果存在双射函数q：V1V2,使得对于任意的e=(vi,vj)E1当且仅当e=(q (vi), q (vj)E2,并且e与e的重数相同,则称G1与G2是同构的,记作G1G2.例：例(1)画出4个顶点3条边的所有可能非同构的无向简单图；(2)画出3个顶点2条边的所有可能非同构的有向简单图.7.2 通路、回路、图的连通性1、通路（定义7.11） 给定图G.设G中顶点和边的交替序列为v0e1v1e2elvl,若满足如下条件:vi-1和vi是ei的端点(在G是有向图时,要求vi-1是ei的始点,vi是ei的终点),i1,2,l,则称为顶点v0到vl的通路.v0和vl分别称为此通路的起点和终点,中边的数目l称为的长度.当v0vl时,此通路称为回路. 2、简单通路（迹）若中的所有边e1,e2,el互不相同,则称为简单通路或一条迹.若回路中的所有边互不相同,称此回路为简单回路或一条闭迹.3、初级通路若通路的所有顶点v0,v1,vl互不相同(从而所有边互不相同),则称此通路为初级通路或一条路径.若回路中,除v0vl外,其余顶点各不相同,所有边也各不相同,则称此回路为初级回路或圈. 4、复杂通路、复杂回路有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路.由定义可知,初级通路(回路)是简单通路(回路),但反之不真.例：(1)为v0至v4的长为4的初级通路(路径).(2)为v0至v8的长为8的简单通路.(3)是v0至v5(v0=v5)的长为5的初级回路. (4)为v0到v8(v0=v8)的长为8的简单回路. 有向图中的初级通路,简单通路,初级回路,简单回路的示意图分别如下图(5),(6),(7),(8)所示在有向图的通路和回路中,注意箭头方向的一致性.5、几个定理：定理7.3 在一个n阶图中,若从顶点vi到vj(vivj)存在通路,则从vi到vj存在长度小于等于n1的通路.推论:在一个n阶图中,若从顶点vi到vj(vivj)存在通路,则从vi到vj存在长度小于等于n1的初级通路. 定理7.4 在一个n阶图中,如果存在vi到自身的回路,则从vi到自身存在长度小于等于n的回路.推论 在一个n阶图中,如果vi到自身存在一条简单回路,则从vi到自身存在长度小于等于n的初级回路.6、连通在一个无向图G中,若从顶点vi到vj存在通路(当然从vj到vi也存在通路),则称vi与vj是连通的.规定vi到自身总是连通的.在一个有向图D中,若从顶点vi到vj存在通路,则称vi可达vj.规定vi到自身总是可达的.短程线(无向图)：设vi,vj为无向图G中的任意两点,若vi与vj是连通的,则称vi与vj之间长度最短的通路为vi与vj之间的短程线,短程线(有向图)：设vi,vj为有向图D中任意两点,若vi可达vj,则称从vi到vj长度最短的通路为vi到vj的短程线,短程线的长度称为vi到vj的距离,记作d.性质：若vi不可达vj,规定d. d具有下面性质:(1) d 0,vivj时,等号成立.(2)满足三角不等式,即 d+d d.在无向图中,还有对称性,即d(vi,vj)d(vj,vi).例：在(a)中有：d(v2，v1)1，d(v1，v2)2，d(v3，v1)2，d(v1，v3)4；在(b)中有：d(v1，v3)2，d(v3，v7)3，d(v1，v7)4。 7、连通图（1）连通图(无向图)若无向图G是平凡图,或G中任意两顶点都是连通的,则称G是连通图;否则,称G是非连通图.无向图中,顶点之间的连通关系是等价关系.设G为一个无向图,R是G中顶点之间的连通关系,按着R可将V(G)划分成k(k1)个等价类,记成V1,V2,Vk,由它们导出的导出子图GV1,GV2,GVk称为G的连通分支,其个数记为p(G).例：G1是连通图，p(G1)1；G2是非连通图，且p(G2)4。 （2）连通图(有向图)设D是一个有向图,如果略去D中各有向边的方向后所得无向图G是连通图,则称D是连通图,或称D是弱连通图.若D中任意两顶点至少一个可达另一个,则称D是单向连通图.若D中任何一对顶点都是相互可达的,则称D是强连通图(1)为强连通图,(2)为单向连通图,(3)为弱连通图.注意:强连通图一定是单向连通图,单向连通图一定是弱连通图.8、点割集设无向图G,若存在顶点子集V V,使G删除V将V中顶点及其关联的边都删除)后,所得子图GV的连通分支数与G的连通分支数满足p(G-V)p(G),而删除V的任何真子集V后,p(G-V)p(G),则称V为G的一个点割集.若点割集中只有一个顶点v,则称v为割点.9、边割集若存在边集子集E E,使G删除E(将E中的边从G中全删除)后,所得子图的连通分支数与G的连通分支数满足p(G-E)p(G),而删除E的任何真子集E后,p(G-E)p(G),则称E是G的一个边割集.若边割集中只有一条边e,则称e为割边或桥.例1：v2, v7，v3，v4为点割集，v3，v4为割点e1, e2，e1, e3, e4，e6，e7, e8，e2, e3, e4等都是割集，其中e6是桥。例2：图(1)中,删除点集c,d后所得到的图(图(2)不再是连通图,但删除其子集c或d后得到的仍是连通图,所以c,d是点割集.图(3)中,删除点集a后得到的图如图(4)是非连通图,故a是割点.7.3图的矩阵表示1、无向图的关联矩阵设无向图G,Vv1,v2,vn,Ee1,e2,em,令mij为顶点vi与边ej的关联次数,则称(mij)nm为G的关联矩阵,记为M(G)例：、由定义可知,无向图关联矩阵由如下性质:(1)每列之和为2,说明每条边关联两个结点(环关联的结点重合);(2)每行之和为该行所对应结点的度数;(3)元素全为0的行,对应的结点是孤立点;(4)相同的两列,对应一对平行边;(5)M中所有元素之和是边数的2倍,等于各结点度数的总和,符合握手定理.在同构意义下,给定图G的关联矩阵,就可以画出G的图形.2、有向图的关联矩阵例：由定义可知,对于无环有向图的关联矩阵有如下性质:(1)关联矩阵是以-1,0,1为元素的矩阵;(2)关联矩阵每列元素之和为0,每行中1的个数等于它对应的结点的出度,每行中-1的个数等于它对应的结点的入度;(3)相同两列对应一对平行边,元素全为0的行对应孤立点.3、有向图的邻接矩阵设有向图D. V=v1,v2,vn, |E|m.令aij (1) 为vi邻接到vj的边的条数,称aij (1) mn为D的邻接矩阵,记作A(D).性质：4、有向图的可达矩阵7.4最短路径及关键路径1、最短路径问题v 对于有向图或无向图G的每条边附加一个实数w(e)则称w(e)为边e上的权.v G连同附加在各边上的实数称为带权图.常记带权图为G=.v 设G1是带权图G的子图,称为G1的权,记作W(G1).当然,W(G)是G的权.当无向边e=(vi,vj)或有向边e=时,w(e)也记为wij 什么是最短路径：设带权图G=. wij0 .u,v为G中任意两个顶点,从u到v的所有通路中带权最小的通路称为u到v的最短路径.设G=是n阶简单带权图,wij0.若顶点vi与vj不相邻,令wij=.求G中顶点v1到其余各顶点的最短路径. 例如交通网络中的带权图求最短路径的问题。 （1）两地之间是否有路相通? （2）在有多条通路的情况下，哪一条最短?其中，交通网络可以用带权图表示：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离，交通费用或途中所需的时间等等。例：由表可知,v5与v3相邻,v3与v4相邻,v4与v2相邻,v2与v1相邻,v1与v0相邻.这样从v5往前追踪,得v0到v5的最短路径为 =v0v1v2v4v3v5. W()=9.2.关键路径问题v 后继元集;先驱元集.v PERT图（计划评审技术图）设D=是n阶有向带权图,满足:1)D是简单图;2)D中无回路;3)有一个顶点入度为0,称此顶点为发点;有一个顶点出度为0,称此顶点为收点;4)记边带的权为wij;它常表示时间;则称D为PERT图.通常把计划、施工过程、生产流程、程序流程的都当成一个工程。除了很小的工程外、一般都把工程分为若干个叫做“活动”的子工程。完成了这些“活动”的子工程，这个工程就可以完成了。通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边 表示活动vi必须先于活动vj进行。 这种的有向图叫做用边表示活动的网络，简称AOE（active on edges）网络。AOE网络在某些工程估算方面非常有用。他可以使人们了解： （1）：研究某个工程至少需要多少时间？ （2）：那些活动是影响工程进度的关键？在AOE网络中，有些活动可以并行的进行。完成不