版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
作业13·P173-7.1下列各组数中,哪些能构成无向图的度数列?哪些能构成无向简单图的度数列?(1)1,1,1,2,3.能构成无向简单图的度数列.例如,(2)3,3,3,3.可以构成无向简单图的度数列,例如,12/1/20191作业13(3)1,3,3,3.不能构成无向简单图的度数列.因为有一个悬挂点,则其余三个顶点度数不可能均为3,但可构成无向图的度数列,例如,12/1/20192作业1312/1/20193P173-7.5
下面各无向图中有几个顶点?(2)21条边,3个4度顶点,其余的都是3度顶点.解.设该图有n个顶点,则由握手定理3×4+(n-3)×3=2×21,解得,n=13.故该图有13个顶点.P173-7.635条边,每个顶点的度数至少为3的图最多有几个顶点?解.设该图最多有n个顶点,由握手定理3n≤35×2,则
n≤[70/3]=23.故该图最多有23个顶点.作业13P173-7.13设G1,G2,G3均为4阶无向简单图,它们均有两条边,它们能彼此均非同构吗?为什么?解.G1,G2,G3彼此不能均非同构.因为4阶2条边的非同构无向简单图只有2个.事实上,因为图只有两条边,故总度数为4,且为无向简单图,因而每个顶点度数最多为2.将4分解为4个数的和且每个数
不超过2,得下面3组数:(0,0,2,2),
(0,1,1,2),
(1,1,1,1)而(0,0,2,2)不可能是一4阶2条边的无向简单图的度数列,因2个顶点为孤立点,则另两个顶点的度数最多为1,否则,会出现平行边或环.所以(4,2)图只有2个非同构的图,如上图.12/1/20194作业14补充1
(1)若无向图G中只有两个奇度顶点,则这两个奇度顶点一定是连通的.(2)若有向图D中只有两个奇度顶点,则它们一个可达另一个或相互可达吗?(1)证明.设G中的两个奇度顶点分别为u和v,若u和v不连通,即它们之间无任何通路,则G至少有两个连通分支
G1,G2,使得u和v分别属于G1和G2,于是G1和G2中各有1
个奇度顶点,这与握手定理的推论矛盾.因而u和v一定是连通的.(2)解.有向图D中只有两个奇度顶点u和v,则u与v不一定相互可达,也不一定一个可达另一个.如右图,顶点u和v的度数均为1,w的度数为2,但u不可达v,v也不可达u.12/1/20195作业1412/1/20196补充2
设G是n阶无向简单图,如果G中每一对顶
点的度数之和均大于等于n-1,那么G是连通图.证明.假设G不是连通图,则G至少有两个连通分支
G1,G2,设G1中有n1个顶点,G2中有n2个顶点,则n1+n2≤n.分别从G1和G2中任取一个顶点u,v,由于G是简单图,从而G1和G2也都是简单图,所以d(u)≤n1-1,d(v)≤n2-1,故d(u)+d(v)≤n1+n2-2≤n-2,与题设矛盾.作业14P174-7.18有向图D如下图所示.求D中长度为4的通路总数,并指出其中有多少条是回路?又有几条是v3到v4的通路?解.图D的邻接矩阵为则4由A得,∑∑aij=15,∑aii=3,a34=2,故D中长度为4的3
42条.通路有15条i=,1j其=1
中有3条i=回1
路,从v
到v
长度为4的通路有12/1/201974
4
4(4)(4)
(4)作业14P203-9.1设无向树T有3个3度顶点,2个2度顶点,其余顶点都是树叶,问T有几片树叶?解.设T有t片树叶,则T的总顶点数为3+2+t,总边数为
3+2+t-1=4+t,由握手定理,有2(4+t)=3×3+2×2+t,解得t=5,故T有5片树叶.P203-9.4已知n(n≥2)阶无向简单图G有n-1条边,G一定为树吗?解.不一定.如G为非连通图时就不是树.例如,在图G中,n=5,m=4,m=n-1,但G不是树.12/1/20198作业14P203-9.7在下图所示的无向图G中,实线边所示的子图为G的一棵生成树T,求G对应于T的基本回路系统和基本割集系统.解.对应于弦c的基本回路为:Cc=adcb,对应于弦e的基本回路为:Ce=ade,对应于弦g的基本回路为:Cg=agf,对应于弦h的基本回路为:Ch=afhb,所以对应于T的基本回路系统为:{adcb,ade,agf,afhb}.对应于树枝a的基本割集为:Sa={a,e,c,g,h},对应于树枝b的基本割集为:Sb={b,c,h},对应于树枝d的基本割集为:Sd={c,d,e},对应于树枝f的基本割集为:Sf={f,g,h},所以T的基本割集为:{{a,e,c,g,h},{b,c,h},{c,d,e},{12/1/20199作业14P203-9.8求下图所示两带权图的最小生成树,并计算它们的权.解.(a)的最小生成树为
T1,如下图.T1的权为:
W(T1)=1+2+3+1=7.(b)的最小生成树为
T2,如右图.T2的权为:
W(T2)=1+2+4+4=11.12/1/201910作业15P204-9.11下图给出的2元树表达一个算式.给出这个算式的表达式;给出算式的波兰符号法表达式;
(3)给出算式的逆波兰符号法表达式.解.(1)((a+b×c)×d-e)÷(f+g)+h×i×j.(2)+÷-×+a×bcde+fg××hij.(3)abc×+d×e-fg+÷hi×j×+.12/1/201911作业15P204-9.13设7个字母在通信中出现的频率如下:a:35%,b:20%,c:15%,d:10%,e:10%,f:5%,g:5%.求传输这7个字母的最佳前缀码.解.以100乘各频率并由小到大排列为:w1=5,w2=5,w3=10,w4=10,w5=15,w6=20,w7=35.用huffman算法求带权为
w1,w2,w3,w4,w5,w6,w7的最优2元树如右图.最佳前缀码为:{01,11,001,100,101,0000,0001}.对应的码子传输的字母为:11传a,01传b,101传c,100传d,001传e,0001传f,0000传g.12/1/201912作业15P188-8.3完全二部图Kr,s中,边数m为多少?解.Kr,s中,边数m为:m=rs.P188-8.6画一个无向欧拉图,使它具有:(1)偶数个顶点,偶数条边;
(2)奇数个顶点,奇数条边;
(3)偶数个顶点,奇数条边;
(4)奇数个顶点,偶数条边.解.(1)
(2)
(3)(4)12/1/201913作业15P189-8.8画一个无向图,使它是:(1)既是欧拉图,又是哈密尔顿图;
(2)是欧拉图,而不是哈密尔顿图;
(3)是哈密尔顿图,而不是欧拉图;(4)既不是欧拉图,也不是哈密尔顿图.解.(1)
(2)
(3)
(4)12/1/201914作
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年全钢丝子午胎成形机合作协议书
- 2024年超硬复合材料合作协议书
- 2024年固有荧光早期癌症诊断仪项目合作计划书
- 2024年贵金属压延加工材合作协议书
- 2024年室内环保检测仪器合作协议书
- 2024年自动包装设备项目合作计划书
- 2024年数字视频切换台项目建议书
- 2024年玻璃浮球项目发展计划
- 2024年旋片真空泵项目建议书
- 2024年摩托车零部件及配件项目发展计划
- 第二型曲面积分PPT课件
- 金属盐类溶度积表
- 海尔集团员工守则
- 牛皮基础知识
- 股权收购备忘录(定稿)
- PFC电感计算(周洁敏)
- 安全带检测报告
- 租房合同模板
- 八年级数学上册三角形复习优质课教案
- (完整版)挖掘机安全技术交底.doc
- 环卫管理人员岗位职责
评论
0/150
提交评论