离散数学习题解答第6部分(图论)

离散数学习题解答 习题六 （第六章 图论）

1．从日常生活中列举出三个例子，并由这些例子自然地导出两个无向图及一个向图。

[解] ①用V代表全国城市的集合，E代表各城市间的铁路线的集合，则所成之图G=（V，E）是全国铁路交通图。是一个无向图。

②V用代表中国象棋盘中的格子点集，E代表任两个相邻小方格的对角线的集合，则所成之图G=（V，E）是中国象棋中“马”所能走的路线图。是一个无向图。

③用V代表FORTRAN程序的块集合，E代表任两个程序块之间的调用关系，则所成之图G+（V，E）是FORTRAN程序的调用关系图。是一个有向图。 2．画出下左图的补图。

[解] 左图的补图如右图所示。

3．证明下面两图同构。

v2

a 图G′

v3 图G

v4

[证] 存在双射函数 :V→V′及双射函数 : E→E′

(v1)=v1′ (v2)=v2′ (v3)=v3′ (v4)=v4′ (v5)=v5′ (v6)=v6′

(v1，v2)=(v1′，v2′) (v2，v3)=(v2′，v3′) (v3，v4)=(v3′，v4′) (v4，v5)=(v4′，v5) (v5，v6)=(v5′，v6′) (v6，v1)=(v6′，v1′) (v1，v4)=(v1′，v4′) (v2，v5)=(v2′，v5′) (v3，v6)=(v3′，v6′)

显然使下式成立：

(vi，vj)=(vi,vj′) (vi)=v i′∧ (vj)=vj′ (1≤i·j≤6) 于是图G与图G′同构。

4．证明（a），（b）中的两个图都是不同构的。

图G中有一个长度为4的圈v1v2v6v5v1，其各顶点的度均为3点，而在图G′中却没有这样的圈，因为它中的四个度为3的顶点v1 ，v5 ，v7 ，v3 不成长度的4的圈。

图G中′有四个二度结点，v6 ，v8 ，v4 ，它们每个都和两个三度结点相邻，而G中一个区样的结点都没有。

在（b）中，图G 中有一2度结点v3 ，它相邻的两个项点v2 ，v4 的度均为4，而在图G中却没有这样的点。

G

G′

G

G′

v3

v4

5．一个图若同构于它的外图，则称此图为自补图。在满足下列条件的无向简单图中： 1) 给出一个五个结点的自补图；

2)有三个或一结点的自补图吗？为什么？

3）证明：若一个图为自补图，则它对应的完全图的边数不清必然为偶数。 [解] 1) 五个结点的自补图如左图G所示

同构函数 : V→V及 : E→E如下： (a)=a (b)=c (c)=e (d)=b (e)=d

(a，b)=(a，c) (b，c)=(c，e) (c，d)=(e，d) (d，e)=(b，d) (e，a)=(d，a)

G

G

e

b

a

e

2)（a）没有三个结点的自补图。因为三个结点的完备图的边数为3(3 1)=3

2为奇数，所以由下面3)的结论，不可能有自补图。

（b）有五个结点的自补图。1）中的例子即是一个五个结点的自补图。 3）证：一个图是一个自补图，则它对应的完全图的边数必为偶数。

因为若一个图G是自补图，则G∪G=对应的完全图，而且E∩E=φ，G现G同构，因此它们的边数相等，即|E|=|E|，因此对应的完全图的边数|E*|=|E|+|E|=2|E|，是偶数。

实际上，n个项点（n＞3）的自补图G，由于其对应的完全图的边数|E*|=

n(n 1)n(n 1)

，因此有=2|E|，为偶数。这里n≥4。对于所有大于或等22

于4的正整数，都可表达成n=4k，4k+1，4k+2，4k+3的形式，这里k=1，2， 。

其中只有n=4k，4k+1，才能使4k或4k+1形式，（k∈N）

n(n 1)

为偶数，所以自补图的项点数只能是2

6．证明在任何两个或两个以上人的组内，总存在两个人在组内有相同个数的朋友。

[证] 令上述组内的人的集合为图G的项点集V，若两人互相是朋友，则其间联以一边。所得之图G是组内人员的朋友关系图。显然图G是简单图，图中项点的度恰表示该人在组内朋友的个数，利用图G，上述问题就抽象成如下的图认论问题：在简单图G中，若|V|≥2，则在G中恒存在着两个项点，v1，v2∈V，使得它们的度相等，即deg(v1)=deg(v2)。其证明如下：

