第5 章图的基本概念 内容提要 ●图 1 无向图与有向图无向图G=,其中V≠.称为顶点集,其元素称为顶点, E 是V& V 的多重子集,称为边集,其元素称为无向边或边。有向图 D =,其中 V 同 无向图, E 是V×V 的多重子集,其元素称为有向边或边。有时用 G 泛指图(无向的或有向 的),但 D 只表示有向图。用V(V(E(E(分别表示G(的顶点集与边集。 G)(D))、G)(D)) D) 零图与平凡图只有顶点没有边的图称为零图,只有一个顶点的零图称为平凡图。 关联与相邻设图G=,v∈V,u,对于有向图,v>∈ E),称uv 为 e 的端点( 又称 u 为 e 的始点,称 e 与uv 是彼此 、对于有向边, v 为 e 的终点), 、 相关联的。无边关联的顶点称为孤立点。若 e 关联的两个顶点重合,则称 e 为环。若u≠ v, v) v( 则称 e 与u(的关联次数为1。若u=即 e 为环),则称 e 与 u 关联的次数为2。若顶 点u、 v 之间有边关联,则称 u 与 v 相邻。若两条边至少有一个公共端点(对于有向图,一条 边的终点是另一条边的始点),则称这两条边相邻。 顶点的度数称无向图或有向图的顶点 v 作为边的端点的次数之和为 v 的度数或 度,记作d()。称有向图的顶点 v 作为边的始点次数之和为 v 的出度, v), v 记作d+( v 作 为边的终点的次数之和为 v 的入度,记作d-(v)。显然,d(v)=d+(v)+d-(v)。称 max{d(v∈V(G)} 记作Δ(或Δ, in{v)|v∈V(为 G 的最 v)|为 G 的最大度, G) 称md(G)} 小度,记作δ(G)或δ。类似地定义有向图的最大度Δ( D )、最大出度Δ+( D )、最大入度 Δ-(D)、最小度δ(D)、最小出度δ+(D)、最小入度δ-(D)。 简单图对于无向图,若关联一对顶点的边多于一条,则称这些边为平行边。对于有向 图,若关联一对顶点的方向相同的边多于一条,则称这些边为平行边。平行边的条数称作重 数。既不含平行边,也不含环的图称为简单图。 完全图设 G 为 n 阶(无向简单图, 则称 G 为 n 个顶点) 若 G 中任何两个顶点均相邻, n 阶完全图,记作Kn 。设 D 为 n 阶有向简单图,若 D 中任何两个顶点之间均有两条方向相 反的边,则称 D 为 n 阶有向完全图。 正则图设 G 为 n 阶无向简单图,若 G 中每个顶点的度数均为k,则称 G 为 k 正则图。 子图设G=,G'=,若V'. V 且E'.E,则称G'为 G 的子图,记 作G'.G。若G'. G 且G'≠G,则称G'为 G 的真子图。若G'. G 且V'=V,则称G'为 G 的生成子图。若V1. V 且V1≠.,则称以V1 为顶点集、以两个端点均在V1 中的边为边集 的图为V1 的导出子图,记作G[]。若E1. E 且E1≠., 以E1 中边 V1 则称以E1 为边集、 关联的顶点为顶点集的图为E1 的导出子图,记作G[E1]。 ·72· 离散数学题解(第六版) 补图设G=为 G 的补图。 E>为 n 阶简单图,..u,v∈ V 且(v).E}, .. .. 图的同构设G1=、G2=为两个无向图,若存在双射函数f:V1→ V2,使得对于任意的u,v∈V,(u,v)∈E1 当且仅当( f (u), f (v))∈E2 且(u,v)与 (f( 主要定理 f(的重数相同, 记作G1.G2 u),v)) 则称G1 与G2 同构,。两个有向图的同构类似。 定理5.1(握手定理) 任何图(无向图或有向图)中所有顶点的度数之和等于边数的2 倍。任何有向图中所有顶点的入度之和等于所有顶点的出度之和等于边数。 推论任何图中奇度顶点的个数为偶数。 ●通路、回路、图的连通性 2 通路与回路设Γ=v0e1v1e2…elvl 为图 G 中的顶点与边的交替序列,若vi-1、vi 为ei 要求vi1是eii=l, 的端点(若 G 为有向图,- i 的始点,v是ei 的终点),1,2,…,则称 Γ 为一 条通路,、分别称为通路 Γ 的始点和终点,边的数目 l 称为 Γ 的长度。若通路的始点与 v0 vl 终点重合,则称为回路。所有边互不相同的通路称为简单通路。所有边互不相同的回路称 为简单回路。所有顶点互不相同的通路称为初级通路。所有顶点互不相同且所有边也互不 相同的回路称为初级回路或圈。有边重复出现的通路称为复杂通路。有边重复出现的回路 称为复杂回路。 顶点之间的连通关系在无向图 G 中,若顶点 u 到 v 有通路,则称 u 与 v 连通。规定 顶点与自身连通。顶点之间的连通关系是等价关系。在有向图 D 中,若 u 到 v 有通路,则 称 u 可达v。规定任何顶点与自身可达。 无向图的连通性若无向图 G 中任何两个顶点都连通,则称 G 是连通图。对于无向图 G,设V1,Vk 是顶点集 V 关于连通关系的等价类, V2,…,则称它们的导出子图为 G 的连通 分支, G 的连通分支数记作p(G)。 有向图的连通性若略去有向图 D 中各边的方向所得无向图是连通图,则称 D 是弱 连通图(或连通图); 若 D 中任何两个顶点至少一个可达另一个,则称 D 是单向连通图;若 D 中任何两个顶点都是相互可达的,则称 D 是强连通图。强连通图一定是单向连通图,单 向连通图一定是弱连通图。 点割集与割点设无向图 G =,V'.V,若p( G -V')>p(G), 且对任意的 V″.V均有p(G-″)=p(G), 则称V'为 G 的点割集。若Vv}是点割集,即称 v 为G ' , V'={ 的割点。这里,G-V'表示从 G 中去掉V'中所有顶点及其关联的边。 边割集及桥设无向图G=,E'.E,若p(G-E')>p(G), 且对任意的E″. E' , G- ″ )p(则称E'={是边割集, 均有p(E=G), '是 G 的边割集或割集。若Ee} 则称 e 为 G 中的桥或割边。这里,G-E'表示从 G 中去掉E'中所有的边。 ●图的矩阵表示 3 E>,v1,vE={e2,…,}, 无向图的关联矩阵设无向图G=,V = {v1,v2,…,vn },E = {e1,e2,…,em },令 mij = 1, vi 为ej 的始点 0, vi 与ej 不关联 -1, vi 为ej 的终点 ì . í .. .. 则称(mij)n×m 为D 的关联矩阵,记作M (D )。 有向图的可达矩阵 设有向图D =,V={v1,v2,…,vn},令 pij = 1, vi 可达vj 0, 否则{ 则称(pij)n×n 为D 的可达矩阵,记作P(D )。由于vi 可达vi,所以P(D )中pii =1,i=1, 2,…,n。 有向图的邻接矩阵 设有向图D =,V={v1,v2,…,vn}。令a(1) ij 为vi 邻接到 vj 的边的条数,则称(a(1) ij )n×n 为D 的邻接矩阵,记作A(D ),简记为A。记A 的l(l≥1)次 幂Al=(a(l) ij ),Br=(b(r) ij )=A+A2+…+Ar。 无向图的可达矩阵和邻接矩阵 与有向图的可达矩阵和邻接矩阵类似,实际上,只要把 每条无向边看作一对方向相反的有向边,就可以把无向图作为有向图的特殊情况。无向图 的可达矩阵和邻接矩阵都是对称的。 主要定理及推论 定理5.2 设A 为图G(有向图或无向图)的邻接矩阵,V ={v1,v2,…,vn },则Al(l≥ 1)中元素a(l) ij 为顶点vi 到vj 长度为l 的通路数,Σi,j a(l) ij 为G 中长度为l 的通路(含回路) 数,其中Σi a(l) ii 为G 中长度为l 的回路数。 推论 Br(r≥1)中元素b(r) ij 为G 中vi 到vj 长度小于或等于r 的通路数,Σi,j b(r) ij 为G 中长度小于或等于r 的通路(含回路)数,其中Σi b(r) ii 为G 中长度小于或等于r 的回路数。 ●4.最短路径问题 带权图 在图G=的每条边e=(vi,vj )(e=)上附加一个实数 w (e)(或记为wij),称w (e)(wij)为边e 的权,称G 为带权图,记作G=。设Γ 是G 中一条通路,称Γ 中所有边的权之和为Γ 的权,记作W (Γ)。 最短路径 设带权图G,u、v 为G 中两个顶点,从u 到v 所有通路中权最小的通路称 为u 到v 的最短路径,其权称作u 到v 的距离。 最短路径问题是求带权图中指定两点之间的最短路径及距离。Dijkstra标号法是最短 路径问题的常用有效算法,它适用于所有的权非负的情况。 ●5.项目网络图与关键路径 项目网络图是一个带权的有向图,用来描述项目中活动的完成时间及相互关系。项目 第5章 图的基本概念·73· ·74· 离散数学题解(第六版) 网络图中从始点到终点的最长路径称作关键路径。关键路径上的活动称作关键活动。通过 计算各顶点的最早开始时间和最晚完成时间找到关键路径及活动的相关数据。 ● 6 着色问题 着色给无环的无向图的每个顶点涂一种颜色,使得相邻的顶点涂不同的颜色,称作图 的点着色,简称着色。图的着色问题是如何用尽可能少的颜色给图着色。 ● 7 小结 本章概念较多,它们是图论中的基本概念。在学习和领会这些概念时,以下6点要特别 注意。 (1)牢记握手定理及其推论,并且能灵活应用。例如,在求解无向图(例如,已知边数 m 和一些顶点的度数,求另外一些顶点的度数), 求解无向树(见第7章)以及判断某些非负整 数序列能否充当图的度数序列等问题中都要用到握手定理或推论。在图论的许多证明题中 也要用到握手定理。 D)≤2( G)≤n- n 阶有向 (2)记住简单图的概念和性质,如 n 阶无向简单图 G 的最大度Δ(1, 简单图 D 的最大度Δ(n-1), 最大出度Δ+(D)≤n-1,最大入度Δ-(D)≤n-1。 在讨论给定的非负整数列能否充当无向图的度数序列时,都要用到以上性质。另外还要掌 握完全图、正则图、补图等概念。 (3)清楚图同构的概念。对一些比较简单的情况,会根据定义和必要条件判断两个图 是否同构。会画出4阶无向完全图K4 和3阶有向完全图的所有非同构的子图。 (4)清楚通路与回路的概念及其分类。初级通路(回路)都是简单通路(回路), 但反之 不真。长为1的圈是环,长为2的圈是两条平行边,只能在非简单图中出现。在简单图中初 级回路(圈)的长度都大于或等于3。 (5)在讨论图的连通性时,要特别注意有向连通图的分类及它们之间的关系,即强连通 的有向图必为单向连通的,单向连通的必为弱连通的,但反之都不真。 (6)在图的矩阵表示中,可以用邻接矩阵及各次幂,求图中的通路数及回路数。要注意,这 里不同的通路(回路)是按定义来区分的,而不是同构意义下区分的。例如,长度为l(的有 l≥1) 向圈在计算长度为l的回路时被计算l次,也就是说,不同始点(也是终点)的圈被看成是不同的。 习题 5.下列各组数中,哪些能构成无向图的度数序列? 哪些能构成无向简单图的度数序列? 1 (1)1,1,1,2,3; (2)2,2,2,2,2; (3)3,3,3,3; (4)1,2,3,4,5; (52)1,3,3,3。 2,3, 0,3, 5.设有向简单图 D 的度数序列为2,3,入数序列为0,2,试求 D 的出数序列。 第5章图的基本概念·75· 1,5.3 设 D 是4阶有向简单图,度数序列为3,3,或出度序列) 1, 1吗? 3,3。它的入度序列( 能为1, 5.4 设(d1,d2,…,dn )为一正整数序列,d1,d2,…,dn 互不相同,此序列能构成 n 阶 无向简单图的度数序列吗? 为什么? 5.下面各无向图中有几个顶点? 5 (1)16 条边,每个顶点都是2度顶点 。 (2)21 条边,3个4度顶点,其余的都是3度顶点 。 (3)24 条边,各顶点的度数是相同的 。 5.每个顶点的度数至少为3的图最多有几个顶点? 6 35 条边, 5.设 n 阶无向简单图 G 中,G)n-Δ(应为多少? 7 δ(=1,G) .. 5.8 一个n(阶无向简单图 G 中,已知 G 中有 r 个奇度顶点, G 的补图 n≥2) n 为奇数, G 中有几个奇度顶点? 5.9 设 D 是 n 阶有向简单图,'是 D 的子图, '的边数mn(1), D已知D'=n- D 的边数 m 为多少? 5.画出K4 的所有非同构的子图, 生成子图中有几个是 10 其中有几个是生成子图? 连通图? 11 设 G 为 n 阶简单图(无向图或有向图), G 为 G 的补图。若G... 补图 5 。 . K4 的生成子图中有几个非同构的自补图? ..G,则称 G 为自 5.画出3阶有向完全图所有非同构的子图,其中有几个是生成子图? 生成子图中 12 有几个是自补图? 5.设G1、G2、G3 均为4阶无向简单图,均有两条边,它们能彼此非同构吗? 为什么?13 已知 n 阶无向图 G 中有 m 条边,各顶点的度数均为3。又已知2在同 5.n-=m, 14 3 构的意义下, G 是唯一的吗? 若 G 为简单图,是否唯一? 5.在K6 的边上涂上红色或蓝色。证明对于任意一种随意的涂法,总存在红色K3 15 或蓝色K3。 试寻找3个4阶有向简单图D1、、。使得D1 为强连通图;D2 为单向连通 5.16 D2 D3 图,但不是强连通的;而D3 为弱连通图,但不是单向连通的,更不是强连通的。 5.设V'和E'分别为无向连通图 G 的点割集和边割集。G-E'的连通分支个数一 17 定为多少?G-V'的连通分支数也是定数吗? 5.有向图 D 如图5-1所示。求 D 中在定义意义下长度为4的通路总数,并指出其 18 中有几条是回路? 又有几条是v3 到v4 的通路? 5.求图52中从 b 到其余各顶点的最短路径和距离。 19 图5- 1 图5- 2 ·76· 离散数学题解(第六版) 5.某工程项目有13 个工序,工序之间的关系和完成时间如表5-1所示。 20 表5- 1 工序A B C D E F G H I J K L M 紧前工序---A A,B A,B A,B C,G D,E,F D,E D,E H,J I,L 时间/天3 2 4 4 4 4 2 5 3 3 6 1 1 (1)画出项目网络图。 (2)求各工序的最早开始时间、最早完成时间、最晚开始时间、最晚完成时间及缓冲 时间。 (3)求关键路径、关键工序及项目的工期。 5.计算机系期末要安排7门公共课的考试,课程编号为1~7。下列每对课程有学 21 生同时选修:1和2,1和3,1和4,1和7,2和3,2和4,2和5,2和7,3和4,3和6,3和7,4 和5,4和6,5和6,5和7,6和7。这7门课的考试至少要安排在几个不同的时间段?给出 一个安排方案。 5.假设两家电视台相距不超过150km 就不能使用相同的频率,表5-2列出6家电 22 视台之间的距离,它们至少需要使用多少个不同的频率? 如何分配? 表5- 2 (单位:km) 2 3 4 5 6 1 85 175 200 50 100 2 125 175 100 160 3 100 200 250 4 210 220 5 100 题5.~题5. 2325 的要求是从供选择的答案中选出应填入叙述中的方框□内的正确 答案。 5.设 n 阶图 G 中有 m 条边,每个顶点的度数不是 k 就是k+1,若 G 中有Nk 个k 23 度顶点和Nk+1 个(度顶点,则Nk k+1) 为A。 供选择的答案 A:①n/2; ②nk; ③n(k+1)211 题。 k+1)。 k+1); ④n(-m; ⑤n(- m 5.在图5-3的5个图中A是自补图。关于自补图的定义见5. 24 图5- 3 第5章图的基本概念·77· 供选择的答案 A:①(a),(b); ②(c),(d); ③(a),(c); ④(b),(e)。 5.在图5-4所示的6个图中,强连通图为A,单向连通图为B。 25 图5- 4 供选择的答案 A、B:①(a),(c); ②(d),(f); ③(a),(b),(d),(f); b),(e),(e),( ④(a),(e),( f)。 习题解答 5.1 (1)、(2)、(3)、(5)都能构成无向图的度数序列,其中除(5)外又都能构成无向简单 图的度数序列。 n 分析1° 非负整数列d1,d2,…,dn 能构成无向图的度数序列当且仅当Σdi 为偶 = d2,…,1)、(3)、(中分别有4个、、(i) 4个奇 数,所以,它们都能构成无向图的度数序列。当然,所对应的无向图很可能是非简单图。而 数,即d1,dn 中的奇数为偶数个。(2)、(5) 0个4个、(1) (4)中有3个奇数,因而它不能构成无向图度数序列;否则就违背了握手定理的推论。 2° (5)虽然能构成无向图的度数序列,但不能构成无向简单图的度数序列。假若存在 无向简单图G,以1,3,3,3为度数序列。不妨设 G 中顶点为v1,v2,v3,v4,且d(v1)=1, d(d(3。于是,、、v4 中的一个相邻。设v1 与v2 相邻。 d(v1 只能与v2 v2)=v3)=v4)=v3 这样一来,除v2 能达到3度外,、v4 都达不到3度,矛盾。 在图5-图55(以(为度数序列, -b) 2) 图5-5 v3 5所示的4个图中, -a) 1) 图55(以(为度数序列, (以(为度数序列, -d)5) 非简单图)。 c) 3) 图55(以(为度数序列( 图5- 5 5.由于d(=v)+d-v), 所以d+(d(-)。已知 D 的度数序列 2 v)d+((v)=v)d-( 为2,2,3,3,入度序列为0,0,2,3,故 D 的出度序列为2,2,1,0。请读(v) 者画出一个有向图,以 2,2,3为度数序列,0,3为入度序列,2,0为出度序列。 3,0,2,2,1, 3 D 的入度序列不可能为1,1,1,1;否则,必有出度序列为2,2,2,2。于是,入度之和 5. 为4,出度之和为8,两者不相等,这违背握手定理。类似地,1,1,1,1也不能为D 的出度序列。 5.4 不能。n 阶无向简单图的最大度Δ≤n-1。而n 个彼此不同的正整数中至少有 一个大于或等于n,因而这n 个数不能构成无向简单图的度数序列。 5.5 (1)边数m =16,设顶点数为n。根据握手定理可知 2m =32=Σn i=1 d(vi)=2n 所以,n=16。 (2)边数m =21,设3度顶点个数为x,由握手定理有 2m =42=3×4+3x 由此方程解出x=10,于是顶点数n=3+10=13。 (3)设有n 个顶点,已知边数m =24,每个顶点的度数均为k,由握手定理有 2×24=48=nk 方程的正整数解有下面10种情况。 ①n=1,k=48。 ②n=2,k=24。 ③n=3,k=16。 ④n=4,k=12。 ⑤n=6,k=8。 ⑥n=8,k=6。 ⑦n=12,k=4。 ⑧n=16,k=3。 ⑨n=24,k=2。 ......n=48,k=1。 其中,①是由一个顶点和24个环构成的图。⑩是由24个K2 构成的图。其余有多个非同 构的图,其中很多是非简单图,也有简单图。 分析 由于n 阶无向简单图G 中,Δ(G)≤n-1,所以①~⑤所对应的图不可能有简单 图。⑥~⑨既有简单图,也有非简单图,读者可以画出若干非同构的图。 5.6 设G 为n 阶图,由握手定理可知 70=2×35≥3n 得 n ≤ 70 3 =23 其中,.x.为不大于x 的最大整数。例如.2.=2,.2.5.=2。 5.7 Δ(G)≥δ(G)=n-1。由于G 为简单图,又有Δ(G)≤n-1,因而Δ(G)=n-1。 于是,Δ(G)=δ(G)=n-1,即G 的所有顶点的度数为n-1,这是n 阶完全图Kn 。 5.8 由补图的定义,对每个顶点v 有 dG (v)+d..G (v)=n -1 其中,dG (v)表示v 在G 中的度数;d..G (v)表示v 在..G 中的度数。由于n 是奇数,n-1为偶 ·78· 离散数学题解(第六版) 数,所以dG (v)与d..G (v)同为奇数或同为偶数,因而若G 有r 个奇度顶点,则..G 也有r 个奇 度顶点。 5.9 显然,m'≤m 。而n 阶有向简单图的边数m ≤n(n-1),所以 n(n -1)=m' ≤m ≤n(n -1) 得m =n(n-1),这说明D 为n 阶完全有向图,且D'=D 。 5.10 图5-6给出了K4 的全部18个非同构的子图,其中有11个生成子图(⑧~......), 生成子图中有6个是连通的(......,......,......,......,......,......)。图5-6中n、m 分别为顶点数和边数。 m n 0 1 2 3 4 5 6 1 ① 2 ② ③ 3 ④ ⑤ ⑥ ⑦ 4︵ 生成子图︶ ⑧ ⑨ ⑩ ...... ...... ...... ...... ...... ...... ...... ...... 图 5-6 5.11 K4 的生成子图中只有一个(图5-6......)是自补图。 分析 设K4 的子图G 有m 条边,则G 的补图有6-m 条边。如果G 是自补图,则必 有m =6-m ,得m =3。于是,只需要考虑图5-6中的......、......和......。......与......互为补图且非同 构,所以它们不是自补图。而......与自己的补图同构,所以......是自补图。 5.12 3阶有向完全图共有20个非同构的子图,如图5-7所示,其中⑤~......为生成子 图,生成子图中⑧、......、......、......为自补图。 分析 设D 为3个顶点m 条边的简单有向图,它的补图有6-m 条边。若D 是自补 图,则m =6-m ,得m =3。于是,只需考虑图5-7中的⑧、......、......和......4个图,它们都与自己 的补图同构,所以都是自补图。 5.13 不能。 分析 只有两个非同构的4阶两条边的简单无向图,如图5-6中......与......所示。由鸽巢 原理可知,G1、G2、G3 中至少有两个是同构的。 鸽巢原理 m 只鸽子飞进n 个鸽巢,则必有一个鸽巢飞入至少 m n 只鸽子。这里éx ù表 第5章 图的基本概念·79· 示不小于x 的最小整数。例如,é2ù=2,é2.5ù=3。 m n 0 1 2 3 4 5 6 1 ① 2 ② ③ ④ 3︵ 生成子图︶ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... 图 5-7 5.14 G 是不唯一的,即使G 是简单图也不唯一。 分析 由握手定理有2m =3n。又由已知2n-3=m ,解得n=6,m =9。 6个顶点、9条边、每个顶点的度数都是3的非同构的简单图有两个,如图5-8所示。注 意在图5-8(a)中不存在3个彼此相邻的顶点,而在图5-8(b)中存在3个彼此相邻的顶点, 因而它们不同构。此外还有多个非同构的非简单图,请读者自己画出几个。 5.15 设K6 的顶点为v1,v2,…,v6,讨论v1 所关联的边。由鸽巢原理(见5.13题)可 知,与v1 关联的5条边中至少有3条边颜色相同。不妨设有3条红色边,它们分别关联v2、 v4、v6,如图5-9(a)所示。若v2、v4、v6 构成的K3 中还有红色边,则这条边与前面3条边中的 两条构成一个红色K3。如边(v2,v4)为红色,则v1、v2、v4 构成红色K3,如图5-9(b)所示。若 v2、v4、v6 构成的K3 各边都是蓝色(用虚线表示),则这是一个蓝色的K3,如图5-9(c)所示。 图 5-8 图 5-9 ·80· 离散数学题解(第六版)