资源描述：
《离散图论习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、以下内容供参考！欢迎补充~~~14.19.19.设G是n阶自补图,证明n=4k或n=4k+1,其中k为正整数.设G是n阶m条边的自补图,则G为n阶m条边的简单图,且G≅⎯G.于是,⎯G的边数m'=m,且m+m'=2m=n(n−1)/2.于是n(n−1)=4m,因而n=4k,或n−1=4k,k为正整数.14.21.21.无向图G如图14.19所示.(1)求G的全部点割集和边割集,并指出其中的割点和桥(割边);(2)求G的点连通度κ(G)和边连通度λ(G).(1)点割集两个{a,c},{d},d是割点.7个边割集:{e5},{e1,e3},{e2,e4},{e1,e2},{e2,e
2、3},{e3,e4},{e1,e4},e5是桥.(2)因为既有割点又有桥,所以κ=λ=1.14.22.22.无向图G如图14.20所示,现将该图顶点和边标定.然后求图中的全部割点和桥,以及图的点连通度和边连通度.第14题答图标定如答图.3个割点:d,f,h.3个桥:e5,e9,e10.因为既有割点又有桥,所以κ=λ=1.14.23.23.求图14.21所示图G的κ(G),λ(G)和δ(G).κ=2,λ=3,δ=4.14.43.43.有向图D如图14.22所示.(1)D中有多少种非同构的圈?有多少种非同构的简单回路?答：有2种非同构的圈，长度为2和3；有3种非同构的简单回路，
3、长度为2，3，5(2)求a到d的短程线和距离d.a到d的短程线为aed，d=2(3)求d到a的短程线和距离d.d到a的短程线为deba，d.=3(4)判断D是哪类连通图.单向连通图(5)对D的基图讨论(1),(2),(3)三个问题.答：有4种非同构的圈，长度为2，3，4,5；有7种非同构的简单回路除了4种非同构的圈外，还有3种非圈的简单回路。长度为5,6,8；a到d的短程线有3条，d=2d到a的短程线有3条d=215.14.14.今有n个人,已知他们中的任何二人合起来认识其余的n−2个人.证明:当n≥3时,这n个人能排
4、成一列,使得中间的任何人都认识两旁的人,而两旁的人认识左边(或右边)的人.而当n≥4时,这n个人能排成一个圆圈,使得每个人都认识两旁的人.作n阶简单无向图G=,V=这n个人的集合,E={(u,v)
5、u,v∈V∧u≠v∧u与v认识}.∀u,v∈V,.(1)若u,v相邻,则d(u)+d(v)≥(n−2)+2=n.(2)若u,v不相邻,则∀w∈V−{u,v},w必与u和v都相邻.否则,比如u和w不相邻,则v,w都不邻接u,于是u和w合起来至多与其余的n−3个人认识,与已知条件不符.因而d(u)+d(v)≥2(n−2).当n≥3时,2(n−2)≥n−1,因此无论第(1)或(2
6、)种情形,都有d(u)+d(v)≥n−1,由定理15.7知G中有哈密顿通路,通路上的人按在通路中的顺序排成一列,满足要求.当n≥4时,2(n−2)≥n,因此无论第(1)或(2)种情形,都有d(u)+d(v)≥n,由定理15.7的推论知G中有哈密顿回路,回路上的人按在回路中的顺序排成一个圆圈,满足要求.15.15.15.某工厂生产由6种不同颜色的纱织成的双色布.已知在品种中,每种颜色至少能与其他5中颜色中的3种相搭配.证明可以挑出3种双色布,他们恰由6种不同颜色的纱织成.作无向简单图G=,V={v
7、v为6种颜色的纱之一},
8、V
9、=6,E={(u,v)
10、u,v∈V∧u≠v
11、∧u与v能搭配}.由给出的条件知,∀u,v∈V,有d(u)+d(v)≥3+3=6=
12、V
13、.由定理15.7的推论知,G是哈密顿图,因而有哈密顿回路,设C=vi1vi2vi3vi4vi5vi6vi1为其中的一条.任何两个顶点在C中相邻,说明这两个顶点代表的颜色的纱可以搭配成双色布.让vi1与vi2的搭配,vi3与vi4的搭配,vi5与vi6的搭配就可以织成3种双色布,恰用了6种不同的颜色.16.26.26.设T为非平凡树,Δ(T)≥k,证明T至少有k片树叶.证法一设T中有x片树叶,则T中有n−x个分枝点(度数≥2),其中至少有个1个顶点度数为Δ(≥k).由树的性质及握手定理知2m=
14、2(n−1)=Σd(v)≥x⋅1+(n−x−1)⋅2+Δ.整理得x≥Δ≥k.16.29.29.设G为n(n≥5)阶简单图,证明G或⎯G中必含圈.首先利用第23题的结论确认无圈的图(森林)的边数m=n−p≤n−1.(反证法)假如G和⎯G都不含圈,则1/2n(n−1)=
15、E(Kn)
16、=
17、E(G)
18、+
19、E(G)
20、≤2(n−1),于是n(n−4)≤0,而这与(n≥5)矛盾.16.31(1)4(2)4(3)5(4)6讲过的例题：P315例16.5P312例16.3(例15.3有没讲？）