若存在着一个项点v∈V，使得deg(v)=0，则图G中各项点的度最大不超过n-2。因此n个项点的度在集合{0，1，2， ，n-2}里取值，而这个集合只有n-1个元素，因此，根据鸽笼原理，必有两个项点的度相同。

若不存在一个度为零的项点，则图G中各项点的度最大不超过n-1。因此n个项点的度在集合{1，2， ，n-1}中取值，这个集合只有n-1个元素，因此，根据鸽笼原理，必有两具项点的度相同。

7．设图G的图示如右所示： 1) 找出从A到F的所有初级路；

2）找出从A到F的所有简单路； 3）求由A到F的距离。 [解] 1）从A到F的初级路有7条

E

P1 : (A，B，C，F)，P2 (A，B，C，E，F)，P3 : (A，B，E，F) P4 : (A，B，E，C，F)，P5 : (A，D，C，E，F)，P6 : (A，D，E，C，F) P7 : (A，D，E，B，C，F)。 2）从A到F的简单路有9条

除了上述1）中7条外，不有P8 : (A，D，E，C，B，E，F) P9 : (A，D，E，B，C，E，F)。 3）从A到F的距离为3。

由图可看出，显然从A到F，一步不可能到达，二步也不可到达；但有长度为3的路，比如P1，P3，P5等能从A到F，故从A到F的距离为3。

8．在下面的图中，哪此是边通图？哪些是简单图？

（a） (b) (c)

[解] （1）图（2）与图（b）不连通，它们能分成两个边通支。所以只有图（c）是

连能图。

（2）图（c）是简单图，图为它显然无平等边，无自环。图（a）、（b）是多重图（a）有平行边（b）有自环。

9．求出所有具有四个结点的简单无向连通图。

[解] 在不同构的意义下，具有四个结点的简单无向连通图共有6个。

如下面所示：

G1

G2 G2

G3

G4 G4

G5 G5

G6 G6

lya定理得证。参见卢（实际上，具有四个结点的简单图共有11个，这可由P o

开澄的《组合数学一算法与分析》上册P241-P244）。 10．设G是一个简单无向图，且为（n，m）图，若

1

m (n 1)(n 2)

2

证明G是连通图。

[证] 用反证法。假若简单无向图G不是连通图，那么G必可成K（≥2）个连通分支G1，G2， ，Gk，每个连通分支Gi（1≤i≤k）都是一个简单无向图，因此它们分别为（n1，m1），（n2，m2）， （nk，mk）图显然有n=n1+n2+ nk，m=m1+m2+ mk，且ni≤n-1（1≤i≤k）于是有

m=m1+m2+ mk

n1(n1 1)n2(n2 1)n(n 1)

kk

222

(n 1)(n1 1)(n 1)(n2 1)(n 1)(nk 1)

222

=(n-1)·== ≤

1

·((n1-1)+(n2-1)+ +(nk-1)) 2

1

(n-1)((n1+n2+ +nk)-k) 2

1

(n-1)(n-k) 2

1

(n-1)(n-2) (k≥2) 2

1

（n-1）(n-2)矛盾。 2

这与已知M＞

因此假设错误，G是连通图。

11．设G=（V，E）是无向完全图（无自环），|V|=n

1） 求G中有多少初级圈？

2） 设e∈E，求含有e的初级圈有几个？

3） 设u，v∈V，u≠v，求由u到v有几条初级路？

[解] 1）在一个有n个结点的无向完全图（无自环）中，构成一个初级圈，至少需3个结点，至多有n个结点，故G中初级圈的个数为

2! n 3! n (n 2)! n (n 1)! n

2 3 2 4 2 n 2 2 n 1 Akn(个)k 32

列（除2）；长为k的圈排列可形成k个线排列（除k）。 2）含有边e的初级圈为

n 2k 0

n

即将从n个结点中选出的k个结点进行排列，然后除去重复：每个排列的倒排

A

1

n 2

A

2n 2

A

n 2n 2

Akn 2(个)

即，从u到v的直接边（完全图，该边存在）是一条；再将该直接边加到其它初级路里，就构成了含边（u，v）的初级圈，从而由2)可得如上数值。

12．试证在简单有向图中

1) 每个结点及每条边都属于且只属于一个弱分图； 2) 每个结点及每条边都至少属于一个单向分图。

