2024年1月7日发(作者：怎样输入数学试卷)

习 题 十 二

1．一个简单图G有多少不同的定向图？

分析：由于简单图的每条边有两种不同的方向可供选择，因此具有q条边的无向简单图G共有2q个不同的定向图。

解.设G(p,q)是简单图，则G共有2q个不同的定向图。

2．简单有向图的基础图一定是简单图吗？

分析：有向图的基础图是将有向边变成无向边所得到的无向图，由于在有向图中（u,v）和(v,u)

是两条不同的边，而在无向图中却属于同一条边，这样无重边的有向图变成无向图以后就有可能含有重边，从而不是简单图。

解：不一定，如右图。

3．设D(p,q)是简单有向图，证明：

（1）若D是强连通图，则pqp(p1)

（2）若D是弱连通图，则p1qp(p1)

分析：强连通图D是指D中任意两个顶点间存在双向的通路，因此D的基础图G必含H回路，一条H回路的边数至少有p条边，因此qp；另一方面，由于完全强连通图的边数等于p(p1)，因此简单有向图D的边数qp(p1)。

弱连通图D是指D的基础图是连通图的有向图，根据习题5第16题（1）有具有q个顶点的连通图的边至少有p-1条，因此p1q。

证明（1）因D是强连通图，故D中任意两个顶点u,v之间既存在(u,v)通路，又存在有向(v,u)一通路，于是，D的基础图G必含H回路.故qp，又因D是简单有向图.故D中任何两个顶点之间最多有二条弧，从而qp(p1)，故pqp(p1).

（２）因D是弱连通图，故D的基础图G是连通的，若G无回路，则qp1，因此，p1qp(p1)

4．设D(p,q)是有向图，证明：

ppdi1D(ui)qdD(ui)

i1分析：dD(v)是指有向图D中顶点v的出度，即以顶点v为尾的弧的条数；

由于D中的任一弧恰有一个头和一个尾，因此，每增加一条弧，对D的所有顶点来说，肯定会增加一个出度，同时也会增加一个入度。

证明：因为有向图中的每条弧对应一个顶点（尾）的出度和另一个顶点（头）的入度计数.故

i1dpD(ui)dD(ui)q

i1p5．基础图是完全图的有向图D(p,q)满足

(di1pD(ui))(dD(ui))2

2i1p分析：显然基础图是完全图的有向图D(p,q)中每个顶点满足：d(ui)d(ui)p1

p(p1)p 又根据第4题对D中每个顶点ui来说满足d(ui)qdD(ui)，

2i1i1ppp(p1)因此有dD(ui)dD(ui)

2i1i1证明.由D的假设知，对任何uiV(D)有

Dpd(ui)d(ui)p1 （1）

于是，

d(ui))22d(ui)d(ui)d(ui))2(p1)2（2）

又由（1）有

d(ui)(p1)d(ui)，代入（2）有

(d(ui))22[(p1)d(ui)]d(ui)(d(ui))2(p1)2

整理得

(d(ui))22(p1)d(ui)(d(ui))2(p1)2 （3）

由题4知

整理得

d(ui)qi1pD2pi1i1p1p(p1) （完全有向图）

2(d(ui)(dD(u1))2

V(D)，均有d(u)d(u)，则D有一条有向回6．设D是单连通图. 试证明：若对任意u路。

V(D)，存在一条单向通路，考虑D中的极长通路P分析：单连通图D，是任意两个顶点u,v的始点u，由d(u)d(u)即能得到D中的一条有向回路。

证明：因为D是单连通图，所以D中至少存在一条通路。

假设P（uv0v1„vn）(vn =v)是D的一条极长通路，因为d(u)d(u)，所以d(u)0，因此在D中存在以u为头的弧e，由P是极长通路，所以e的尾必在P 中，不妨假设e的尾是vi，于是vi uv0v1„vi构成了D的一条有向回路。



7．设D是一个简单有向图，求证

（1）D中包含长度至少为max{,}的有向通路

（2）若max{,}k0，则D中包含长度至少为k1的有向回路.其中max{d(v)},min{d(v)}

vVDvvD分析：（1）由对称性，不妨假设max{,}=，考虑D中极长有向通路P（uv0v1„vn）(vn =v)，假设P的长度小于，由的定义，知d(v)，因此以v为尾的弧的条数应不小于，因此至少有一条弧的头不在P上，与P是极长通路矛盾。本小题使用反证法。

（2）同样考虑P上的顶点v，由以v为尾的弧的条数应不小于，且这些弧的头都在P上，可构造一条长度不小于k+1的有向回路。

证明（1）不妨假设max{,}（否则考虑其反向图）

设P（uv1v2„vn）(vn =v)是D中极长的有向(u,v)通路.若|P|，则由于G是简单有向图，必有尾为v而头不在P上的弧，因此P可以延长，此与P的极长性矛盾。

（2）同（1）设max{由（1）设P是D中最长的有向(u,v)通路.于是|P|k.,}，显然，d(v)k.且以v为尾的弧的头必在u,v1,,vn1中，否则与p的最长性矛盾.

a) 若nk，则必有vn,uA(D)

