第6章图的基本概念.ppt

1/42,主要内容：图的基本概念 树与割集 连通度与匹配 平面图与图的着色 有向图,第二篇 图论,2/42,第六章 图的基本概念,主要内容：图论的产生与发展图的基本定义路、回路、连通图补图、偶图欧拉图哈密顿图图的矩阵表示带权图与最短路问题,3/42,6.1 图论的产生与发展,图论是数学的一个分支，它以图为研究对象。图是由若干给定的点和连接两点的线所构成。其中，用点代表事物，用连接两点的线表示相应两个事物间具有的特定关系。图论起源于18世纪，文字记载最早出现于瑞士数学家欧拉(L.Euler)1736年的论著中，关于解决哥尼斯堡七桥问题。,4/42,6.1 图论的产生与发展,哥尼斯堡七桥问题:,一个出发者能否从一块陆地出发走遍七座桥,而且每座桥恰好走一次，最后回到出发点？,陆地用点来表示,桥用连接两个点的一条线段来表示。,A B DC,5/42,6.1 图论的产生与发展,1936年德国数学家柯尼希(D.Knig)著线复形的组合拓朴学作为第一本图论著作问世，前后相隔200年。在这期间，德国学者基希霍夫(G.R.Kirchhoff)、英国数学家凯莱(A.Cayley)、哈密尔顿(W.R.Harmilton)和法国数学家若尔当(M.E.C.Jordan)等人都做出了开创性的工作。,6/42,6.1 图论的产生与发展,在20世纪100年间，图论不仅在许多领域，如运筹学、计算机科学等得到了广泛的应用，而且学科本身也获得长足发展，形成了拟阵理论、超图理论以及代数图论、拓朴图论等新分支。本篇只讨论图论的最基本概念和基本理论及其典型应用，为大家在今后学习和工作中能够运用这一有力工具打下良好的基础。,7/42,设V是一个非空集合，V的一切二元子集之集合记为P2(V)，即P2(V)=AAV,A=2(=x,y|x,yA).,定义6.2.1 设V是一个非空集合，EP2(V)，二元组(V,E)称为一个无向图。V称为顶点集，V中元素称为无向图的顶点；E称为边集，E的元素称为无向图的边。如果u,vE，则称u与v相邻(邻接).,6.2 图的基本定义,以V为顶点集，E为边集的无向图(V,E)常用字母G表示，即G=(V,E).,如果V=p，E=q，则称G为一个(p,q)图，即G是一个具有p个顶点q条边的图.,8/42,常用小写的英文字母u,v,w表示图的顶点(带下标);常用小写的英文字母x,y,z表示图的边(带下标)。,1、顶点与边的表示方法,如果x=u,v是图G的一条边，则x为这条边的名，u和v称为边x的端点，这时称顶点u和v与边x互相关联，还说x是联接顶点u和v的边，且记为x=uv或x=vu，若x与y是图G的两条边，并且仅有一个公共端点，即xy=1，则称边x与y相邻(邻接).,2、顶点与边的关联、边与边相邻(邻接),6.2 图的基本定义,9/42,由定义可知，一个无向图G就是一个非空有限集合V上定义的一个反自反且对称的二元关系E和V构成的关系系统.,3、图的关系表示,6.2 图的基本定义,10/42,实例 设V=v1,v2,v5,E=v1,v2,v2,v3,v2,v5,v1,v5,v4,v5，则 G=(V,E)为一无向图.,将图的每个顶点在平面上用一个点或一个小圆圈表示，并在其旁写上顶点的名(如果顶点已命名)，如果x=u,v是图的一条边，则在代表u和v的两点间连一条线，这样得到的图就叫做一个图的图解.注意：在画图的图解时，线的交点不是图的顶点.,4、图解,6.2 图的基本定义,11/42,定义6.2.2 在图中联结一个顶点与其自身的边称为环。允许有环存在的图称为带环图.,在图中如果允许两个顶点之间有两个以上的边存在，这样的边称为平行边(或多重边)。平行边的条数称为重数.含平行边的图称为多重图.,伪图,允许有环与平行边存在的图，称为伪图.,既不含平行边也不含环的图称为简单图.,问题：这里的“图”究竟是如何定义的？,12/42,相关概念,1、n阶图n个顶点的图,2、有限图顶点数和边数均为有限数的图(注意：以后所 讲的图都是有限图).,3、零图一条边也没有的图(G=(V,E),E=)。n 阶零图记作Nn，即(n,0)图。1阶零图N1称为平凡图，即(1,0)图.4、空图规定顶点集为空集的图，记为.,13/42,相关概念,5、顶点与边的关联关系 设G=为图，x=vi,vjE，则称vi，vj为x的端点，x与vi(vj)关联.若vivj，则称x与vi(vj)的关联次数为1；若vi=vj，则称x与vi(vj)的关联次数为2，并称x为环；如果顶点vm不与边x关联，则称x与vm的关联次数为0.,14/42,如果x=(u,v)是有向图的一条边，则称弧x为起于顶点u终于顶点v的弧，或从u到v的弧，u称为x的起点，v为x的终点。,有向图,定义6.2.3 设V为一个非空有限集合，AVV(u,u)|uV，二元组D=(V,A)称为一个有向图。V中的元素称为D的顶点，A中元素(u,v)称为D的从u到v的弧或有向边.如果x=(u,v)与y=(v,u)均为A的弧，则称x与y为一对对称弧.,定义6.2.4 不含对称弧的有向图称为定向图.,15/42,定义6.2.5 设G=(V,E)是一个图，图H=(V1,E1)称为G的一个子图，如果V1是V的非空子集且E1是E的子集.,子 图,定义6.2.6 设G=(V,E)是一个图，如果FE，则称G的子图H=(V,F)为G的生成子图.,如果H是G的子图，则说G包含H.,设H是图G的一个子图.如果HG，则称H是G的真子图。,16/42,极大子图,设G的子图H具有某种性质，若G中不存在与H不同的具有此性质且真包含H的图，则称H是具有此性质的极大子图.,包含V1并且与V1有边相连的极大子图,17/42,定义6.2.7 设S为图G=(V,E)的顶点集V的非空子集，则G的以S为顶点集的极大子图称为由S导出的子图，记为.形式地，=(S,P2(S)E).,S的两个顶点在中相邻，当且仅当这两个顶点在G中相邻。,导出子图,v1 v2 v3 v6 v4,18/42,设G=(V,E)，uV，由V u导出的子图记成G-u，从图的图解上看，G-u的图解是从G的图中去掉顶点u及与u关联的边所得到的图解.,子图的表示方法,设x是G的一条边，则G的生成子图(V,E x)简记为G-x.,如果u和v是G的两个不相邻的顶点，则图(V,Eu,v)简记成G+uv，它是在G的图解中，把u与v间联一条线而得到的图.,19/42,v1 v2 v3 v4 v5,v1 v3 v4 v5,v1 v2 v3 v4 v5,v1 v2 v3 v4 v5,图G,图G-v2,图G-v4,v5,图G+v2,v4,实例,20/42,顶点的度数,定义6.2.8(1)设G=为无向图,vV，称v作为边的端点的次数之和为v的度数，简称为度，记作degv.(2)G的最大度 G的最小度(3)奇度顶点与偶度顶点.(4)度为零的顶点称为孤立顶点.,显然，对(p,q)图的每个顶点v，有0degvp-1.,21/42,定理6.2.1(Euler定理或握手定理)设G=(V,E)是一个具有p个顶点q条边的图，则G中各顶点度的和等于边的条数q的两倍，即:,证 G中每条边均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，q 条边共提供 2q 度.,注意：此定理对伪图也成立。,握手定理,22/42,推论6.2.1 任一图中，度为奇数的顶点的数目必为偶数.,证 设G=(V,E)，令度为奇数的顶点的集合为V1，则V2=V V1为度为偶数的顶点之集;,从而,也就是V1个奇数相加是偶数，V1的个数必为偶数.,由定理6.2.1有,握手定理推论,23/42,定义6.2.9 图G称为r度正则图，如果(G)=(G)=r，即G的每个顶点的度都等于r.3度正则图也叫做三次图.一个具有p个顶点的p-1度正则图称为p个顶点的完全图,记为Kp.,在Kp中，每个顶点与其余各顶点均相邻，所以Kp有p(p-1)/2条边.,r-正则图,推论6.2.2 每个三次图均有偶数个顶点.,0度正则图就是零图.,24/42,例6.2.1 证明：在至少有两个人的团体里，总存在两个人，使得他们在这个团体里恰有相同个数的朋友.,证 设此团体里共有n个人，n2，若用点表示人，两人互为朋友时就在相应点间联一条线，这样便得到了具有n个顶点的图G，每个人的朋友数就是G中相应顶点的度，要证明G中必有两个顶点有相同的度.,例题,25/42,例题,例6.2.2 无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点度数均小于3，问G的阶数n为几？,解 本题的关键是应用握手定理.设除3度与4度顶点外，还有x个顶点v1,v2,vx，则 d(vi)2，i=1,2,x，于是得不等式 32 24+2x得 x 4,阶数 n 4+4+3=11.,26/42,例题,例6.2.3 9阶无向图G中，每个顶点的度数不是5就是6.证明G中至少有5个6度顶点或至少有6个5度顶点.,证 关键是利用握手定理的推论.方法一：穷举法设G中有x个5度顶点，则必有(9x)个6度顶点，由握手定理推论可知，(x,9x)只有5种可能：(0,9),(2,7),(4,5),(6,3),(8,1）它们都满足要求.方法二：反证法否则，由握手定理推论可知，“G至多有4个5度顶点并且至多有4个6度顶点”，这与G是 9 阶图矛盾.,27/42,定义6.2.10 设G=(V,E)，H=(U,F)是两个无向图.如果存在一个一一对应:VU，使得uvE当且仅当(u)(v)F，则称G与H同构，记为G H.,u1 u2 u3 u6 u5 u4,v1 v5 v2 v6 v4 v3,图的同构,28/42,定义6.2.10 设G1=,G2=为两个图，若存在双射函数f:V1V2,对于vi,vjV1,vi,vjE1 当且仅当f(vi),f(vj)E2并且vi,vj 与 f(vi),f(vj)的重数相同，则称G1与G2是同构的，记作G1G2.,图的同构,图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件，但它们全不是充分条件：边数相同，顶点数相同;度数序列相同;对应顶点的关联集的元素个数相同，等等.若破坏必要条件，则两图不同构.判断两个图同构是个难题.,29/42,设G=(V,E)，H=(U,F)是两个图，V=v1,v2,.,vp，U=u1,u2,.,up，p3.如果对每个i，G-viH-ui，则GH.,乌拉姆(S.M.Ulam)猜想,30/42,图的同构实例,图中(3)与(4)的度数列相同，它们同构吗？为什么？,图中，(1)与(2)不同构(度数列不同).,(3)(4),31/42,实例,例6.2.4 画出K4的所有非同构的生成子图.,32/42,6.3 路、圈、连通图,定义6.3.1 设G=(V,E)是一个图，G的一条通道是G的顶点和边的一个交错序列 v0,x1,v1,x2,v2,x3,.,vn-1,xn,vn,其中xi=vi-1vi，i=1,2,.,n，n称为通道的长，这样的通道常称为v0-vn通道，并简记为v0v1v2.vn.当v0=vn时，则称此通道为闭通道.,定义6.3.2 如果图中一条通道上的各边互不相同，则称此通道为图的迹，如果一条闭通道上的各边互不相同，则此闭通道称为闭迹.,定义6.3.3 如果图中一条通道上的各顶点互不相同，则称此通道为路或路径，如果闭通道上各顶点互不相同，则称此闭通道为圈，或回路.,33/42,例6.3.1 分析通道与闭通道，迹与闭迹，路与圈之间的关系.,v1v2v5v2v3是一条长为4的v1-v3的通道.,v1v2v5v4v2v3是一条长为5的迹.,v1v2v5v3是一条长为3的路.,v2v4v5v2是圈.,v2v4v5v2v3v2是闭通道，但不是闭迹.,例题,34/42,通道与回路的性质,定理6.3.1 在n 阶图G中，若从顶点vi 到vj（vivj）存在通道，则从vi 到 vj 存在长度小于或等于n1 的通道.推论1 在 n 阶图G中，若从顶点vi 到 vj（vivj）存在通道，则从vi 到vj 存在长度小于或等于n1的路.定理6.3.2 在一个n 阶图G中，若存在 vi 到自身的闭通道，则一定存在vi 到自身长度小于或等于 n 的闭通道.推论2 在一个n 阶图G中，若存在 vi 到自身的闭迹，则一定存在长度小于或等于n 的回路.,35/42,扩大路径法,任给一条路径，若此路径的始点或终点与路径外的某个顶点相邻，就将它扩到路径中来，继续这一过程，直到最后得到的路径的两个端点不与路径外的顶点相邻为止。最后总能得到一条极大路径.称如此构造一条极大路径的方法为“扩大路径法”。这是一种涉及路径和圈的构造证明中常用的方法.,设G=(V,E)为 n 阶无向图，为G中一条路径。若的始点和终点都不与路径外的顶点相邻，则称 是一条极大路径.,36/42,实例,由某条路径扩大出的极大路径不惟一，极大路径不一定是图中最长的路径.上图中，(1)中实线边所示的长为2的初始路径，(2),(3),(4)中实线边所示的都是它扩展成的极大路径.还能找到另外的极大路径吗？,37/42,定理6.3.3 设G=(V,E)是至少有一个顶点不是弧立顶点的图，如果uV，degu为偶数，则G中有圈.,证 令P是G中的一条最长的路(或极大路径)，P=v1v2.vn,degv12，除v2外，必有某个顶点u和v1相邻，那么u必在P中；,所以u必是v2,.,vn中的某个vi，i3，于是P=v1v2.viv1是G的一个圈.,如果u不在P中，P1=uv1v2.vn是一条更长的路;,通道与回路的性质,38/42,扩大路径法的应用,例6.3.2 设 G 为 n（n3）阶无向简单图，2，证明G 中存在长度+1 的圈.,证 设=v0v1vl 是由初始路径 0 用扩大路径法的得到的极大路径，则 l（为什么？）.因为v0 不与 外顶点相邻，又 d(v0)，因而在 上除 v1外，至少还存在 1个顶点与 v0 相邻.设 vx 是离 v0 最远的顶点，于是 v0v1vxv0 为 G 中长度+1 的圈.,39/42,定义6.3.4 设G=(V,E)是图，如果G中任两个不同顶点间至少有一条路联结，则称G是一个连通图.,连通图,定义6.3.5 图G的极大连通子图称为G的一个支或连通分支.,例6.3.3 考虑下图的连通分支数并理解极大的含义.,连通分支数是10，极大连通子图可理解为含有某一点的极大连通子图.,40/42,定理6.3.4 设G=(V,E)是一个图，在V上定义二元关系R如下:u,vV，uRv当且仅当u与v之间有一条路，则R是V上的等价关系，G的支就是关于R的每个等价类的导出子图。,证 定义uV，u与u间有长为0的路，所以R是自反的;,若u与v之间存在路，那么v与u之间也存在路，R是对称的;,若u与v之间存在路，v与w之间也存在路，则u与w之间也存在路，R是传递的;,所以R是等价关系。,wV，等价类w中各顶点间有路，故是连通子图.,uV，若uw，则u与w的每个顶点间无路，所以导出子图是G的极大连通子图;,因此是G的一个支.,连通图,41/42,定理6.3.5 设G=(V,E)是一个有p个顶点的图，若对G的任两个不相邻的顶点u和v有:degu+degvp-1，则G是连通的.,证 如果G不连通，则G至少有两个支，设G1=(V1,E1)是其中的一个支，其他各支构成的子图为G2=(V2,E2)；,设V1=n1，则V2=p-n1,在G1中，uV1，degun1-1;,在G2中，则vV2，有degvp-n1-1,degu+degv(n1-1)+(p-n1-1)=p-2,这与定理的假设矛盾，所以G是连通的。,连通图的充分条件,42/42,定理6.3.6 如果图G中的两个不同顶点u与v间有两条不同路联结，则G中有圈。,证 令P1和P2是G中两条不同的u-v路；,因为P1P2，所以存在P2的一条边x=u1v1不在P1上，或者存在P1的一条边x=u1v1不在P2上;,由P1和P2上的顶点和边构成的G的子图记为P1P2，,于是(P1P2)-x是G的一个连通子图.,所以(P1P2)-x中包含一条u1-v1路P，于是P+x=P+u1v1就是G的一个圈.,