离散作业14(2).pdf
- 文档编号:14648755
- 上传时间:2023-06-25
- 格式:PDF
- 页数:5
- 大小:450.07KB
离散作业14(2).pdf
《离散作业14(2).pdf》由会员分享,可在线阅读,更多相关《离散作业14(2).pdf(5页珍藏版)》请在冰点文库上搜索。
1(1points)非同构生成子图画出k4的所有非同构的生成子图。
2(1points)握手定理设无向图G中只有两个奇度顶点u与v,试证明u与v必连通.答案答案用反证法。
假设u与v不连通,即u与v之间无通路,则u与v处于G的不同连通分支中。
不妨设u在G1,v在G2中。
于是,G1与G2作为G的子图,他们中均只含有一个奇度顶点,这与握手定理的推论矛盾。
3(1points)扩大路径法设D=为有向简单图,已知(D)2,且(D)0,+(D)0,证明D中存在长度大于等于max(D),+(D)+1的圈。
答案答案证明:
(1)当-+时,证明D中存在长度大于等于-+1的圈。
使用扩大路径法的极大路径=v0v1vl,则l-。
这是因为,无外的顶点邻接到v0,v0要达到它的入度d-(v0)-只能是上的顶点邻接到它,因而在上存在邻接到v0。
于是为D中长度大于等于-+1的圈(见示意图)。
(2)当+-时,证明D中存在长度至少为+1的圈。
依然使用扩大路径法,设=v0v1vl为极大路径。
由于vl不邻接到外的顶点,要使d+(vl)+,vl至少邻接到上的+个顶点,于是为D中长度大于等于+1的圈,见示意图。
4(1points)边足够多的连通性设n阶无向简单图G有m条边,已知m(n-1)(n-2)/2,证明G必连通答案答案证明:
在证明本题中,要用到
(1)任何n阶简单图的边数m均小于等于完全图Kn的边数n(n-1)。
(2)若G中无孤立点,则(G)1。
用归纳法。
n=1时,G为平凡图,显然G连通。
n=2时,m(n-1)(n-2)+1=1,此时G为K2,当然连通。
设n=k(k2),m(k-1)(k-2)+1时结论成立,要证明当n=k+1,mk(k-1)+1时结论也成立。
下面分三步证明:
(i)若G为Kk+1,G当然连通。
(ii)若G中含孤立点,一定推出矛盾。
删去G中的孤立点,记作G1。
则G1的边数mk(k-1)+1,这与G1为阶数小于等于k的简单图矛盾,故G中不可能含孤立点。
(iii)由(i)、(ii)可知,只需对G不为完全图、又不含孤立点的情况加以证明。
G中存在v0,使1d(v0)k-1(G中无孤立点,又不是k+1阶完全图),令G=G-v0,则G为k阶简单图,且G的边数mk(k-1)+1-(k-1)=(k(k-1)-(k-1)+1=(k-1)(k-2)+1由归纳假设可知,G是连通图,而G为G的子图,故G也连通。
分析分析做过本题后,我们可以思考这样的问题:
n阶简单非连通图的边最多可以为多少条?
其实,n阶简单非连通图的边数最多可以为(n-1)(n-2)条一个平凡图与一个Kn-1构成的非连通图,他们边数为(n-1)(n-2)。
在此基础上,再加一条边所对应的无向简单图,就一定连通了。
5(1points)边足够多的连通性设G为n阶无向简单图,证明以下题目:
(1)当(G)时,证明G连通。
(2)当(G)(n+k-1)时,证明G是k-连通图。
提示提示使用反证法。
答案答案
(1)要用到n阶简单图的最大度n-1。
用反证法。
假设G至少有两个连通分支,设G1,G2为其中的两个,并设G1,G2的阶数分别为n1和n2,则n1+n2n,且minn1,n2。
于是,对任意的vV(G1),dG1(V)=dG(V)-1,这与(G)矛盾,所以G连通。
(2)利用
(1)的结果。
要证明G是k-连通图,只需证明从G中删除任意(k-1)个顶点后,所得图依然连通。
设V为V(G)的任意子集,且|V|=k-1。
令G=G-V,则G为n-(k-1)=n-k+1=n阶无向简单图,而(G)(G)-(k-1)(n+k-1)-(k-1)=(n+k-1-2k+2)=(n-k+1)=n由
(1)可知,G连通,故G为k-连通图。
6(1points)各种路径图D如下1.D中有几种非同构的圈?
2.D中有几种非圈的非同构的简单回路?
3.D是哪类连通图?
4.D中V1到V4长度为1,2,3,4的通路各有多少条?
并指出其中有几条是非初级的简单通路?
5.D中V1到V1长度为1,2,3,4的回路各为多少条?
并讨论它们的类型。
6.D中长度为4的通路(不含回路)有多少条?
7.D中长度为4的回路有多少条?
8.D中长度小于等于4的通路共有多少条?
其中有几条是回路?
9.写出D的可达矩阵。
(1)D中有中有3种非同构的圈,长度分别为种非同构的圈,长度分别为1,2,3,请画出它们的图形,请画出它们的图形.
(2)D中有中有3种非圈的非同构的简单回路,它们的长度分别为种非圈的非同构的简单回路,它们的长度分别为4,5,6.请画出它们的图形来请画出它们的图形来.(3)D是强连通的(为什么?
)是强连通的(为什么?
)为解为解(4)(8),只需先求,只需先求D的邻接矩阵的前的邻接矩阵的前4次幂次幂.(5)v1到到v1长度为长度为1,2,3,4的回路数分别为的回路数分别为1,1,3,5.其中长度为其中长度为1的是初级的的是初级的(环环);长度为;长度为2的是复杂的;的是复杂的;长度为长度为3的中有的中有1条是复杂的,条是复杂的,2条是初级的;长度为条是初级的;长度为4的有的有1条是复杂的,有条是复杂的,有4条是非初级的简单回条是非初级的简单回路路.请在图中行遍以上各回路请在图中行遍以上各回路.(6)长度为长度为4的通路的通路(不含回路不含回路)为为33条条.(7)长度为长度为4的回路为的回路为11条条.(8)长度长度4的通路的通路88条,其中条,其中22条为回路条为回路.(9)44的全的全1矩阵矩阵.1222234412222465012112220121222310010121100102210100100101000021432AAAA(4)v1到到v4长度为长度为1,2,3,4的通路数分别为的通路数分别为0,0,2,2.其中只有长度为其中只有长度为4的两条是非初级的简单的两条是非初级的简单通路(定义意义下),见下图所示通路(定义意义下),见下图所示.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散 作业 14