第八章 图论_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
第八章 图论
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩47页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
4~离散数学习题解答习题六(第六章图论)6..doc 33页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：150 &&
你可能关注的文档：
·········
········
离散数学习题解答
1．从日常生活中列举出三个例子，并由这些例子自然地导出两个无向图及一个向图。
[解] ①用V代表全国城市的集合，E代表各城市间的铁路线的集合，则所成之图G=（V，E）是全国铁路交通图。是一个无向图。
②V用代表中国象棋盘中的格子点集，E代表任两个相邻小方格的对角线的集合，则所成之图G=（V，E）是中国象棋中“马”所能走的路线图。是一个无向图。
③用V代表FORTRAN程序的块集合，E代表任两个程序块之间的调用关系，则所成之图G+（V，E）是FORTRAN程序的调用关系图。是一个有向图。
2．画出下左图的补图。
[解] 左图的补图如右图所示。
3．证明下面两图同构。
[证] 存在双射函数(:V→V′及双射函数( : E→E′
( (v1)=v1′
( (v1，v2)=(v1′，v2′)
( (v2)=v2′
( (v2，v3)=(v2′，v3′)
( (v3)=v3′
( (v3，v4)=(v3′，v4′)
( (v4)=v4′
( (v4，v5)=(v4′，v5′)
( (v5)=v5′
( (v5，v6)=(v5′，v6′)
( (v6)=v6′
( (v6，v1)=(v6′，v1′)
( (v1，v4)=(v1′，v4′)
( (v2，v5)=(v2′，v5′)
( (v3，v6)=(v3′，v6′)
显然使下式成立：
( (vi，vj)=(vi,vj′)( ( (vi)=v i′∧( (vj)=vj′
(1≤i·j≤6)
于是图G与图G′同构。
4．证明（a），（b）中的两个图都是不同构的。
图G中有一个长度为4的圈v1v2v6v5v1，其各顶点的度均为3点，而在图G′中却没有这样的圈，因为它中的四个度为3的顶点v1(，v5(，v7(，v3(不成长度的4的圈。
图G′中有四个二度结点，v6(，v8(，v4(，它们每个都和两个三度结点相邻，而G中一个区样的结点都没有。
在（b）中，图G(中有一2度结点v3(，它相邻的两个项点v2(，v4(的度均为4，而在图G中却没有这样的点。
5．一个图若同构于它的补图，则称此图为自补图。在满足下列条件的无向简单图中：
1) 给出一个五个结点的自补图；
2)有三个或一结点的自补图吗？为什么？
3）证明：若一个图为自补图，则它对应的完全图的边数不清必然为偶数。
[解] 1) 五个结点的自补图如左图G所示
同构函数( : V→V及( : E→如下：
((a，b)=(a，c)
((b，c)=(c，e)
((c，d)=(e，d)
((d，e)=(b，d)
(e，a)=(d，a)
2)（a=3为奇数，所以由下面3)的结论，不可能有自补图。
（b）有五个结点的自补图。1）中的例子即是一个五个结点的自补图。
3）证：一个图是一个自补图，则它对应的完全图的边数必为偶数。
因为若一个图G是自补图，则G∪=对应的完全图，而且E∩=φ，G现同构，因此它们的边数相等，即|E|=||，因此对应的完全图的边数|E*|=|E|+||=2|E|，是偶数。
实际上，n个项点（n＞3）的自补图G，由于其对应的完全图的边数|E*|=，因此有=2|E|，为偶数。这里n≥4。对于所有大于或等于4的正整数，都可表达成n=4k，4k+1，4k+2，4k+3的形式，这里k=1，2，…。其中只有n=4k，4k+1，才能使为偶数，所以自补图的项点数只能是4k或4k+1形式，（k∈N）
6．证明在任何两个或两个以上人的组内，总存在两个人在组内有相同个数的朋友。
[证] 令上述组内的人的集合为图G的项点集V，若两人互相是朋友，则其间联以一边。所得之图G是组内人员的朋友关系图。显然图G是简单图，图中项点的度恰表示该人在组内朋友的个数，利用图G，上述问题就抽象成如下的图认论问题：在简单图G中，若|V|≥2，则在G中恒存在着两个项点，v1，v2∈V，使得它们的度相等，即deg(v1)=deg(v2)。其证明如下：
若存在着一个项点v∈V，使得deg(v)=0，则图G中各项点的度最大不超过n-2。因此n个项点的度在集合{0，1，2，…，n-2}里取值，而这个集合只有n-1个元素，因此，根据鸽笼原理，必有两个项点的度相同。
若不存在一个度为零的项点，则图G中各项点的度最大不超过n-1。因此n个项点的度在集合{1，2，…，n-1}中取值，这个集合只有n-1个元素，因此，根据鸽笼原理，必有两具项点的度相同。
正在加载中，请稍后...
56页58页160页82页56页42页18页57页68页42页扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
证明：若n阶简单无向图G的任意两个结点的度数之和大于等于n-1,则G是连通的.我也搜到“假设G有两个连通分支G1和G2,那么取v1是G1中度数最小的顶点,v2是G2中度数最小的顶点,则d(v1)+d(v2)≤n-2（等号在G1和G2都是完全图时取到）,这与条件矛盾.” 我希望有一个正规的步骤……我确实不懂这个……
作业帮用户
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
假设G不是连通的则G至少有两个连通分支G1和G2,有 |G1|+|G2| ≤ |G| = n任取G1中一点v1,G2中一点v2则d(v1)≤|G1|-1,d(v2)≤|G2|-1d(v1)+d(v2) ≤ |G1|+|G2|-2 ≤ n-2,与条件矛盾
为您推荐：
其他类似问题
假设G有两个连通分支G1和G2，那么取v1是G1中度数最小的顶点，v2是G2中度数最小的顶点，则d(v1)+d(v2)≤n-2（等号在G1和G2都是完全图时取到）
扫描下载二维码君，已阅读到文档的结尾了呢~~
离散习题(附答案) (9)
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
离散习题(附答案) (9)
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口第七章特殊图类；习题7.1；1.设树T有6条边，试问T有多少个结点？；2．若无向图G中有n个结点，n-1条边，G为树；7．在图7-2中，⑴，⑵所示的连通图中各有几棵非；⑴⑵；图7-2；8．在图7-4中所示的带权图G共有多少棵生成树，；c9．用Kruskal算法，求图7-6的最小生成；-6；；习题7.2；1.一个有向图G，仅
特 殊 图 类 习题7.1 1. 设树T有6条边，试问T有多少个结点？ 2．若无向图G中有n个结点，n-1条边，G为树。这个命题正确吗？为什么？ 3．设无向图G有n个结点，n-1条边，则G为连通图当且仅当G中无回路。 4. 设G是一个森林，由3个连通分支组成，若它有15个结点，试问G有多少条边？ 5. 画出具有6个结点的所有不同构的树。 6. 任何一棵非平凡树中，至少有两片树叶。 7．在图7-2中，⑴，⑵所示的连通图中各有几棵非同构的生成树？ ⑴ ⑵ 图7-2
8．在图7-4中所示的带权图G共有多少棵生成树，它们的权各为多少？其中哪些是图中的最小生成树？
b a 1 3 2 2 d 4 图7-4 c 9．用Kruskal算法，求图7-6的最小生成树，并计算出该生成树的权。 1 9 6 3 10 4 图7-6 5 8 7 2 11
91 习题7.2 1. 一个有向图G，仅有的一个结点入度为0，其余所有结点的入度均为1，G一定是根树吗？ 2. 五个结点可以形成多少棵根树？并指出这些根树都是几元树。 3．根树中最长路径的端点都是树叶吗？为什么？ 4．证明本节定理4（完全二元树有奇数个结点）。 5．对图7-10给出的二元树分别进行先根遍历、中根遍历、后根遍历并写出结果。 6．求带权2、3、5、7、8、11的最优树。 a 习题7.3 d 1．在图7-12所示的三个图中，哪几个是偶图？哪几个不是偶图？是偶图的，请给出互补结点子集；不是偶图的，请说明理由。 2. 试证明树是一个偶图。 a b d c e g (1) f b (2) 图7-12 c g b (3) a e f a d e f g c b e g 图7-10 c h i f
3. 一次舞会，共有n位男士和n位女士参加，已知每位男士至少认识两位女士，而每位女士至多认识两位男士，问能否将男士和女士分配为n 对，使得每对中的男士和女士彼此都认识？ 4. 今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周三人只熟悉数学、物理两门课程。问能否安排他们五人每人只上一门自己熟悉的课程，使得每门课程都有人教。说明理由。 习题7.4 1．试证明图7-13所示的两个图均为平面图。
92 a e i h d (1)
e a i d h (1) c b f g f b b a f c c 图7-13 b d d (2)
f a g 图7-14 c (2) e
2．指出图7-15所示的两个图各有几个面；写出每个面的边界和秩。 a b c d b c a d e e (1) 图7-15 f (2)
3．试证明：在有6个结点、12条边的连通简单图中，每个面均由3条边围成。 4．指出图7-16所示的图为非面图。
93 5．在简单平面图G中，至少有一个度数小于等于5的结点。 6．证明小于30条边的简单平面图G中至少有一个度数小于等于4的结点。
复习题7 1．一棵树T有5个2度结点，3个3度结点，4个4度结点，2个5度结点，其余都是1度结点，问T有多少个1度结点？ 2．设无向图G是连通图，试证明m≥n -1. 3．设无向图G是森林，且G有p个连通分支，试证明：m?n?p.
4．T1和T2是连通图G的两棵不同的生成树，a是在T1中但不在T2中的一条边。试证明存在边b，它在T2中但不在T1中,使得（T1?{a})?{b}和(T2?{b})?{a}都是G的生成树。 5．设无向图G是有k,(k?2)棵构成的森林，至少在G中添加多少条边才能使G成为一棵树？ 6. 用Kruskal算法求图7-18(a)的一棵最小生成树。 a 16 b 7 8 5 6 c 9 13 (a) d 4 6 e
7．图7-19⑴给出的赋权图表示7个城市a,b,c,d,e,f,g及架起城市间直接通讯线路的预测造价，试给出一个设计方案使得各城市之间能够通信且总造价最小，要求计算出最小总造价。
7-18 图 94 a 23 f 28 36 8 e 20 1 4 g 16 17 b 15 9 3 d c ⑴
8．画出所有不同构的高为2的二元树，其中有多少棵完全二元树？有多少棵满二元树？ 9．设T为任意一棵完全二元树，m为边数，t为树叶数，试证明：m?2t?2。其中t?2。 10．证明：若T是有n个结点的完全二元树，则T有(n?1)/2片树叶。 11．分别用先根、中根和后根的次序遍历如图7-21`所示的二元树。 12．根据图7-22中所示的两棵二元树，产生两个前缀码。
图7-19 ⑴ ⑵ 图7-22 13．⑴求带权2，3，5，7，8的最优二元树T。 ⑵求T对应的二元前缀码。
95 10 5 2 ⑴ 3 2 5 3 ⑵ 25 5 10 5 2 3 ⑶ 5 7 15 8 2 5 10 15 5 7 3 ⑷ 8 图7-24
14．在通信中要传输八进制数字0，1，2，…，7。这些数字出现的频率为： 0：30；1：20；2：15；3：10；4：10；5：60；6：5；7：4。 如何编一个二元前缀码，使通讯中出现的二进制数字尽可能地少。具体要求如下： ⑴ 画出相应的二元树； ⑵ 写出每个数字对应的前缀码； ⑶ 传输按上述比例出现的数字10000个时，至少要用多少二进制数字？ 15．证明如果G是二部图，它有n个顶点，m条边，则m?n/4。
16．某单位按编制有7个空缺P1，P2，…，P7。有10个申请者a1，a2，…，a10，他们的合格工作岗位集合依次是：{ P1, P5, P6}，{ P2, P6, P7}，{ P3, P4}，{ P1, P5}，{P6, P7}，{ P3}，{ P2, P3}，{ P1, P3}，{P1}，{P5}。如何安排他们工作使得无工作的人最少？ 17．在某单位有6个未婚女青年L1，L2，L3，L4，L5，L6，有6个未婚男青年G1，G2，G3，G4，G5，G6，他们都想结婚，但也不是随便哪一个都可以，他们心中都有一张表，只愿意和表上的人结婚，现在知道L1，L2…，L6的表分别是：
L1: { G1, G2, G4};
L2: { G3, G5};
L3: { G1, G2, G4};
L4: { G2, G5, G6};
L5: { G3, G6};
L6: { G2, G5, G6}
G1, G2…，G6的表分别是：
G1: { L1, L3, L6}
G2: { L2, L4, L6}
G3: { L2, L5}
G4: { L1, L3}
G5: { L2, L6}
G6: { L3，L4，L5}
请问如何分配，使得男女双方都满意且结婚的对象最多。 2 96 三亿文库3y.uu456.com包含各类专业文献、应用写作文书、中学教育、外语学习资料、行业资料、专业论文、71第七章 特殊图类等内容。　
　效果图 7.4 轮廓图效果 7.4.1 制作轮廓图效果 绘制一个图形,选择“交互式...章节 名称 章节 分析 教学步骤 第七章 图形的特殊效果 计划 学时 2 学时 ... 　第七章 习题 7.1 1.解因 m=n-1,这里 m=6,所以 n=6+1=7. 特殊图类 2.解 不正确。 K 3 与平凡图构成的非连通图中有 4 个结点 3 条边,但是它... 　第​七​章​ ​特​殊​图​类第七章习题 7.1 特殊图类 1. 设树 T 有 6 条边,试问 T 有多少个结点? 2.若无向图 G 中有 n 个结点... 　第七章 专题讲座三 化学平衡图像_理化生_高中教育_教育专区。一、传统图像的...(如下图);M 点后为平衡受温度的影响情况,即升温,A 的百分含量增加 或 C ... 　第七章平面图形的认识(二)复习教学案_数学_初中教育_教育专区。word版,专题复习...(2005 宜昌)在 5×5 方格纸中将图 7-7(1)中的图形 N 平移后的位置如图... 　新闻 网页 贴吧 知道 音乐 图片 视频 地图 百科...7十年药综 第七章 特殊人群的用药指导(12分左右)...洛尔类 07B 维 A 酸 07B 晚期:阿司匹林 09B P... 　离散数学讲义 武汉科技大学计算机学院 第七章 特殊关系重点:等价关系、偏序关系的各种性质的判断和证明; 难点: 如何正确地掌握等价关系及相应的等价类与集合划分之间... 　第七章 控制图 95 第七章 控制图前言: 一. 前言: 为使现场的质量状况达成...(i)绘制中心线及控制界限,并将各点点入图中. (j)将各数据履历及特殊原因...