[证] 1）有向图中的弱连通性建立了G中结点集合V上的等价关系，因此构成了V上的一个划分；同时，还建立了边集上的一个划分。因此，每一个弱连通支就是一个“划分块”。设G1，G2， ，Gk为G的所有弱连通分图，则有：

V（G）=V（G1）∪V（G2） ∪V（Gk） E（G）=E（G1）∪E（G2） ∪E（Gk）

并且，当i≠j时，V（Gi）∩V（Gj）=φ，E（Gi）∩E（Gj）=φ。因此，每个结点及每条边都属于且只属于一个弱图。

2）有向图中的单向连通性建立了G中结点集合V上的一个相容关系，因此构成了V上的一个覆盖；同时，还建立了边集上的一个覆盖；每一个单向分图就是一个“覆盖快”。设G1，G2 ，Gk为G的所有单向分图，则有

V（G）=V（G1）∪V（G2）∪ ∪V（Gk） E（G）=E（G1）∪E（G2）∪ ∪E（Gk） 因此，每个结点及每条边都至少属于一个单向分图。

13．试用有向图描述出下述问题的解法路径：某人m带一条狗d，一只猫c和一只

兔子r过河，没有船，他每次游过河时只能带一只动物，当没有人管理时狗和兔子不能相处，猫和兔子也不能相处。在这些条件的约束下，他怎样才能将这三只动物从北岸带往南岸？

[解] 将人，狗，兔中任意几种在一起的情况看作是一种状态；一个布局是一个二元

组，由两个互补的状态构成，二元组的前者表示河北岸的状态，后者表示河南岸的状态。初始布局为（pdcr，φ），终止布局为（φ，pdcr）安全布局有十种，不安全布局有六种，它们是：

（dr，pc），（cr，pd），（dcr，p）， （pc，dr），（pd，cr），（p，dcr）。

14．求下列图中的所有强连通支，单向连通支，弱连通支。

v5

v6

v10

[解] 1）有六个强连通支，它们是：

G1=({v1，v2，v3，v9，v10}，{(v1，v2)，(v2，v9)，(v9，v10)，(v10，v1)，(v2，v3)，

(v3，v9)})

G2=({v4}，φ)，G3=({v8}，φ)，G4=({v7}，φ)， G5=({v5}，{(v5，v5)})，G6=({v6}，φ)。

2）有四个单向连通支，它们是：

G1=({v1，v2，v3，v4，v9，v10}，{(v1，v2)，(v2，v9)，(v9，v10)，(v10，v1)，(v2，

v3)，(v3，v9)，(v3，v4)})，

G2=({v4，v7，v8}，{(v7，v8)，(v8，v4)})， G3=({v5}，{v5，v5})，G4=({v6}，φ) 3）有三个弱连通支，它们是

G1=({v1，v2，v3，v4，v7，v8，v9，v10}，{(v1，v2)，(v2，v9)，(v9，v10)，(v10，

v1)，(v2，v3)，(v3，v9)，(v3，v4)，(v7，v8)，(v8，v4)}) G2=({v5}，{(v5，v5)})，G3=({v6，φ})

15．给出有向图如下所示： 1) 求它的邻接矩阵A；

2) 求A2，A3，A4，指出从v1到v4长度为

1，2，3，4的路径各有几条？

3) 求AT，ATA，AAT，说明ATA和AAT

中元素（2，3）和（2，2）的意义；

4) 求A(2)，A

（3）

v9 v8 v7

v

1

v2 ，A

（4）

及可过矩陈R；

v3

5) 求出强度通支。 [解] 1）它的邻接矩阵

0 0A

0 0 2) 0 0A2

0 0 0 03

A

0 0 0 0A4

0 0

101

011 101

100 101 0

011 0101 0

100 0

111 0

201 0111 0

011 0212 0

122 0212 0

201 0

101 0

011 0

101 0

100 0

101 0

011 0

101 0

100 0101 0

011 0

1010 100 0

111

201 111

011 212

122 212

201 323

413 323

122

从v1到v4长度为1的路有1条，是（v1，v4）；

从v1到v4长度为2的路有1条，是（v1，v2），（v2，v4）； 从v1到v4长度为3的路有2条，是： (v1，v2)，(v2，v8)，(v3，v4)； (v1，v4)，(v4，v2)，(v2，v4)。 从v1到v4长度为4的路有3条，是： (v1，v2)，(v2，v3)，(v3，v2)，(v2，v4)； (v1，v2)，(v2，v4)，(v4，v2)，(v2，v4)； (v1，v4)，(v4，v2)，(v2，v3)，(v3，v4)； 3）

