设n阶无向完全图的边数为m

1、 第5章 图论P 190: 31. 设n阶无向完全图的边数为m，则图中所有点的度数和为2m。 而n阶无向完全图的每个顶点都与其它顶点相邻，故图中每个点度数都为n-1， 进而所有点的度数和为n*(n-1)。 因此2m=n(n-1)，故m=n*(n-1)/2。2. 设n阶有完全图的边数为m，则图中所有点的度数和为2m。 而n阶无向完全图的每个顶点都与其它顶点都有两条方向相反的边相连，并且有自回路，故图中每个点度数都为2(n-1)+2=2n， 进而所有点的度数和为2n*n=2n2。 因此2m=2n2，故m=n2。3. 需证：即证：又 由G的底图为k正则可知：对所有i1,2,3,n，故 045同构映射

2、g为：g(a)=a； g(b)=b； g(c)=c； g(d)=d； g(e)=e； g(f)= f；7（注意：同构图只列出其中一个）8由G是3正则可知：m=3n/2，由前提可知：3n/2=2n-4，故3n/22n-4，即n8。9竞赛图P203 作业：3、51、(a) 强连通；(b) 弱连通；(c) 单向连通；(d) 强连通图；2、G的主子图G-c不连通。3、4、假设一个包含两个分支分的n阶图两个分支的顶点数分别为x和y，则x+y=n。(1) 因为包含m个顶点的连通图至少包含m-1条边，故G1和G2各至少包含x-1和y-1条边，所以该n阶图至少包含x-1+y-1x+y-2条边，而x+y=n，故

3、该n阶图至少包含n-2条边。(2) 当n阶图的两个分支都是无向完全图时，两个分支包含的边数最多，设为m，则m = x(x-1)/2+y(y-1)/2=1/2(x+y)2-(x+y)-2xy)=1/2(n2-n-2xy)当x=1，y=n-1或x=n-1,y=1时，xy取值最小，即m取最大值1/2(n2-3n+2) 故该n阶图的边数最多为1/2(n2-3n+2)。5、bcdefghiz1063¥¥¥¥¥10611¥¥¥¥1011¥911¥911¥11¥111311161

4、31116121515a到z的最短路径为：aedcfgz；边权和为：14P：216：作业：4和81. 2. 题目所给的序列共有6个数，故序列对应的图应该有6个结点。根据无向树的性质，6个结点的无向树有5条边。再根据握手定理，图中所有结点的度数之和等于边数的两倍，因此6个结点的无向树所有结点的度数之和为5*2=10。因此只有第(4)个序列满足这个条件，并且第(4)个序列能对应以下无向树： 3. 证明：设无向树T=<V,E>, 设|V|=n，则|E|=n-1 因为T是连通图，因此，对于任意vÎV，有：d(v)³1。 根据握手定理，有：åvÎVd(

5、v)=2|E|=2n-2。 假设G中没有叶子结点，则所有结点的度数至少为2，因此，åvÎVd(v)³2n，这与åvÎVd(v)=2n-2矛盾。故G中至少有一个叶子结点。 假设G中只有一个叶子结点t，即除去t，V中其他结点的度不小于1。 因此，有: åvÎVd(v)³2(n-1)+1=2n-1，这与åvÎVd(v)=2n-2矛盾。故G中至少有两个叶子结点。4. 设T中共有x个5度点，则T总共有13+1+2+x=16+x个结点，因此共有16+x-1=15+x条边。根据握手定理可知：所有结点度数之和等

6、于边数的两倍。故13+1´3+2´4+x´5=2´(15+x)，解得x=2。即T中有2个5度点。5. 设T中共有x个叶子结点。则T共有x+100+5+2+7=x+114个结点，因此共有x+114-1=x+113条边。根据握手定理可知：x+100´2+5´3+2´4+7´5=2´(x+113)，解得：x=32。即T中包含32个叶子结点。6. 设T中共有x个叶子结点，则T中共有x+n2+nk个结点，因此共有x+n2+nk-1条边。根据握手定理可知：x+å2£i£kini =2&#

