图论及其应用1-3章习题答案

图1-28

证明 将图1-28的两图顶点标号为如下的(a)与(b)图

u1 v1

u6 u5 v6 v10 v5 v2 u2 u8 v7

u10 u3 v8 v9

u7 u9 v4 v3 (b) (a)

作映射f : f(vi)ui (1 i 10) 容易证明，对vivjE((a)),有f(vivj)uiujE((b)) (110 )

由图的同构定义知，图1-27的两个图是同构的。

u4 i 10, 1j

n2. （题6）设G是具有m条边的n阶简单图。证明：m =2当且仅当G是

完全图。

证明 必要性 若G为非完全图，则n(n-1) 2mn(n-1) m

v

V(G),有d(v)

n-1 d(v)

n n(n-1)/2=2, 与已知矛盾！

 d(v) =n(n-1)

充分性 若G为完全图，则 2m=

n m= 2。

3. （题9）证明：若k正则偶图具有二分类V= V1∪V2，则 | V1| = |V2|。

证明 由于G为k正则偶图，所以，k V1 =m = k V2 V1

。

4. （题12）证明：若δ≥2，则G包含圈。

= V2

证明 只就连通图证明即可。设V(G)=｛v1,v2,…,vn｝,对于G中的路v1v2…vk,若vk与v1邻接，则构成一个圈。若vi1vi2…vin是一条路，由于 2，因此，对vin，存在点vik与之邻接，则vikvinvik构成一个圈 。

5. （题17）证明：若G不连通，则G连通。

证明 对u,vV(G),若u与v属于G的不同连通分支，显然u与v在G中连通；若u与v属于g的同一连通分支，设w为G的另一个连通分支中的一个顶点，则u与w，v与w分别在G中连通，因此，u与v在G中连通。

____习题二

2、证明：每棵恰有两个1度顶点的树均是路。

证明：设树T为任意一个恰有两个1度顶点的树，则T是连通的，且无圈，令V1

、V2 为度为1的顶点，由于其他的顶点度数均为0或者2，且T中无圈，则从V1到V2 有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。 5、证明：正整数序列(d1,d2,...,dn)是一棵树的度序列当且仅当

di1ni2(n1)。

n 证明：设正整数序列(d1,d2,...,dn)是一棵树T的度序列，则满足

ndi1i2E，E为T的

边数，又有边数和顶点的关系nE1，所以di1i2(n1)

n314、证明：若e是Kn的边，则(Kne)(n2)n。

若e为Kn的一条边，由Kn中的边的对称性以及每棵生成树的边数为n-1，Kn的所有生

(n1)n成树的总边数为：

n2(n1)nn22nn3，，所以，每条边所对应的生成树的棵数为：1n(n1)2所以，K n - e 对应的生成树的棵数为：

(Kne)nn22nn3(n2)nn3

16、Kruskal算法能否用来求：

（1）赋权连通图中的最大权值的树？

（2）赋权图中的最小权的最大森林？如果可以，怎样实现？ 解：（1）不能，Kruskal算法得到的任何生成树一定是最小生成树。 （2）可以，步骤如下：

步骤一：选择边e1，是的(e1)尽可能小；

步骤二：若已选定边e1,e2,...,ei，则从E\\{e1,e2,...ei}选取ei1，使 a、G[{e1,e2,...ei1}]为无圈图 b、(ei1)是满足a的尽可能小的权； 步骤三：当步骤二不能继续执行时停止；

习题三

3.设G是阶大于2的连通图，证明下列命题等价：

（1）G是块

（2）G无环且任意一个点和任意一条边都位于同一个圈上； （3）G无环且任意三个不同点都位于同一条路上。 证明：（1）→（2）：

G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到

新图G1，显然G1的是阶数大于3的块，由定理，G中的u,v位于同一个圈上，于是G1中u与边e都位于同一个圈上。 (2)→(3):

无环，且任意一点和任意一条边都位于同一个圈上，任取的点u，边e，若在上，则三个不同点位于同一个闭路，即位于同一条路，如不在上，由定理，的两点在同一个闭路上，在边插入一个点v，由此得到新图，显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。 (3)→(1):

连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，xv1,yv2，点在每一条的路上，则与已知矛盾，是块。

13、设H是连通图G的子图，举例说明：有可能k(H)> k(G). 解：通常.

整个图为，割点左边的图为的的子图， ，则.

e 15、设T是简单连通图G的生成树，TGE(T)称为G的余树，图G的极小边割是指其H 任何真子集均不是边割的边割。证明： （1）T不含G的极小边割。

（2）Te包含G的唯一的极小边割，其中e为G的不在T中的边。

证明：（1）设T含有G的极小边割S，则T中不含极小边割S，由于T是简单连通图G的生

成树，则T中必然含有一组极小割边，这与T中不含极小割边相矛盾，则T中不含G的极小边割。

（2）假设e为T中的一条边，根据（1）得T+e中仍不含G的极小割边，这与 Te包含G的唯一的极小边割相矛盾，则e为G的不在T中的边，得证。