离散数学图论部分

第四部分图论图论问题的起源18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”SNAB陆地岛屿岛屿陆地哥尼斯堡七桥问题如何不重复地走完七桥后回到起点？。。。。ABCD当时人们热衷于这样的游戏：设想从任一个地方出发通过每座桥一次且仅一次后回到原地,这是否可能?但多次实践都发现不行。1727年欧拉的朋友向欧拉提出了这个问题是否有解？1736年欧拉用图论的方法解决了这个问题,写了第一篇图论的论文,成为图论的创始人。后来称此问题为哥尼斯堡七桥问题。•但在此之后100年间，没有大的进展。•直到Kirchhoff(克希霍夫)用树的理论解决了电网络问题。这些结果引起了人们的重视,图论的研究进入了一个发展时期。•直到1920年,科尼格(Konig)撰写了许多图论方面的论文。在1936年科尼格(Konig)发表了第一本图论书籍《有限图与无限图理论》,总结了200年来图论研究的主要成果。•此后的50年,图论经历了一场爆炸性的发展,成为数学科学中一门独立的学科。•几十年来图论在理论上和应用上都得到很大的发展,特别是在近30多年来由于计算机的广泛应用而又得到飞跃的发展。•在计算机科学、运筹学、化学、物理和社会科学等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应用。•这里主要讨论图的基本概念和算法,为今后的学习和研究打下基础。本章首先给出图、简单图、完全图、子图、路和图的同构等概念，接着研究了连通图性质和规律，给出了邻接矩阵、可达性矩阵、连通矩阵和完全关联矩阵的定义。最后介绍了欧拉图与哈密尔顿图。图的定义（无向图）一个无向图G是一个有序二元组EV,，记作EVG,，其中V是一个非空集合，V中的元素称为结点或顶点；E是无序积VV&的多重子集（元素可重复出现的集合），称E为G的边集，E中的元素称为无向边或简称边。（有向图）一个有向图G是一个有序二元组EV,，记作EVG,，其中V是一个非空的结点集；E是笛卡尔积V×V的多重子集，其元素称为有向边，也简称边或弧。例如,,EVG54321,,,,vvvvvV,),,{(21vvE)},(),,(),,(),,(),,(4331313222vvvvvvvvvv,G的图形如图2.1.3所示。例如EVG,，其中54321,,,,vvvvvV,,,,,,,,,,,{4223322111vvvvvvvvvvE},43vv,G的图形如图2.1.4所示。图2.1.44v3v2v1v1e3v4v4e图2.1.36e1v5e2e2v3e5v例画出下列图形。(1)G=V,E,其中V={v1,v2,v3,v4,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v1,v5),(v2,v5),(v4,v5)}。v1v2v3v4v5e1e2e3e4e5e6例：画出下列图形。(2)D=V,E,其中V={v1,v2,v3,v4},E={v1,v1,v1,v2,v2,v1,v1,v4,v3,v4,v4,v3,v3,v2}。v1v2v3v4e1e2e3e4e5e6e7图相关的概念和规定设G=V,E为一有向图或无向图。(1)V、E分别表示G的顶点集、边集，|V|、|E|分别表示G的顶点数、边数。若|V|=n,则称G为n阶图。(2)若|V|、|E|均为有限数，则称G为有限图这是本书讨论的重点。(3)在图G中，若E=,则称G为零图。此时若|V|=n，则称G为n阶零图，记作Nn。若|V|=1，则称G为平凡图。(a)图(b)零图(c)完全图没有任何边的图称为零图；只有一个点，没有边的图称为平凡图；任意两点之间都有边的图称为完全图。v1v2v3v4v5e1e2e3e4e5e6在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。例：下图中e4与e5是平行边。v1v2v3v4v5e2e3e4e5e6e7e8在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(即方向相同)，则称这些边为平行边。例：下图中e3与e4是平行边,e7与e8不是平行边（因为e7与e8方向不同）含平行边的图称为多重图；既不含平行边也不含环的图称为简单图。本书主要讨论简单图的相关结论。设G=V,E为无向图，ek=vi,vj∈E,则称vi,vj为ek的端点，ek与vi或ek与vj是彼此关联的。无边关联的顶点称为孤立点。若一条边所关联的两个顶点重合，则称此边为环。vi≠vj，则称ek与vi或ek与vj的关联次数为1，若vi=vj，则称ek与vi的关联次数为2；若vi不是ek的端点，则称ek与vi的关联次数0。设G=V,E为无向图，vi,vj∈V,ek,el∈E,(1)若存在一条边e以vi,vj端点，即e=(vi,vj)则称vi与vj是彼此相邻的。简称相邻的。(2)若ek与el至少有一个公共端点，则称ek与el是彼此相邻的。简称相邻的。设D=V,E为有向图,vi,vj∈V,ek,el∈E,若ek=vi,vj,除称vi,vj是ek的端点外，还称vi为ek的起点，vj为ek的终点，并称vi邻接到vj,vj邻接于vi。顶点的度设G=V,E为一无向图，vi∈V,称vi作为边的端点的次数之和为vi的度数，简称为度，记作deg(vi)（或d(vi)）。设D=V,E为一有向图，vj∈V,称vj作为边的始点的次数之和,为vj的出度，记作d+(vj);称vj作为边的终点的次数之和,为vj的入度，记作d-(vj);称d+(vj)+d-(vj)为vj的度数，记作d(vj)。称度数为1的顶点为悬挂顶点,它所对应的边为悬挂边。例：在上图(1)中,d(v1)=4,d(v2)=4,d(v5)=0,……,在图(2)中,d+(v1)=2,d-(v1)=1,d(v1)=3d+(v2)=1,d-(v2)=3,d(v2)=4,……v1v2v3v4v5e1e2e3e4e5e6(1)v1v2v3v4v5e1e2e3e4e5e6e7e8(2)在无向图G中,令△(G)=max{d(v)|v∈V(G)};(G)=min{d(v)|v∈V(G)}称△(G)和(G)分别为G的最大度和最小度。在有向图D中,可类似定义△(D)、(G)。另外,令△+(G)=max{d+(v)|v∈V(D)}+(G)=min{d+(v)|v∈V(D)}△-(G)=max{d-(v)|v∈V(D)}-(G)=min{d-(v)|v∈V(D)}分别为D的最大出度、最小出度、最大入度、最小入度。简记作△、、△+、+、△-、-。v1v2v3v4v5e1e2e3e4e5e6(1)v1v2v3v4v5e1e2e3e4e5e6e7e8(2)例在上图(1)中,最大度△=6,最小度=0,在图(2)中,最大度△=4,最小度=2,最大出度△+=4,最大入度△-=3最小出度+=1,最小入度-=0。握手定理设G=V,E为无向图或有向图，V={v1,v2,…,vn},|E|=m(m为边数)则证明：G中每条边（包括环）均提供2个端点，故在计算各顶点度数的和时，每条边均提供2度，m条边共提供2m度。=2m。即每个顶点度数之和等于边数的2倍。Vvv)deg(推论在任何图G=V,E中，度数为奇数的结点必为偶数个。设G=V,E是有向图，vV，射入(出)结点v的边数称为结点v的入(出)度。记为deg－(v)(deg＋(v))。显然，任何结点的入度与出度的和等于该结点的度数，即deg(v)=deg－(v)+deg＋(v)。定理：在有向图中，所有结点入度的和等于所有结点出度的和。证明：在有向图中每一条边对应一个入度和一个出度，为图的入度和出度各增加1。所以，所有结点入度的和等于边数，所有结点出度的和也等于边数。设V={v1,v2,…,vn}为图的顶点集，称(d(v1),d(v2),…d(vn))为G的度数序列。例：在下图中的度数序列为（4,4,3,1,0)。v1v2v3v4v5e1e2e3e4e5e6例①(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？②已知图G中有10条边,4个3度顶点,其余顶点的度数均不大于2,问G中至少有多少个顶点?为什么？解:①由于这两个序列中,奇数个数均为奇数,它们都不能成为图的度数序列。②图中边数m=10,由握手定理可知,G中各顶点度数之和为20，4个3度顶点占去12度，还剩8度若其余全是2度顶点,还需要4个顶点来占用这8度，所以G至少有8个顶点。如：K3K6Kn的边数为m=Cn2=n(n-1)/2完全图设G为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图，记作Kn(n≥1)。如：3阶有向完全图n阶有向完全图的边数m=n(n-1）。有向完全图设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D为n阶有向完全图。正则图在一个无向简单图中，如果每个结点的度数均为k，则该图称为k-正则图。下图所示的图称为彼得森（Petersen）图，是3-正则图。完全图是n-1-正则图。如：(1)(3)补图设G=V,E为n阶无向简单图,以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作G。(2)(1)(2)例：在下图中,(1)是(2)的补图,当然(2)也是(1)的补图,就是说,(1),(2)互为补图同样,(3),(4)互为补图。(3)(4)子图与生成子图设G=V,E,G`=V`,E`为两个图(同时为无向图或有向图)，若V`V且E`E，则称G`为G的子图，G为G`的母图，记作G`G。若G`是G的子图，且V`V或E`E，则称G`为G的真子图。若G`是G的子图，且V`=V，则称G`为G的生成子图。生成子图非常重要。导出子图V1V且V1≠,以V1为顶点集,以两端点均在V1中的全体边为边集的G的子图,称为V1导出的导出子图，记为G[V1]。E1E且E1≠,以E1为边集,以E1中边关联的顶点的全体为顶点集的G的子图,称为E1导出的导出子图,记为G[E1]。例：在上图中，G是母图，G1是G的子图，且是真子图；G2是G的生成子图；G3是由边子集{e4,e5}的导出子图，记为G[{e4,e5}];G3也是由结点子集{a,d,e}的导出子图，记为G[{a,d,e}];e3e2e1e4e5e7e6abdeGe3e2e1e4abdG1cce3e4e6abdeG2ce4e5adeG3(1)abdce1e2e3e4e5e6bdce3e4e5(2)(3)母图同时也是(1)的生成子图。(2）是(1)子图、真子图。（3）是（1）的子图、真子图、生成子图。cabde3e4e5e2例：判断下列各图的母子关系。图的同构设G1=V1,E1,G2=V2,E2为两个无(有)向图，若存在双射函数f:V1→V2,于vi,vj∈V1,(vi,vj)∈E1(vi,vj∈E1)(f(vi),f(vj))∈E2(f(vi),f(vj)∈E2)，并且(vi,vj)(vi,vj)与(f(vi),f(vj))(f(vi),f(vj))重数相同，则称G1与是G2同构的，记作G1≌G2。换言之：两个图G1=V1,E1,G2=V2,E2,如果它们的节点间存在一一对应关系（双射），而且这种对应关系也反映在表示边的结点对中(如果是有向边则对应的结点对还保持相同的顺序),则称此两图是同构的。两个图同构的判断非常困难，需要仔细考察图的结点和边的关联关系。如何判断两个图是否同构呢？答案：迄今为止还没有有效的算法。根据定义，则我们得到两个图同构的必要条件：(1)结点数目相等；(2)边数相等；(3)度