1、第第6 6章章 图图1/281第第6 6章章 图图6.1 图基本概念图基本概念6.2 图连通性图连通性6.3 图矩阵表示图矩阵表示6.4 几个特殊图几个特殊图2/2826.1 图基本概念图基本概念6.1.1 无向图与有向图无向图与有向图6.1.2 顶点度数与握手定理顶点度数与握手定理6.1.3 简单图、完全图、正则图、圈图、简单图、完全图、正则图、圈图、轮图、方体图轮图、方体图6.1.4 子图、补图子图、补图6.1.5 图同构图同构3/283无序对与多重集合无序对与多重集合无序对无序对:2个元素组成集合个元素组成集合,记作记作(a,b)无序积无序积:A B=(x,y)|x A y B比如比如
2、A=a,b,c,B=1,2 A B=B A=(a,1),(b,1),(c,1),(a,2),(b,2),(c,2)A A=(a,a),(a,b),(a,c),(b,b),(b,c),(c,c)B B=(1,1),(1,2),(2,2)多重集合多重集合:元素能够重复出现集合元素能够重复出现集合重复度重复度:元素在多重集合中出现次数元素在多重集合中出现次数比如比如 S=a,b,b,c,c,c,a,b,c 重复度依次为重复度依次为1,2,34/284无向图无向图定义定义6.1 无向图无向图G=,其中其中V称为称为顶点集顶点集,其元素称为其元素称为顶点顶点或或结点结点;E是是V V多重子集多重子集,称
3、为称为边集边集,其元素称为其元素称为无向边无向边，简称，简称边边.有时用有时用V(G)和和E(G)分别表示分别表示V和和E比如比如,G=如图所表示如图所表示,其中其中V=v1,v2,v5 E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)e1e2e3e4e5e6e7v5v1v2v3v45/285有向图有向图定义定义6.2 有向图有向图D=,其中其中V称为称为顶点集顶点集,其元素称为其元素称为顶点顶点或或结点结点;E是是V V多重子集多重子集,称为称为边集边集,其元素称为其元素称为有有向边向边，简称，简称边边.有时用有时用V(D)和
4、和E(D)分别表示分别表示V和和E 有限图有限图:V,E都是有穷集合图都是有穷集合图n 阶图阶图:n个顶点图个顶点图零图零图:E=图图平凡图平凡图:1 阶零图阶零图e1e2e3e4e5e6e7dabc6/286顶点和边关联与相邻顶点和边关联与相邻设无向图设无向图G=,ek=(vi,vj)E,称称vi,vj为为ek端点端点,ek与与vi(vj)关联关联.若若vi=vj,则称则称ek为为环环.无边关联顶点称作无边关联顶点称作孤立孤立点点.若若vi vj,则称则称ek与与vi(vj)关联次数为关联次数为1;若若vi=vj,则称则称ek与与vi 关联次数为关联次数为2;若若vi不是边不是边e端点端点,
5、则称则称e与与vi 关联关联次数为次数为0.设设vi,vj V,ek,el E,若若(vi,vj)E,则则称称vi,vj相相邻邻;若若ek,el有有一一个个公共端点公共端点,则称则称ek,el相邻相邻.对有向图有类似定义对有向图有类似定义.设设ek=vi,vj 是有向图一条边是有向图一条边,又称又称vi是是ek始点始点,vj是是ek终点终点,vi邻接到邻接到vj,vj邻接于邻接于vi7/287顶点度数顶点度数设设G=为无向图为无向图,v V,v度数度数(度度)d(v):v作为边端点次数之和作为边端点次数之和 悬挂顶点悬挂顶点:度数为度数为1顶点顶点悬挂边悬挂边:与悬挂顶点关联边与悬挂顶点关联边
6、G最大度最大度(G)=maxd(v)|v VG最小度最小度(G)=mind(v)|v V比如比如 d(v5)=3,d(v2)=4,d(v1)=4,(G)=4,(G)=1,v4是悬挂顶点是悬挂顶点,e7是悬挂边是悬挂边,e1是环是环e1e2e3e4e5e6e7v5v1v2v3v48/288顶点度数顶点度数(续续)设设D=为有向图为有向图,v V,v出度出度d+(v):v作为边始点次数之和作为边始点次数之和v入度入度d(v):v作为边终点次数之和作为边终点次数之和v度数度数(度度)d(v):v作为边端点次数之和作为边端点次数之和 d(v)=d+(v)+d-(v)+(D),+(D),(D),(D),
7、(D),(D)悬挂顶点悬挂顶点,悬挂边悬挂边比如比如 d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,+=4,+=0,=3,=1,=5,=3e1e2e3e4e5e6e7dabc9/289握手定理握手定理定理定理6.1 任何图任何图(无向图和有向图无向图和有向图)全部顶点度数之和都全部顶点度数之和都等于边数等于边数2倍倍.证证 图中每条边图中每条边(包含环包含环)都有两个端点都有两个端点,所以在计算各顶点所以在计算各顶点度数之和时度数之和时,每条边均提供每条边均提供2度度,m条边共提供条边共提供2m度度.推论推论 任何图任何图(无向图和有向图无向图和有
8、向图)都有偶数个奇度顶点都有偶数个奇度顶点定理定理6.2 有向图全部顶点入度之和等于出度之和等于边数有向图全部顶点入度之和等于出度之和等于边数证证 每条边恰好提供每条边恰好提供1个入度和个入度和1个出度个出度10/2810图度数列图度数列设无向图设无向图G顶点集顶点集V=v1,v2,vnG度数列度数列:d(v1),d(v2),d(vn)如右图度数列如右图度数列:4,4,2,1,3设有向图设有向图D顶点集顶点集V=v1,v2,vnD度数列度数列:d(v1),d(v2),d(vn)D出度列出度列:d+(v1),d+(v2),d+(vn)D入度列入度列:d(v1),d(v2),d(vn)如右图度数列
9、如右图度数列:5,3,3,3 出度列出度列:4,0,2,1 入度列入度列:1,3,1,2e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc11/2811实例实例(2)能能例例1 下述下述2组数能成为无向图度数列吗组数能成为无向图度数列吗?(1)3,3,3,4;(2)1,2,2,3解解(1)不可能不可能.有奇数个奇数有奇数个奇数.12/2812实例实例例例2 已知图已知图G有有10条边条边,4个个3度顶点度顶点,其余顶点度数均小其余顶点度数均小于等于于等于2,问问G最少有多少个顶点最少有多少个顶点?解解 设设G有有n个顶点个顶点.由握手定理由握手定理,4 3+2
10、(n-4)2 10解得解得 n 8例例3 已知已知5阶有向图度数列和出度列分别为阶有向图度数列和出度列分别为3,3,2,3,3和和1,2,1,2,1,求它入度列求它入度列解解 2,1,1,1,213/2813实例实例例例4 证实不存在含有奇数个面且每个面都含有奇数条棱证实不存在含有奇数个面且每个面都含有奇数条棱多面体多面体.证证 用反证法用反证法.假设存在这么多面体假设存在这么多面体,作无向图作无向图G=,其中其中 V=v|v为多面体面为多面体面,E=(u,v)|u,v V u与与v有公共棱有公共棱 u v.依据假设依据假设,|V|为奇数且为奇数且 v V,d(v)为奇数为奇数.这与握手定理这
11、与握手定理推论矛盾推论矛盾.14/2814实例实例例例5 设设9阶无向图每个顶点度数为阶无向图每个顶点度数为5或或6,证实它最少有证实它最少有5个个6度顶点或者最少有度顶点或者最少有6个个5度顶点度顶点.证证 讨论全部可能情况讨论全部可能情况.设有设有a个个5度顶点和度顶点和b个个6度顶点度顶点(1)a=0,b=9;(2)a=2,b=7;(3)a=4,b=5;(4)a=6,b=3;(5)a=8,b=1(1)(3)最少最少5个个6度顶点度顶点,(4)和和(5)最少最少6个个5度顶点度顶点方法二方法二 假设假设b9-5=4.由握手定理推论由握手定理推论,a 615/2815简单图简单图定义定义6.
12、4 在无向图中在无向图中,关联同一对顶点关联同一对顶点2条或条或2条以上条以上边边,称为称为平行边平行边,平行边条数称为平行边条数称为重数重数在有向图中在有向图中,含有相同始点和终点含有相同始点和终点2条或条或2条以上边称条以上边称为为有向平行边有向平行边,简称简称平行边平行边,平行边条数称为平行边条数称为重数重数含平行边图称为含平行边图称为多重图多重图既无平行边也无环图称为既无平行边也无环图称为简单图简单图16/2816实例实例e5和和e6 是平行边是平行边重数为重数为2不是简单图不是简单图e2和和e3 是平行边是平行边,重数为重数为2e6和和e7 不是平行边不是平行边不是简单图不是简单图e
13、1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc17/2817完全图与正则图完全图与正则图无向完全图无向完全图:每对顶点之间都有一条边无向简单图每对顶点之间都有一条边无向简单图.n阶无向完全图记作阶无向完全图记作Kn,顶点数顶点数n,边数边数m=n(n-1)/2,=n-1有有向向完完全全图图:每每对对顶顶点点之之间间都都有有两两条条方方向向相相反反边边有有向向简简单单图图.顶点数顶点数n,边数边数m=n(n-1),+=+=-=-=n-1,=2(n-1)k-正则图正则图:每个顶点度数均为每个顶点度数均为k无向简单图无向简单图顶点数顶点数n,边数边数m=kn/21
14、8/2818实例实例K3K53阶有向完全图阶有向完全图2正则图正则图4正则图正则图 3正则图正则图彼得松图彼得松图19/2819圈图与轮图圈图与轮图无向圈图无向圈图Cn=,其中其中V=v1,v2,vn,E=(v1,v2),(v2,v3),(vn-1,vn),(vn,v1),n 3有向圈图有向圈图Cn=,其中其中V=v1,v2,vn,E=,n 3轮图轮图Wn:无向圈图无向圈图Cn-1内放一个顶点内放一个顶点,且与圈图每个顶点且与圈图每个顶点之间恰有一条边之间恰有一条边,n 420/2820方体图方体图n方体图方体图Qn=是是2n阶无向简单图阶无向简单图,其中其中 V=v|v=a1a2an,ai=
15、0,1,i=1,2,n E=(u,v)|u,v V u与与v恰好有一位数字不一样恰好有一位数字不一样.0100011011000 001010 01111010011110121/2821子图子图定定义义6.10 设设G=,G=是是2个个图图(同同为为无无向向图图,或或同为有向图同为有向图)若若VV且且EE,则则称称G 为为G子子图图,G为为G 母母图图,记记作作GG若若GG 且且V=V,则称则称G 为为G生成子图生成子图若若VV或或EE,称称G 为为G真子图真子图设设VV且且V,以以V 为为顶顶点点集集,以以两两端端点点都都在在V 中全部中全部边为边集边为边集G子图称作子图称作V 导出子图导
16、出子图,记作记作GV 设设EE且且E,以以E 为边集为边集,以以E 中边关联全部中边关联全部顶点为顶点为顶点集顶点集G子图称作子图称作E 导出子图导出子图,记作记作GE 22/2822实例实例(1),(2),(3)是是(1)子图子图,(2),(3)是真子图是真子图,(1)是母图是母图.(1),(3)是是(1)生成子图生成子图.(2)是是d,e,f 导出子图导出子图,也是也是e5,e6,e7导出子图导出子图.(3)是是e1,e3,e5,e7导出子图导出子图aabbccdddeee f f f e1 e1 e2 e3 e3 e4 e5 e5 e5 e6 e6 e7 e7 e7(1)(2)(3)23
17、/2823补图补图定义定义6.11 设设G=为为n阶无向简单图阶无向简单图,记记 =V V-E,称称 为为G补图补图24/2824图同构图同构定义定义6.12 设设G1=,G2=为两个无向图为两个无向图(有向有向图图),若存在双射函数若存在双射函数 f:V1V2,使得对于任意使得对于任意vi,vj V1,(vi,vj)E1(E1)当且仅当当且仅当 (f(vi),f(vj)E2(E2)而且而且(vi,vj)()与与(f(vi),f(vj)()重数相同，重数相同，则称则称G1与与G2是是同构同构，记作，记作G1 G2.25/2825实例实例26/2826实例实例例例6 画出画出4阶阶3条边全部非同构无向简单图条边全部非同构无向简单图解解 总度数为总度数为6,分配给分配给4个顶点个顶点,最大度为最大度为3,且奇度顶点数且奇度顶点数为偶数为偶数,有下述有下述3个度数列个度数列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.1,1,1,31,1,2,20,2,2,227/2827实例实例例例7 画出画出3个以个以1,1,1,2,2,3为度数列非同构无向简单图为度数列非同构无向简单图28/2828
