第第6 6章章 图图1第第6 6章章 图图6.1 图的基本概念图的基本概念6.2 图的连通性图的连通性6.3 图的矩阵表示图的矩阵表示6.4 几种特殊的图几种特殊的图26.1 图的基本概念图的基本概念6.1.1 无向图与有向图无向图与有向图6.1.2 顶点的度数与握手定理顶点的度数与握手定理6.1.3 简单图、完全图、正则图、圈图、简单图、完全图、正则图、圈图、 轮图、方体图轮图、方体图6.1.4 子图、补图子图、补图6.1.5 图的同构图的同构3无序对与多重集合无序对与多重集合无序对无序对: 2个元素构成的集合个元素构成的集合, 记作记作(a,b)无序积无序积: A B=(x,y) | x A y B例如例如 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无向图无向图定义定义6.1 无向图无向图G=, 其中其中V称为称为顶点集顶点集, 其元素称为其元素称为顶点顶点或或结点结点; E是是V V的多重子集的多重子集, 称为称为边集边集, 其元素称为其元素称为无向边无向边，简称，简称边边. 有时用有时用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有向图有向图定义定义6.2 有向图有向图D=, 其中其中V称为称为顶点集顶点集, 其元素称为其元素称为顶点顶点或或结点结点; E是是V V的多重子集的多重子集, 称为称为边集边集, 其元素称为其元素称为有有向边向边，简称，简称边边. 有时用有时用V(D)和和E(D)分别表示分别表示V和和E 有限图有限图: V, E都是有穷集合的图都是有穷集合的图n 阶图阶图: n个顶点的图个顶点的图零图零图: E=的图的图平凡图平凡图: 1 阶零图阶零图e1e2e3e4e5e6e7dabc6顶点和边的关联与相邻顶点和边的关联与相邻设设无无向向图图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的的端端点点, 则则称称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顶点的度数顶点的度数设设G=为无向图为无向图, v V,v的度数的度数(度度) d(v): v作为边的端点次数之和作为边的端点次数之和 悬挂顶点悬挂顶点: 度数为度数为1的顶点的顶点悬挂边悬挂边: 与悬挂顶点关联的边与悬挂顶点关联的边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顶点的度数顶点的度数(续续)设设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), (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握手定理握手定理定理定理6.1 任何图任何图(无向图和有向图无向图和有向图)的所有顶点度数之和都的所有顶点度数之和都等于边数的等于边数的2倍倍.证证 图中每条边图中每条边(包括环包括环)均有两个端点均有两个端点, 所以在计算各顶点所以在计算各顶点度数之和时度数之和时, 每条边均提供每条边均提供2度度, m条边共提供条边共提供2m度度.推论推论 任何图任何图(无向图和有向图无向图和有向图)都有偶数个奇度顶点都有偶数个奇度顶点定理定理6.2 有向图所有顶点的入度之和等于出度之和等于边数有向图所有顶点的入度之和等于出度之和等于边数证证 每条边恰好提供每条边恰好提供1个入度和个入度和1个出度个出度10图的度数列图的度数列设无向图设无向图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)如右图度数列如右图度数列:5,3,3,3 出度列出度列:4,0,2,1 入度列入度列:1,3,1,2e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc11实例实例(2) 能能例例1 下述下述2组数能成为无向图的度数列吗组数能成为无向图的度数列吗?(1) 3,3,3,4; (2) 1,2,2,3解解 (1) 不可能不可能. . 有奇数个奇数有奇数个奇数. .12实例实例例例2 已知图已知图G有有10条边条边, 4个个3度顶点度顶点, 其余顶点的度数均小其余顶点的度数均小于等于于等于2, 问问G至少有多少个顶点至少有多少个顶点? 解解 设设G有有n个顶点个顶点. 由握手定理由握手定理, 4 3+2 (n-4) 2 10解得解得 n 8例例3 已知已知5阶有向图的度数列和出度列分别为阶有向图的度数列和出度列分别为3,3,2,3,3和和1,2,1,2,1, 求它的入度列求它的入度列解解 2,1,1,1,213实例实例例例4 证明不存在具有奇数个面且每个面都具有奇数条棱的证明不存在具有奇数个面且每个面都具有奇数条棱的多面体多面体.证证 用反证法用反证法. 假设存在这样的多面体假设存在这样的多面体, 作无向图作无向图G=,其中其中 V=v | v为多面体的面为多面体的面, E=(u,v) | u,v V u与与v有公共的棱有公共的棱 u v.根据假设根据假设, |V|为奇数且为奇数且 v V, d(v)为奇数为奇数. 这与握手定理这与握手定理的推论矛盾的推论矛盾.14实例实例例例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简单图简单图定义定义6.4 在无向图中在无向图中, 关联同一对顶点的关联同一对顶点的2条或条或2条以上的条以上的边边, 称为称为平行边平行边, 平行边的条数称为平行边的条数称为重数重数在有向图中在有向图中, 具有相同始点和终点的具有相同始点和终点的2条或条或2条以上的边称条以上的边称为为有向平行边有向平行边, 简称简称平行边平行边, 平行边的条数称为平行边的条数称为重数重数含平行边的图称为含平行边的图称为多重图多重图既无平行边也无环的图称为既无平行边也无环的图称为简单图简单图16实例实例e5和和e6 是平行边是平行边重数为重数为2不是简单图不是简单图e2和和e3 是平行边是平行边,重数为重数为2e6和和e7 不是平行边不是平行边不是简单图不是简单图e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc17完全图与正则图完全图与正则图无向完全图无向完全图: 每对顶点之间都有一条边的无向简单图每对顶点之间都有一条边的无向简单图.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/218实例实例K3K53阶有向完全图阶有向完全图2正则图正则图4正则图正则图 3正则图正则图彼得松图彼得松图19圈图与轮图圈图与轮图无向圈图无向圈图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方体图方体图n方体图方体图Qn=是是2n阶无向简单图阶无向简单图, 其中其中 V=v|v=a1a2an, ai=0,1, i=1,2,n E=(u,v)| u,v V u与与v恰好有一位数字不同恰好有一位数字不同. 0100011011000 001010 01111010011110121子图子图定定义义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 的导出子图的导出子图, 记作记作GV 设设EE且且E, 以以E 为边集为边集, 以以E 中边关联的所中边关联的所有顶点为有顶点为顶点集的顶点集的G的子图称作的子图称作E 的导出子图的导出子图, 记作记作GE 22实例实例(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补图补图定义定义6.11 设设G=为为n阶无向简单图阶无向简单图, 记记 =V V -E, 称称 为为G的的补图补图24图的同构图的同构定义定义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实例实例26实例实例例例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实例实例例例7 画出画出3个以个以1,1,1,2,2,3为度数列的非同构的无向简单图为度数列的非同构的无向简单图28