0

T

A= 1

0 1

0011

0101

0 1 0 0

0000 0 1011 0

ATA

0100 0 1110 0 0101 00

0011 10

AAT

0101 01

0100 11

10110101

1 0

11 0

01 0

00 0

0 21

1 12

0 21

0 10

003022111

0011

0

2 1 3 1 0 0 1

在ATA中，元素（2，3）=0的意义是：

不存在着这样的结点，从它发出的边同时终止于结点v2及v3；

在ATA中，元素（2，3）=3的意义是：deg（v2）=3，即结点v2的入度为3。

在AAT中，元素（2，3）=1的意义是：存在着一个结点，v4从v2及v3发出的边同时终之于它；

在AAT中，元素（2，2）=2的意义是：deg（v2）=2，即结点v2的出度为2。 4）

A(2)

0

0 0 0 0 0 0 0 0 0 0 0

10111110

01001111

1 0 01 1 0 0 01 0 01 1 0 1 0

101110111011

0100010101011111

A(3)

1 0

01 1 0 0 01 0

01 1 0 0 0

0 0 0 0

11101111

1110

1011

1 1 1 1 1 1 1 1

A(4)

111 0

0111

111 0

111 0

R A A(2) A(4)

0 0 0 0

1 1 1 0 11 11 11

11

111 111 111

111

5）·强连通支为 G1=（{v1}，φ）

G2=（{v2，v3，v4}，{(v2，v3)，(v2，v4)，(v3，v2)，(v3，v4)，(v4，v2)}） 16．利用Dijkstra算法，求出下面图中从u到v的所有最短路径及路径长度。

10

u

v

（1）

(a)

∞ v

(b)

(c)

(d)

(e)

(f)

(g)

(h)

u4

从u到v的最短路径共有三条： P1=(u,u1,u3,u4,v)

P2=(u,u1,u2,u3,u5,u6,v) P3=(u,u12,u2,u3,u6,v) P4=(u,u1,u2,u3,u5,u8,u6,v) P5=(u,u7,u8,u6,v)

从u

到v的最短路长为： W(P1)=W(P2)=W(P3)=15。

u1

(j)

（2）

(a)

(b)

(c)

(d)

(e)

(f)

(g)

17．在Dijjkstra算法中，增加一个记忆系统，使得此算法不仅能给出从u到v的最

短路的路长，而且可以给出一条最短路径。

[解] 观察Dijkstra算法的，容易看出每当确定出一个新的标记点t0 时，由初始

结点u到结点t0的最短路就可以确定下来了（但可能不唯一）。因而，该路中心至少有一点P。直接与结点t0相邻。故此，修正的算法如下： 算法一：在确定从结点u到结点v的最短路的路长的同时， ：={u}；T：=V\P；S(u)：=[u]；d(u)：=0；

( t∈T)(d(t)：=∞)

t∈T)(d(t)：=min{d(t)，d(P)+W(P，t)}；

p P

( t0∈T)( t∈T)(d (t0)≤d(t))； ( P0∈P)(d(t0)=d(p0)+W(p0，t0))；

S(t0)：=[S(p0) | t0]； （表结构）

：=PU{t0}；T：=T\{t0}；mark(t0)：=d(t0) t0=v then exit else goto ； 我们也可以采用回溯方法。

算法二：在Dijkstra算法之后增加一个回溯系统，求出一条从u到v的最短路径。

：={u}；T：=V\P；d(u)：=0；( t∈T)(d(t)：=∞)； t∈T)(d(t)：=min{d(t)，d(p)+w(p，t)})；

p P

( t0∈T)( t∈T)(d(t0)≤d(t))；

：=PU{t0}；T：=T\{t0}；mar(t0)：=d(t0) ：=[v]；g：=v

p∈P)(d(p)=d(g)=W(p，q))； s：=[p | s]； q：=p；

以上两种算法都直接给出了从结点u到结点v的最短路径。但是，算法一的记忆比较庞大，而算法二又重复了Dijkstra算法中的一些判断过程。我们综合以上两种算法，又有如下

算法三：在求出从结点u到结点v的最短路径之间各结点的最短长度d值以及前驱结点（紧前结点）