7、180;(x+å2£i£kni)，解得：x=å2£i£kini-2å2£i£kni。7. 证明：假设T中存在一个结点v，满足d(v)³k+1，则与v关联的边至少有k+1条。由树的性质可知：在树中删除任意一条边，图变为非连通图。因此，若删除与v关联的所有边，则至少得到k+2个连通分支。其中一个分支是孤立点v。在其余k+1个分支中，若分支仅包含一个结点，则该结点在T中为叶子结点；若分支至少包含两个结点，则由练习3的结论可知，该分支至少包含两个叶子结点，其中一个叶子结点必为原树T中的叶子结点。因此，T

8、至少包含k+1个叶子结点。这与T中有k片叶子矛盾。因此，T中任意结点v满足：d(v)£k。8. 红边的导出子图为最小生成树9. 证明：由树的性质可知：二元树的顶点数=m+1。在完全二元树中，除去根结点，其它结点的度数都为3或1。因此，所有顶点的度数和为：t+1´2+3´(m+1-t-1)=3m-2t+2根据握手定理：2m=3m-2t+2。故m=2(t-1)。10. 在完全三元树中，根结点的度数为3，除去根结点，设其它内部结点的数目为x，则，这些结点的度数为4；叶子结点的度数为1，设有y个。则所有结点的度数和为3+4x+y，由握手定理可知：3+4x+y为偶数，故y必

9、须为奇数，即叶子结点数目必须为奇数。11. 12. 高度最大为：2n-1；最小高度为n13. 最多有nh片树叶；最少有(h-1)(n-1)+n=h(n-1)+1片树叶。14. 若有向图的邻接矩阵中有一列值全为0，其它每列中仅有一个元素值为1。则该邻接矩阵所表示的图为有向树。值全0的列的表头元素所代表的结点为根结点；行全为0的表头元素所代表的结点为树叶结点。P228：作业1、(a)、(e)是欧拉图；(c)(d)是半欧拉图；(b)不是欧拉图。2、n为奇数3、将每个房间用图上的一个结点表示，两个房间之间若能通过一扇门连通，则在代表这两个房间的结点之间用一条边连接。则得到下图，问题等价于是否存在起始于

10、x结点，终止于P结点的欧拉通路。X结点度数为偶数，P度数为奇数，故不存在起始于x结点，终止于P结点的欧拉通路。4、(并非一定是下面这些图，只要满足题目条件即可) K5 (1) (2) (3) (4) 5、本问题等价于在图中增加权值和尽量少的边，使得添加边后的图为欧拉图。6、 (并非一定是下面这些图，只要满足题目条件即可) (1) (2) (3) (4)7、证明：任选n阶无向完全图G中两点u和v。设被删除的边集为E，令G=G-E。 若u与v相邻，则被删除的n-3条边中至多有一条边同时关联u与v，其余n-4条边至多只关联u与v中一个顶点。故dG(u)+ dG(v)³ dG(u)+ dG(

11、v)-(2+n-4)= dG(u)+ dG(v)-(n-2)。而由G是n阶无向完全图可知，dG(u)=dG(v)=n-1。因此，dG(u)+ dG(v)³2n-2-(n-2)=n。故G为哈密顿图。89、证明：不失一般性，假设G中有n个顶点，分别为v0,v1,v2,vn。因为图G是哈密顿图，故G中存在一条恰好经过G中每个顶点的回路，不妨设该回路为v0v1v2vnv0。给G中的边vivi+1添加从vi-1到vi的方向，其中i=0,1,n-1。给边vnv0。添加从vn到v0的方向，G中其他边的方向任意指定。这样得到的有向图设为G，则G中存在一条有向回路v0,v1,v2,vn。因此，G是一个

12、强连通图。命题得证。10、证明：任选G中两点u与v。由n为偶数可知：若n/2£k£n-1，则dG(u)+dG(v)=2k³n，因此G是哈密顿图。若0<k£n/2-1，则G的补图中每个结点的度数为(n-1)-k，故因此，是哈密顿图。故G和其补图至少有一个是哈密顿图。P243244，作业：2、101、(b)、(c)是二部图；(a)、(d)都有奇圈，故不是二部图。2、证明：不妨设|V1|=n1,|V2|=n2， 则n1+n2=n。显然， m£Kn1,n2包含的边数，即m£n1×n2；而n1+n2=n，故当n1=n2时，n1&

