图的基本概念

第五章图的基本概念•图论起源于1736年欧拉(Enler)的第一篇图论论文,解决了“哥尼斯堡的七桥问题”。在哥尼斯堡的匹格河上有七座桥,如图所示。•当时人们热衷于这样的游戏：设想从任一个地方出发通过每座桥一次且仅一次后回到原地,这是否可能?但多次实践都发现不行•1727年欧拉的朋友向欧拉提出了这个问题是否有解？•1736年欧拉用图论的方法解决了这个问题,写了第一篇图论的论文,成为图论的创始人。•后来称此问题为哥尼斯堡七桥问题。•在图a中,用边表示桥,顶点表示岛屿和河的两岸,便得到一个图,如图b所示。很显然,通过哥尼斯堡七座桥中每一座一次且仅一次的问题等价于在图5.13(b)中找一条闭链,使得它的每一边出现一次且仅一次,也就是如何一笔画的问题。•但在此之后100年间，没有大的进展。•直到Kirchhoff(克希霍夫)用树的理论解决了电网络问题，•1857年Cayler(凯莱)用统计不同构树的方法来计算CnH2n+1同分异构体数目,•这些结果引起了人们的重视,图论的研究进入了一个发展时期,•在此期间,出现了两个著名的问题:四色问题和Hamilton回路问题,成为不少数学家的研究目标。•但在19世纪后期和二十世纪初，图论的研究再次处于停顿状态。•直到1920年,科尼格(Konig)攥写了许多图论方面的论文,•在1936年科尼格(Konig)发表了第一本图论书籍《有限图与无限图理论》，总结了200年来图论研究的主要成果。•此后的50年，图论经历了一场爆炸性的发展，成为数学科学中一门独立的学科。•主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。•几十年来图论在理论上和应用上都得到很大的发展,特别是在近30多年来由于计算机的广泛应用而又得到飞跃的发展。•在计算机科学、运筹学、化学、物理和社会科学等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应用。•这里主要讨论图的基本概念和算法，为今后的学习和研究打下基础。5.1引言•一、图的定义：•在集合论中离散对象之间的关系可以用关系图来描述,这种图就是图论中所述的有向图。•定义5.1：设V是一个非空集,E是V上的二元关系,称有序对(V,E)为有向图,记为G=(V,E)或G(V,E)。V中的元素称为顶点(或点),V称顶点集。E是V×V的子集,E中的元素是有序对,称为弧,E称为弧集。•例如有向图G=(V,E),V={a,b,c,d,e,f,g},•E={(a,b),(a,c),(b,c),(c,a),(c,c),(c,e),(d,a),(d,c),(f,e),(f,f)},•弧(a,b)表示从顶点a到顶点b的一条带箭头的线。对于弧(a,b)来讲,在关系中a称为有序对中的第一个元素,b称为第二个元素。在图论中，称a为起点，b为终点。称a与弧(a,b)关联，b与弧(a,b)关联。弧(c,c),(f,f)这种起点与终点相同的弧就称为自环。在图中，g与E中任何元素(弧)都不关联，称为孤立点。•定义5.2：顶点a和b称为弧(a,b)的端点,a为起点,b为终点。称a和b与弧(a,b)关联。若顶点a和b相同,则对应的弧(a,b)称为自环。若V中某顶点与E中任何弧都不关联,则该顶点称为孤立点。与一条弧相关联的两个顶点称为邻接的或相邻的。一顶点关联于几条弧,称这些弧是弧邻接或弧相邻。例如上图中a与b相邻;c与d相邻;(a,b)与(b,c)弧相邻。•在研究有向图时,只考察它的顶点与弧的连接关系以及整个图形所具有的性质。至于各顶点之间的相对位置及弧的长短曲直都是无关紧要的。•对于有向图，弧集中的元素都是有序对，若改成无序对，则就是下面介绍的无向图。•定义5.3：设V是一个非空集,E是以V中两个元素组成的多重集为元素的集合,称有序对(V,E)为无向图,也记为G=(V,E)或G(V,E)。V中的元素称为顶点或点,V称为顶点集,E中的元素称为边,E称为边集。•E中元素现在也是集合，由于可能出现{a,a}这种情况，所以说E中元素是V中两个元素组成的多重集。该图的V={v1,v2,v3,v4,v5,v6}，E={{v1,v2},{v1,v5,}，{v2,v2},{v2,v3},{v2,v4},{v2,v5},{v2,v5},{v3,v4},{v4,v5}}，边{v1,v2}关联于顶点a,b，而{v2,v2}这种关联的两个顶点是相同的称为自环。而v6不关联任何边，也称为孤立点。顶点v4同时关联边{v2,v4},{v3,v4},{v4,v5}，称这些边为边邻接另外在上图中，边{v2,v5}出现了两次，象这种两个顶点之间出现不止一条的边称为多重边。•定义5.7：若图G=(V,E)中,连结两个顶点之间的边可以不止一条这些边称为多重边,则图G称为多重图。无自环的非多重图称为简单图。边集为空集的图称为零图。只有一个顶点的图称为平凡图。若G中每两个顶点之间恰有一条边,则称G为完全图。n个顶点的完全图记为Kn。•在定义5.7中,零图是指没有边的图,其每个顶点为孤立点,但顶点集V不能是空集。•同样在有向图中，也可定义多重弧，多重有向图和简单有向图。•为了叙述方便起见,简称无向图为图,如果在图(有向图)中顶点标以名称,如上图中顶点标a,b,c,d,e,f,g,这样的图(有向图)称为标定图(有向图),否则称为非标定图(有向图)。下面主要考虑标定图。•如果一个图的顶点集和边集是有限的,则称该图为有限图,类似地定义有限有向图。我们这里讨论的图和有向图是指有限图和有限有向图。•图(有向图)的最本质的内容就是顶点与边(弧)的关联关系。为了描述这一关系,现在引进一个重要的概念,即顶点的度数。•二、顶点度数•定义5.4：设G=(V,E)是一个图,顶点v所关联的边数(有自环情况要计算两次),称为顶点v的度数,记为d(v)。度数为1的顶点称为悬挂点。度数为奇(偶)数的顶点称为奇(偶)顶点。图G中顶点的最小度数记为(G),(G)=minvV{d(v)},简记为。•在这里要注意：•对于边{a,b},在计算顶点a的度数和b的度数时分别都被用了一次，因此对于自环，此时b=a,{a,a},同样要统计两次。•证明：对每条边来讲，有两个端点，•在计算顶点度数时，每条边被计算了两次(极端情况，自环，同一端点同样算了两次)，•所以图中所有顶点度数之和为边数的两倍。定理5.1:evdnii2)(1•定理5.2:奇顶点有偶数个。•定义5.5：设G是一个有向图,以顶点v为起点的弧数称为v的出度,记为d+(v);以顶点v为终点的弧数称为v的入度,记为d-(v)。•对于有向图G中任一顶点v,d+(v)+d-(v)称为顶点v的度数,也记为d(v)。•作为弧，有进必有出，有出必有进，两者平衡•定理5.3:在有向图中,所有顶点的入度之和等于所有顶点的出度之和。•证明略。•三、同构•一个有向图的弧以及弧所关联的顶点位置变动后,可以画出许多不同的图形和形状。例如图的(a)和(b)这两个有向图,粗看起来是不同的,但仔细观察以后,发现顶点之间一一对应,即aD,bB,cA,dE;弧之间也一一对应,即(a,b)(D,B),(a,c)(D,A),…，即这两个有向图除顶点所标名称不同外,其结构相同,顶点数相同,弧数相同,并且顶点与弧的关联关系保持不变,通常说这两个有向图是同构的。•定义5.6：设G=(V,E)和G'=(V',E')是两个有向图,若存在双射:V→V'以及双射:E→E',使得对任何u,vV,(u,v)E,有((u,v))=((u),(v)),称G和G'是同构的,记为GG'。•类似可以定义两个无向图的同构概念。•图5.4中两个图同构,即著名的彼得森(Petersen)图。该图的每个顶点度数均为3,称为3-正则图。一般,若图的每个顶点度数均为r,则称为r-正则图。•研究同构的好处是，对于几个同构的图只要研究其中一个图的性质，其他几个图的性质也就知道了。事实上同构关系是一个等价关系。•定义5.8：设V是顶点集,E是边集,f是V到实数的函数,g是E到实数集的函数,称有序三元组G=(V,E,f)或G=(V,E,g)，以及有序四元组G=(V,E,f,g)为带权图。•例如下图就是边上带权为g的带权图G=(V,E,g),以后主要讨论边上带权的带权图•在有向图中类似可以定义带权有向图。•四、子图•在讨论图的性质时研究图的局部结构是相当重要的,现介绍子图的概念。•定义5.9：设有图G=(V,E),若在图G'=(V',E')中,V'V,E'E且E'中边所关联的顶点在V'中,则称G'为G的子图。若V'=V,E'E,则子图G'=(V',E')称为图G的一个生成子图。•定义5.10：设有图G=(V,E),设E'E,以E'为边集,E'中边的端点全体为顶点集,构成的子图称为由E'导出的G的子图,记为G(E'),又称为G的边导出子图。设V'V,以V'为顶点集,端点均在V'中所有边的全体为边集,构成的子图称为由V'导出的G的子图,记为G(V'),又称为G的导出子图•例如图(d)是由G的边{v1,v2},{v2,v4},{v4,v5}导出的子图J,•(e)是由G的顶点v1,v2,v4,v5导出的子图H。定义5.11:设G=(V,E)是n个顶点的任意简单图,从完全图Kn中删去G的所有边,但保留顶点集V所得到的图称为G的补图,记为G,简称为G的补。•简单图G=(V,E)的补图是一个以V为顶点集的简单图,中两个顶点相邻当且仅当这两个顶点在G中不相邻。•从图G中删去一个顶点v及其关联的边得到的子图,记为G-v,或G-{v}。从图G中删去一边e得到的子图记为G-e,如图所示。5.2路与回路•一、路径,链,路•定义5.12：图G的一个有限点边交替序列(v0,e1,v1,e2,…,em,vm)，使得对1≤i≤m,ei的端点是vi-1和vi,称该序列为一条路径。边e1,e2,…,em互不相同的路径称为链。m称为该链的长度。顶点都不相同的链称为路,m称为该路的长度。v0=vm的路径(或链)称为闭路径(或闭链)。除首尾两点外其余顶点都不相同的闭链称为回路。长度为偶(奇)数的路或回路称为偶(奇)路或偶(奇)回路。•例如图中(v2,e6,v5,e7,v2,e8,v4,e4,v5,e7,v2,e1,v1)是一条v2到v1的路径;•(v2,e6,v5,e7,v2,e1,v1)是一条v2到v1的路径，由于边不重复，所以是链;•(v2,e8,v4,e4,v5,e5,v1)是一条v2到v1的路径，边不重复，所以是链，又因为点也不重复，所以是一条路。有时点边交替序列可用边序列或点序列代替。在图中(v2,e6,v5,e7,v2,e8,v4,e4,v5,e7,v2)是一条闭路径;(v1,e1,v2,e6,v5,e7,v2,e8,v4,e4,v5,e5,v1)是一条闭路径，由于边不重复，是一条闭链;(v1,e1,v2,e8,v4,e4,v5,e5,v1)是一条闭路径，由于边不重复，是一条闭链，除首尾两点外，点不重复，是回路。(v2,e6,v5,e7,v2)也是回路。•一条路也是一条链,一条回路也是一条闭链,并且自环和两条多重边都自成一条回路•一条回路上每个顶点的度数为2,一条路除起点和终点外,每个顶点的度数也为2。•定理5.4：若图G中每个顶点度数至少为2,则G包含一条回路。•证明：若图G包含自环或多重边,则定理结论显然成立(a,e,a),或(a,e,b,e',a)。•下面假设图G是简单图•二、连通与连通图•定义5.14：设u和v是图G的两个不同的顶点,若u和v之间存在一条路,则称顶点u和v是连通的。若图G中任何两个不同顶点之间存在一条路,则称G为连通图,否则称G为不连通图。上面图是连通图，而下面图因为v1到v8之间没有路，即v1与v8不连通，所以不是连通图把V划分为非空子集V1,V2,…,Vω,使得u和v属于同一子集Vi当且仅当u和v是连通的。每个顶点子集Vi的导出子图Gi称为G的一个连通分支,简称分支。G有ω个分支:G1,G2,…,Gω。当ω