：= {u}；T：=V\P；d(u)：=0；( t∈T)(d(t)：=∞)； t∈T)(d(t)：=min{d(t)，d(p)+w(p，t)})；

p P

( t0∈T)( t∈T)(d(t0)≤d(t))； ( p∈P)(d(p)=d(p0)+w(p0，t0))；

：=PU{t0}；T：=T\{t0}；mark(t0)：=(p0，d(t0))； t0=v then exit else goto ；

算法三并未直接给出从结点u到结点v的最短路径，但它的记忆系统比较简单，计算方便。要给出从结点u到v的最短路经时，只要从终步v开始，根据标记的第一个分量，向前回溯即可得到。 18．判断下列图示能否一笔画。

b

c

[解] 根据本章§2定理2：图中奇结点的个数是偶数。所以奇结点的个数为2k，当

k=0，1时，此图是一笔画的，而当k＞1时，则此图是k笔画的。于是 图(a)，不是一笔画，因为它的奇结点为四个（用○·表示）； 图（b），（c）都是一笔画，因为它的奇结点是二个；

19．设G是有向图，证明G是Euler图的充要条件是：G是强连通的，且G中每一

结点的进度等于出度。 [证] 必要性

若G是Euler图，则G中含有有向Euler圈，并且G中无狐立点，从而G

中每个结点都与一条有向边相连。由于每条向边都必须在有向Euler圈上，因此每个结点也都在有向Euler圈上，所以从任一结点出发都可到达另一任意结点，故此G是强连通的。

而且，又由于每条有向边只能在有向Euler圈中出现一次，于是每一个结点，

有一边进来，就应有一边出去，再有一边进来，就应再有一边出来；这样，每一结点的进度必然等于度。 充分性

因为G是强连通的，故G中任何两个结点都可互相到达，因此G中存在着

有向简单圈。不妨设C是G中长度最长的有向简单圈套 ，则C必是G中的有向Euler圈，从而G是Euler图。

否则，必有边e不在圈C中，但e的一个端点在C上，不然的话，则图G

一定不强连通，这和已知条件矛盾。由于对于图G中每个点v，degG(u)= 并且C是一个有向圈，从而对图G1=（V（G），E（G）\C）仍有=degG(u)= degG(u)，

G(u)，故此在G1中一定存在含有e的有向圈C1中一定存在含e的有向圈

C1，C∪C1显然仍是G中的有向圈，且此有向圈的长度大于C的长度，这和C是G中最长的有向圈的假定相矛盾，故C一定是G中的有向Euler圈。 这个有向Euler圈C可利用一个算法给出： 以G中任一结点出发，沿着有向边走

成一个圈，而且是简单圈套；

若此圈已是有向Euler圈，出口；

否则，除此圈外，必仍有若于边不在其中，这些边中至少有一条边以引中至少有一条边以此圈中的某一结点为起点，以这个结点为起点走出一个圈（这个别圈不应含原圈中的任一边，并且是一简单圈）；

将此圈插入原圈中，得到一个新的长度更长的简单圈，然后

20．设G是连通的无向图，且有2k＞0奇结点。证明：在G中存在k条边不重的简

单路G1，C2，C3 Ck，使

E(G)=E(C1)∪E(C2)∪E(E3)∪ ∪E(Ck)

[证] 设v1，v2， ，vk，vk+1 ，v2k为G中的2k个奇结点，在vi和vi+k两个结点间

连以新边ei*(i=1，2， ，k)，所得之图记为G*，则G*的每个结点的度均为偶数，又由于G连通，则G*也是连通的，根据Euler定理，知在G*中存在Euler圈C*。若我们从C*中除去这k条新边ei*(i=1，2， ，k)，则C*就分解成k条边不重的简单路C1，C2，C3 Ck，并且显然有E(G)=E(C1)∪E(C2)∪E(C3) ∪E(Ck)。

21．构造一个长度为16的De Bruijn序列。

[解] 我们定义一个有向图D4如下：D4的项点是3位二进制数p1p2p3，其中pi=0或1。存在一条以项点p1p2p3为起点，以项点q1q2q3为终点的向边（p1p2p3，q1q2q3）当且仅当p2=q，p3=q2。另外，D4的每条有向边（p1p2p3，p2p3p4）上都标以四位二进制数p1p2p3p4。D4如下图1所示：

显然，D4是连通的，并且D4的每个项点都具有入度2和出度过2，故由有

本文来源：https://www.bwwdw.com/article/duei.html