b）若nk，设nkr，r1，于是至少有(k0)

vn,vjmA(D)，m=1,2,„k

不妨假设vj1vj2vjk。于是D中存在有向回路

Q(vj1vj2vjkvvj1） 显然|Q|k1

8．有向图D的有向E闭链指D中存在一条过每条弧恰好一次的有向闭链。证明：有向图D含有向E闭链当且仅当D是强连通的，并且对所有v∈V（D），有dD(v)dD(v)

分析：显然充分性成立。

反之，如果D是强连通的，并且对所有v∈V（D），有dD(v)dD(v)，则D中含有有向回路，假设C是D中最长的有向回路，考虑D1=D-E（C），若D1是零图，则C就是D中的有向E闭链；若D1不是零图，则将构造出D的一个比C还长的有向回路，从而导出矛盾。

证明：若D是平凡图，结论显然成立，下面设D为非平凡图，设D是具有m条边的n阶有向图。

充分性 如果D含有向闭链，由于D的每个顶点都处于回路中，故D是强连通的。又由于E

闭链上包含了D的所有弧，且当经过回路上每个顶点一次时，被消耗的出度与入度相等。所以，对所有v∈V（D），有

dD(v)dD(v)。

必要性 由D是非平凡的连通图可知，G中边数m≥1，对m做归纳法。

D的强连通性及D中任意顶点v∈V（D），有dD(v)dD(v) ，由习题6的结论，D中存在有向回路，设C是D中一个最长的有向回路，删除C上的全部边，得D的生成子图D1，若D1是零图，则C就是D中的有向E闭链；若D1不是零图，则D1中至少存在一条弧e满足e的一个端点在C中，否则在D中C将成为一个独立的强连通分支，与D是强连通矛盾。考虑D1包含e的强连通分支D2，显然D2满足也dD(v)dD2(v)，因此D2中也含有一个回路2C1，这样在D中C∪C1就构成了一个比C更长的有向回路。与C是D中最长的有向回路矛盾。

9．设D是不含有向回路的有向图，证明：

（1）0

（2）存在V（D）的一个有序顶点序列v1，v2….，vp使得对于1≤i≤p，D的每条以vi为头的弧在{v1，v2….，vi-1}中都有它的尾。

分析：（1）由的定义，只需证明D中存在某点v，满足dD(v)0即可。

 若D为零图，结论显然成立。假设D不是零图，则D中至少存在一条边，于是D中至少存在一条有向通路。假设P=v1v2….vk是D中一条“极大有向通路”，则可以证明dD(v1)0

（2）类似（1）的证明，可证明(D)0，因此D中至少存在一个顶点，不妨假设为vp，满足dD(vp)0，于是以vp为头的弧的尾都在{v1，v2….，vp-1}中，又因为Dvp也是不含有向回路的有向图，因此(Dvp)0，于是Dvp中也至少存在一个顶点，不妨假设为vp-1，满足dD(vp1)0，于是以vp-1为头的弧的尾都在{v1，v2….，vp-2}中，以此类推，可证明本题。

证明：（1）若D为零图，结论显然成立，因而设D不是零图。

 假设1，则对任意v∈V（D），均有dD(v)1。

由于D存在弧，所以D中存在“极大有向通路”，设P=v1v2….vk是D中一条“极大有向通路”，k≥2，由于vk不连接到P外的任意顶点，故存在vi（1≤i≤k），使得∈E（D），于是形成回路vivi+1….vk vi，这与D中无回路矛盾，因而D中存在dD(vk)0，因此0

（2）类似（1）的证明，可证明(D)0，因此D中至少存在一个顶点，不妨假设为vp，满足dD(vp)0，于是以vp为头的弧的尾都在{v1，v2….，vp-1}中，又因为Dvp也是不含有向回路的有向图，因此(Dvp)0，于是Dvp中也至少存在一个顶点，不妨假设为vp-1，满

足dD(vp1)0，于是以vp-1为头的弧的尾都在{v1，v2….，vp-2}中，以此类推，可构造出D的顶点序列v1，v2….，vp使得对于1≤i≤p，D的每条以vi为头的弧在{v1，v2….，vi-1}中都有它的尾。

10．证明：若有向完全图D中有一条有向回路，则D中有一个三角形的有向回路。

分析：由有向完全图的定义，有向完全图实际上是一个竞赛图。因此该题转化为证明含有有向回路的竞赛图存在一个三角形的有向回路。本题的证明用到了第12题的结论。

证明：设D是一个包含一条有向回路C的有向完全图，考虑由C中的顶点构成的D的点导出V(D\'),有d+(v)>0，子图D\'，显然D\'是一个回路，且D\'也是一个竞赛图，并且对任意顶点vd-(v)>0，于是D\'可以看作是一个满足第12题条件的问题，由12题结论有D\'中存在一个三角形的有向回路。从而D中存在一个三角形的有向回路。

11．dD(v)0的顶点称为发点，dD(v)0的顶点称为收点，证明：如果有一个有向图D不含有向回路，则D至少有一个发点和一个收点。

分析：如果D为零图或平凡图，显然满足结论。

否则考虑D中的极长通路P=v1v2….vk由P的极长性，可知d(v1)0且d(vk)0

证明：若D为零图或平凡图，结论显然成立，因而设D至少存在一条边。于是D中至少存在一条通路，假设P是D中的极长有向通路，（P=v1v2….vk），k≥2，由P的极长性，知以v1为头的弧如果存在的话，则该弧的尾必在P内，不妨假设为vi（1≤i≤k），即∈E（D），于是形成回路v1v2….vi v1，这与D中无回路矛盾，因而dD(v1)0。同理有dD(vk)0

12．假设在一次有n(≥3)名选手参加的循环赛中，每一对选手赛一局定胜负，没有平局，并且没有一个人是全胜的，证明其中一定有三名选手甲、乙、丙，使得甲胜乙，乙胜丙，丙胜甲。

分析：将参加比赛的n名选手看作有向图的结点，选手间的比赛为代表该两位选手间的一条有向弧，赢的一方为弧尾，输的为弧头，可构造具有n个结点的竞赛图，因此只需证明满足条件的n阶竞赛图必包含一个三角形的有向回路即可。本题的证明用到了推论12.2.2的结论。

证明：由推论（12.2.2），竞赛图D中含顶点u，使得从u出发，到其它各顶点都有一条长度不超过2的有向通路，又u不可能全胜，因此至少存在一个顶点w，满足w胜u，即存在从w到u的一条弧，因为从u到w存在一条长度k≤2的一条通路P，如果k=1，显然不满足竞赛图的定义，因此k=2，于是P+wu形成了一个三角形的回路。

13．证明：在完全二叉树中，弧的数目q恒为q2(l1)。其中l是树叶结点数目。

分析：由教材第102页结论，在完全二叉树中，满足 i+1=l（m=2，i是分枝结点数，l是树叶结点数），由定义12.3.2有顶点p=i+l，再由定义12.3.1知其基础图是树，因此其弧数（边数）q=p-1。

证：因为

(m1)i1t

这里m2,itp（顶点数），tl，i1t

因二叉树的基础图是树，故

qp1(it)1(t1)t12(t1)2(l1)

14．证明：一个完全二叉树必有奇数个结点。

分析：由题13知，一个完全二叉树弧的条数q2(l1)，而对一个树来说，其弧数q与顶点数p满足qp1。

证：由题13知，q2(l1)，而qp1

于是pq12(l1)1，因此一个完全二叉树必有奇数个结点。

15．试构造一个与英文字母b, d, e, g, o, y对应的前缀码，并画出该前缀码对应的二叉树，再用这六个字母构成一个英文短语，写出此短语的编码信息（0-1序列）。

分析：6个符号需要用三位二进制来编码，所以对应的二叉树高度至少为3。按定理12.4.2的方法构造一个高度为3的正则二叉树，并按定理12.4.1的方法将每条弧用0/1进行标记，删除多余的叶子直到只保留需要的六个叶子结点，将每个叶子分配给这六个符号，所得的编码必为前缀码。

解：构造的二叉树及其编码如下图所示。按此编码方法可对goodbye进行编码，其编码信息应为：011010

0

0

1

1

0

0 1

0

1

d

1

go

y

b e


更多推荐

顶点,存在,回路