《图论及应用第一章完整作业》由会员分享，可在线阅读，更多相关《图论及应用第一章完整作业（7页珍藏版）》请在金锄头文库上搜索。
1、习 题 11. 证明在n阶连通图中（1） 至少有n-1条边。（2） 如果边数大于n-1，则至少有一条闭通道。（3） 如恰有n-1条边，则至少有一个奇度点。证明 (1) 若对vV(G),有d(v)2,则：2m=d(v)2n mnn-1,矛盾！ 若G中有1度顶点，对顶点数n作数学归纳。 当n=2时，G显然至少有一条边，结论成立。 设当n=k时，结论成立， 当n=k+1时，设d(v)=1，则G-v是k阶连通图，因此至少有k-1条边，所以G至少有k条边。(2) 考虑v1v2vn的途径，若该途径是一条路，则长为n-1,但图G的边数大于n-1,因此存在vi,vj,使得viadgvj,这样，vivi+1vj
2、并上vivj构成一条闭通道；若该途径是一条非路，易知，图G有闭通道。(3) 若不然，对vV(G),有d(v)2,则：2m=d(v)2n mnn-1,与已知矛盾！2. 设G是n阶完全图，试问（1） 有多少条闭通道？（2） 包含G中某边e的闭通道有多少？（3） 任意两点间有多少条路？ 答 (1) (n-2)! (2) (n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+(n-2)1.3. 证明图1-27中的两图不同构：图1-27证明 容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。4. 证明图1-28中的两图是同构的图1-28证明 将图1-
3、28的两图顶点标号为如下的(a)与(b)图作映射f : f(vi)ui (1 i 10)容易证明，对vivjE(a),有f(vivj)=uiujE(b) (1 i 10, 1j 10 )由图的同构定义知，图1-27的两个图是同构的。5. 证明：四个顶点的非同构简单图有11个。证明 m=0123456 由于四个顶点的简单图至多6条边，因此上表已经穷举了所有情形，由上表知：四个顶点的非同构简单图有11个。6. 设G是具有m条边的n阶简单图。证明：m =当且仅当G是完全图。证明 必要性 若G为非完全图，则$ vV(G),有d(v) n-1 d(v) n(n-1) 2mn(n-1) m n(n-1)/
4、2=, 与已知矛盾！ 充分性 若G为完全图，则 2m= d(v) =n(n-1) m= 。7. 证明：（1）m(Kl,n) = ln，（2）若G是具有m条边的n阶简单偶图，则m 。证明 (1) Kl,n的总度数为2ln,所以，m(Kl,n) = ln。(2) 设G的两个顶点子集所含顶点数分别为n1与n2,G的边数为m,可建立如下的二次规划：m=n1n2s.t n1+n2=nn11, n2 1当n为偶数时，n1=n2=n/2时，m取最大值：m=n2/4当n为奇数时，取n1=(n+1)/2, n2=(n-1)/2时，m取最大值：m=(n2-1)/4所以，m 。8. 设和是简单图G的最大度和最小度，
5、则2m / n。证明9. 证明：若k正则偶图具有二分类V= V1V2，则 | V1| = |V2|。 证明 由于G为k正则偶图，所以，k| V1 | =m = k| V2 | V1= V2 。10. 证明：由两人或更多个人组成的人群中，总有两人在该人群中恰好有相同的朋友数。 证明 将人用图的顶点表示，图的两顶点邻接当且仅当人群中的两人相认识，于是，问题转化为：证明在任意一个简单图中必有一对度数相等的顶点。 若图G为连通单图，则对vV(G),有1d(v)n-1,因此，n个顶点中必存在两个顶点，其度数相同；若G为非连通图，设G1为阶数n1的连通分支，则vV(G1),有1d(v)n1-1，于是在G1
6、中必存在两个顶点，其度数相同。11. 证明：序列 (7,6,5,4,3,3,2) 和 (6,6,5,4,3,3,1) 不是图序列。证明 由于7个顶点的简单图的最大度不会超过6，因此序列 (7,6,5,4,3,3,2) 不是图序列；(6,6,5,4,3,3,1)是图序列 （5，4，3，2，2，0）是图序列，然（5，4，3，2，2，0）不是图序列，所以(6,6,5,4,3,3,1) 不是图序列。12. 证明：若2，则G包含圈。 证明 只就连通图证明即可。设V(G)=v1,v2,vn,对于G中的路v1v2vk,若vk与v1邻接，则构成一个圈。若vi1vi2vin是一条路，由于d 2，因此，对vin，
7、存在点vik与之邻接，则vikvinvik构成一个圈 。 13. 证明：若G是简单图且2，则G包含长至少是+1的圈。证明 设v0v1vk为G中一条最长路，则v0的邻接顶点一定在该路上，否则，与假设矛盾。现取与v0相邻的脚标最大者，记为l，则ld,于是得圈v0v1v2vlv0,该圈长为l+1，显然不小于+1。14. G的围长是指G中最短圈的长；若G没有圈，则定义G的围长为无穷大。证明：（1） 围长为4的k的正则图至少有2k个顶点，且恰有2k个顶点的这样的图（在同构意义下）只有一个。（2） 围长为5的k正则图至少有k2+1个顶点。证明 (1) 设u,v是G中两相邻顶点，则S(u)S(v)=f,否则
8、，可推出G中的围长为3，与已知矛盾。因此，G中至少有2（k-1）+2个顶点，即有2k个顶点。把S(u) v，S(v) u连为完全偶图，则得到2k个顶点的围长为4的图，由作法知，这样的图是唯一的。(2) 对uV(G),设u的邻接顶点为u1,u2,uk,由于G的围长为5，所以，u1,u2,uk互不邻接。又设ui的邻接顶点为ui1,ui2,uik-1,(i=1,2,k),显然，S(ui)S(uj)= u (ij),否则，G中有长为4的圈，所以，G的顶点数至少有k2+1个。15. 对具有m条边的阶n图G，证明：（1）若mn，则G包含圈；（2）若mn+4，则G包含两个边不重的圈。证明 （1）若G含有环或
9、平行边，则G有圈。假定G为n阶简单图。若G中顶点度大于等于2，则G中有圈。设G中有一度顶点，去掉该顶点和其关联的边得图G1,由条件，显然有m(G1) V(G1),若G1中有一度顶点，去掉该顶点和其关联的边得图G2,有m(G2) V(G2),，如此进行下去，该过程不可能进行到n=1或n=2的情形，否则，不满足mn所以，过程进行到Gm,Gm是度数2的图，它含有圈。(2) 只就m=n+4证明就行了。设G是满足m=n+4，但不包含两个边不相交的圈的图族中顶点数最少的一个图。可以证明G具有如下两个性质：1) G的围长g5。事实上，若G的围长4，则在G中除去一个长度4的圈C1的一条边，所得之图记为G,显然
10、，m(G) V(G)=V(G),由(1),G中存在圈C2, 使C1,C2的边不相交这与假定矛盾；2）d (G)3。事实上，若d(v0)=2,设v0v1,v0v2E(G),作G1=G-v0+v1v2;若d(v0)1,则G1为在G中除去v0及其关联的边(d(v0)=0,任去G中一条边)所得之图。显然，m(G1)=V(G1)+4,G1仍然不含两个边不重的圈之图。但V(G1)V(G)，与假定矛盾。 由2),n+4=m3n/2 n 8. 但另一方面，由1),在G中存在一个圈Cg，其上的顶点之间的边，除Cg之外，再无其它边，以S0表示Cg上的顶点集，故由2),S0上每个顶点均有伸向Cg外的的边。记与S0距
11、离为1的顶点集为S1，则S0的每一个顶点有伸向S1的边，反过来，S1中的每个顶点仅有唯一的一边与S0相连，不然在G中则含有长不大于g/2+2的圈，这与G的围长为g相矛盾，故S0 S1,于是有：nS0+ S1g+g10,但这与n8矛盾。所以，假定条件下的G不存在。16. 在图1-13的赋权图中，找出a到所有其它顶点的距离。v1 1 v4 6 342 9 a 8 v2 2 v5 6 b 7 2 41 2 v3 v6 图1-139解 1. A1= a，t(a) = 0，T1 = 2.3. m1 = 1, a2 = v3 , t(v3) = t(a) + l(av3) = 1 (最小)， T2 =av
12、32. A2 =a, v3, 3. m2 = 1, a3 = v1 , t(v1) = t(a) + l(av1) = 2 (最小)， T3 =av3, av12. A3 =a, v3, v1, 3. m3 = 3, a4 = v4 , t(v4) = t(v1) + l(v1v4) = 3 (最小)， T4 =av3, av1, v1v42. A4 = a, v3, v1, v4，b1(4) = v2，b2(4) = v2，b3(4) = v2, b4(4) = v53. m4 = 4, a5 = v5 , t(v5) = t(v4) + l(v4v5) = 6 (最小)， T5 =av3,
13、 av1, v1v4, v4v52. A5 = a, v3, v1, v4, v5，b1(5) = v2，b2(5) = v2，b3(5) = v2 , b4(5) = v2, b5(5) = v23. m5 = 4, t(v2) = t(v4) + l(v4v2) = 7 (最小)， T6 =av3, av1, v1v4, v4v5, v4v22. A6 = a, v3, v1, v4, v5, v2, b2(6) = v6, b4(6) = b，b5(6) = v6，b6(6) = v63. m6 = 6, a7 = v6 , t(v6) = t(v2) + l(v2v6) = 9 (最小
14、)， T7 =av3, av1, v1v4, v4v5, v4v2, v2v62. A7 = a, v3, v1, v4, v5, v2, v6, b4(7) = b，b5(7) =b，b7(7) =b3. m7 = 7, a8 = b , t(b) = t(v6) + l(v6b) = 11 (最小)， T8 =av3, av1, v1v4, v4v5, v4v2, v2v6, v6b于是知a与b的距离 d(a, b) = t(b) = 11由T8导出的树中a到b路就是最短路。17. 证明：若G不连通，则连通。证明 对,若u与v属于G的不同连通分支，显然u与v在中连通；若u与v属于g的同一连通分支，设w为G的另一个连通分支中