13、#215;n2取值最大。即n1×n2£(n/2)2=n2/4，故m£ n2/4。3、证明：设该简单连通平面图有r个区域。由每个区域由k条边围成可知：所有区域的边数为kr；而每条边分隔两个区域，即在计算所有区域的边数时被计算了两次，故kr=2m 由欧拉公式可知：n-m+r=2 由式消去r可得：m=k(n-1)/(k-2)4、证明：对任意一个简单平面图G，(1)若G连通，则与课本P241：引理证明类似可证结论成立。(2)若G不连通，任选G的一个连通分支，设为G1，则G1为简单连通平面图，则由课本P241：引理可知：G1中至少存在一个度数小于等于5的顶点。5、证明：设G

14、为G的一个连通分支，则G为简单连通平面图，设G的顶点数为n，边数为m。假设G中每个顶点的度数都大于等于5。则，G中所有顶点的度数和³5n；而根据握手定理：G中所有顶点的度数和=2m；因此，2m³5n 而由G是简单连通平面图可知：3n-6³m 由式可知：2m/5³n；由式可知：n³(m+6)/3，故2m/5³(m+6)/3，即m³30，这与题目条件：G的边数小于30矛盾。故G中必存在度数小于等于4的顶点，因此，G中必存在度数小于等于4的顶点。6、证明：假设G的补图是平面图。设G有n个顶点，则由n阶无向完全图的边数为n(n-1)

15、/2可知：G的补图的边数=n(n-1)/2-27。(1)若G连通由G是简单平面图可知：2n-6³27，故n³11 不妨设G的补图有k个连通分支，第i个连通分支的顶点数为ni，边数为mi。而åmi=n(n-1)/2-27。由G的补图是简单平面图可知：G的补图的每个分支也是简单平面图。因此 3ni-6³mi，进而å1£i£k(3ni-6)³ åmi，即3n-6k³ n(n-1)/2-27，而由k³1可知：3n-6³ n(n-1)/2-27化简可得：n2-7n-42£0

16、而当n³11时，有：n2-7n-42>0恒成立，故式与式矛盾。故当G连通时，G的补图不是平面图。(2) 若G不连通不妨设G有k个连通分支，第i个连通分支的顶点数为ni，边数为mi。显然，G的每个分支都是连通简单平面图，故3ni-6³mi，进而，å1£i£k(3ni-6)³ åmi=27。即3n-6k³27，由k³2可知：3n-6>27，因此：n³11 由G不连通可知：G的补图连通。又因为G的补图为简单平面图，故则3n-6³n(n-1)/2-27，化简可得：n2-7n-42&

17、#163;0 而当n³11时，有：n2-7n-42>0恒成立，故式与式矛盾。因此，故当G不连通时，G的补图不是平面图。 综上所证，G的补图不是平面图。7、证明：6个顶点的无向完全图共有(6×5)/2=15条边。而且G是简单图，故G是由K6中删除两条边得到。不难看出，从K6中任意删除两条边得到的图一定是连通图，故G连通。假设G是平面图，则有3×66³13，显然不成立。故G不是平面图。设G是由K6删除e1和e2两条边得到。由于e1和e2共为G中的点贡献了4度，故任选G中两个顶点u和v则有：d(u)+d(v)³55-4=6。故G是哈密顿图。8、证明：(1) 证法一：(a)图的边数为13，顶点数为6，不满足平面图的必要条件3n6³13，故(a)不是平面图。证法二：将(a)图中的c点删除，得到K5，故K5是(a)的子图，即(a)不是平面图。(2) 从图(b)中删除h结点，删除边：(d,c)、(d,e)、(a,c)、(e,g)可得一个二度同构与K3,3的子图，故(b)不是平面图。9、根据自对偶图的性质，5个点的对偶图G的边数为2&#