标签:   离散   数学   第十章   基本   算法   习题   答案  
文档信息
上传用户 充满希望的奔跑     
文档格式 ppt
文档价格 6.8 元
文档大小 284 KB
文档页数 13 页
相关文档推荐
ppt 《抑郁症及其药物》PPT课件
doc 2020年一级建造师《建筑工程管理与实务》综合练习C卷 附解析
doc 实验小学二年级数学下学期开学考试试题赣南版(II卷) 附解析
doc 2020年六年级数学【上册】期末考试试题外研版C卷 附答案
doc 实验小学二年级数学下学期开学考试试题赣南版(II卷) 含答案
doc 云南省2020年实验小学一年级语文【下册】开学考试试卷 含答案
doc 2020年六年级数学【上册】期末考试试题外研版C卷 含答案
doc 山东省重点小学三年级数学【下册】开学摸底考试试题 (附解析)
doc 云南省2020年实验小学一年级语文【下册】开学考试试题 附解析
doc 实验小学二年级数学下学期开学考试试题部编版C卷 含答案
doc 云南省2020年实验小学一年级语文【下册】期中摸底考试试题 附解析
ppt 《把铁路修的拉萨》PPT课件
doc 山东省重点小学三年级数学【下册】开学摸底考试试题 含答案
doc 实验小学二年级数学下学期开学考试试题豫教版C卷 含答案
doc 2019-2020学年高二英语下学期3月月考试题 (I)
doc 山东省重点小学三年级数学【下册】开学摸底考试试卷 (附答案)
doc 2020年一级建造师《建筑工程管理与实务》综合练习C卷 含答案
doc 实验小学二年级数学下学期开学考试试题赣南版 附解析
doc 广东省重点小学四年级数学下学期期末摸底考试试题B卷 含答案
doc 云南省2020年实验小学一年级语文【下册】开学摸底考试试卷 含答案
doc 实验小学二年级数学下学期开学考试试题赣南版 含答案
doc 2019-2020年高三上学期期中质量监测化学试题 含答案
ppt 离散数学第四章谓词演算的推理理论-归结推理系统
doc 广东省重点小学四年级数学下学期期末摸底考试试题B卷 (附答案)
doc 实验小学二年级数学下学期开学考试试题部编版B卷 附解析
doc 云南省2020年实验小学一年级语文【下册】开学摸底考试试卷 附解析
ppt 《抑郁症与药物治疗》PPT课件
doc 2019-2020学年高二英语上学期阶段考试试题二
ppt 《抓住特征介绍动物》课件
doc 2020年一级建造师《建筑工程管理与实务》综合练习A卷 (附解析)
doc 2019-2020年高三上学期期中质量检测语文试卷含解析
doc 2020年六年级数学【上册】期末考试试题外研版 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试题A卷 附解析
ppt 离散数学第十二章代数结构基本概念及性质
doc 2019-2020年高三上学期期中质量检测英语试题含答案
doc 2019-2020年高三上学期期中质量监测理综试题 含答案
doc 2019-2020学年高二英语下学期2月开学检测试题
doc 云南省2020年实验小学一年级语文【下册】开学摸底考试试卷 附答案
doc 2020年六年级数学【上册】期末考试试题北师大版(II卷) 附解析
doc 2019-2020年高三上学期期中质量检测理科数学试题含答案
doc 实验小学二年级数学下学期开学考试试题赣南版(I卷) 含答案
doc 2019-2020学年高二英语上学期阶段性测试试题
doc 实验小学二年级数学下学期开学考试试题豫教版C卷 附答案
doc 云南省2020年实验小学一年级语文【上册】期末摸底考试试题 附答案
doc 2019-2020学年高二英语下学期2月模块诊断试题
doc 云南省2020年实验小学一年级语文【下册】期中考试试题 附解析
doc 实验小学二年级数学下学期开学考试试题豫教版(II卷) 附解析
ppt 《把铁路修到拉萨去》PPT课件
doc 实验小学二年级数学下学期开学考试试题部编版B卷 含答案
doc 山东省重点小学三年级数学【下册】开学摸底考试试题 附答案
doc 实验小学二年级数学下学期开学考试试题部编版A卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试题B卷 附答案
doc 实验小学二年级数学下学期开学考试试题赣南版B卷 含答案
doc 山东省重点小学三年级数学【下册】开学摸底考试试题 附解析
doc 2020年一级建造师《建筑工程管理与实务》综合练习A卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试题A卷 (含答案)
doc 山东省重点小学三年级数学【下册】开学考试试卷 附解析
doc 2020年六年级数学【上册】期末考试试题外研版 (附答案)
doc 2019-2020学年高二英语上学期阶段联考试题(二)
ppt 《抑郁症的临床表现》PPT课件
doc 云南省2020年实验小学一年级语文【下册】开学摸底考试试题 含答案
doc 云南省2020年实验小学一年级语文【下册】期中考试试卷 附解析
ppt 离散数学第十一章
ppt 《把道理想深想透》PPT课件
doc 实验小学二年级数学下学期开学考试试题部编版C卷 附解析
doc 2020年一级建造师《建筑工程管理与实务》综合练习C卷 (附答案)
doc 2019-2020年高三上学期期中阶段性测评 化学
doc 2020年一级建造师《建筑工程管理与实务》综合练习A卷 (含答案)
doc 山东省重点小学三年级数学【下册】开学考试试题 附答案
ppt 《抑郁症发生的原因》PPT课件
doc 2020年六年级数学【上册】期末考试试题北师大版B卷 附解析
doc 实验小学二年级数学下学期开学考试试题豫教版(II卷) 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试题B卷 (附解析)
doc 2020年一级建造师《建筑工程管理与实务》综合练习A卷 附答案
doc 山东省重点小学三年级数学【下册】开学考试试卷 (附答案)
ppt 《抒情散文思路》PPT课件
doc 山东省重点小学三年级数学【下册】开学考试试卷 (含答案)
doc 山东省重点小学三年级数学【下册】开学考试试卷 含答案
ppt 《抓准四点六朝古都》PPT课件
doc 山东省重点小学三年级数学【下册】开学摸底考试试题 (含答案)
doc 实验小学二年级数学下学期开学考试试题赣南版A卷 附解析
doc 2020年六年级数学【上册】期末考试试题外研版 附解析
doc 云南省2020年实验小学一年级语文【下册】期中考试试卷 附答案
doc 云南省2020年实验小学一年级语文【下册】开学考试试题 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试题C卷 (含答案)
ppt 《抓住增员黄金周》PPT课件
doc 2020年一级建造师《建筑工程管理与实务》综合练习B卷 (含答案)
doc 云南省2020年实验小学一年级语文【下册】期中摸底考试试卷 含答案
ppt 离散数学群与半群
doc 2020年一级建造师《建筑工程管理与实务》综合练习B卷 (附答案)
doc 2020年一级建造师《建筑工程管理与实务》综合练习B卷 附答案
doc 云南省2020年实验小学一年级语文【下册】开学摸底考试试题 附答案
doc 云南省2020年实验小学一年级语文【上册】期末摸底考试试题 附解析
doc 2020年六年级数学【上册】期末考试试题外研版B卷 附解析
doc 广东省重点小学四年级数学下学期期末摸底考试试题A卷 (附解析)
doc 广东省重点小学四年级数学下学期期末摸底考试试题C卷 (附答案)
ppt 《抑郁症的动物模型》PPT课件
ppt 《抓住根本注意动向》PPT课件
ppt 《抑郁症的认知障碍》PPT课件
doc 2019-2020学年高二英语上学期阶段考试试题(二)
doc 云南省2020年实验小学一年级语文【下册】期中考试试卷 含答案
doc 2020年六年级数学【上册】期末考试试题外研版A卷 含答案
doc 实验小学二年级数学下学期开学考试试题赣南版(I卷) 附解析
ppt 《抒情技巧习题》PPT课件
doc 云南省2020年实验小学一年级语文【下册】期末摸底考试试卷 含答案
ppt 《抑郁症药物治疗》PPT课件
doc 2020年六年级数学【上册】期末考试试题北师大版C卷 附答案
doc 实验小学二年级数学下学期开学考试试题赣南版(II卷) 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试题A卷 (附答案)
doc 2020年六年级数学【上册】期末考试试题外研版A卷 附答案
doc 2019-2020年高三上学期期中质量评估语文试题
doc 2019-2020学年高二英语上学期阶段联考试题二
doc 云南省2020年实验小学一年级语文【下册】开学考试试卷 附答案
doc 实验小学二年级数学下学期开学考试试题赣南版 附答案
doc 2020年六年级数学【上册】期末考试试题北师大版(II卷) 附答案
doc 云南省2020年实验小学一年级语文【上册】期末考试试题 附答案
doc 山东省重点小学三年级数学【下册】开学考试试题 (附答案)
doc 山东省重点小学三年级数学【下册】开学摸底考试试卷 含答案
ppt 离散数学第六章集合代数
doc 2020年一级建造师《建筑工程管理与实务》综合练习C卷 附答案
doc 云南省2020年实验小学一年级语文【上册】期末考试试卷 附解析
doc 实验小学二年级数学下学期开学考试试题部编版B卷 附答案
doc 2020年六年级数学【上册】期末考试试题外研版B卷 含答案
ppt 《抑郁症的症状表现》PPT课件
doc 云南省2020年实验小学一年级语文【下册】期中考试试题 含答案
ppt 离散数学第六章代数系统
doc 山东省重点小学三年级数学【下册】开学考试试题 含答案
doc 2019-2020年高三上学期期中质量检测理科数学试题 Word版含答案
doc 实验小学二年级数学下学期开学考试试题部编版 附解析
doc 山东省重点小学三年级数学【下册】开学摸底考试试卷 (附解析)
doc 2020年一级建造师《建筑工程管理与实务》综合练习C卷 (附解析)
doc 2019-2020年高三上学期期中质量检测生物试题 Word版含答案
doc 2020年一级建造师《建筑工程管理与实务》综合练习B卷 含答案
ppt 《抒情散文阅读》PPT课件
doc 广东省重点小学四年级数学下学期期末摸底考试试题A卷 附答案
doc 2020年六年级数学【上册】期末考试试题北师大版(II卷) 含答案
doc 2019-2020学年高二英语上学期返校考试题
doc 2019-2020年高三上学期期中质量监测生物试题 含答案
doc 2019-2020年高三上学期期中质量监测物理试题 含答案
doc 实验小学二年级数学下学期开学考试试题赣南版A卷 含答案
doc 2019-2020年高三上学期期中质量检测理科综合试题 含答案
doc 2019-2020年高三上学期期中质量检测语文试题(含附加题) Word版含答案
doc 2020年六年级数学【上册】期末考试试题外研版 (含答案)
doc 2020年一级建造师《建筑工程管理与实务》综合检测(I卷) 附解析
ppt 《抓住典型案例》PPT课件
ppt 《把课文认真读几遍》PPT课件
doc 2019-2020年高三上学期期中质量检测语文试题(含附加题)含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试题B卷 附解析
doc 2020年六年级数学【上册】期末考试试题北师大版(I卷) 含答案
doc 2020年六年级数学【上册】期末考试试题外研版 (附解析)
doc 2020年一级建造师《建筑工程管理与实务》综合练习A卷 (附答案)
doc 2020年一级建造师《建筑工程管理与实务》综合练习A卷 附解析
ppt 离散数学第六章集合代数
doc 实验小学二年级数学下学期开学考试试题赣南版A卷 附答案
doc 2020年六年级数学【上册】期末考试试题北师大版C卷 附解析
doc 云南省2020年实验小学一年级语文【下册】开学摸底考试试题 附解析
ppt 《把路修到拉萨去》PPT课件
doc 山东省重点小学三年级数学【下册】开学摸底考试试题 (附答案)
doc 山东省重点小学三年级数学【下册】开学摸底考试试卷 附答案
doc 2020年一级建造师《建筑工程管理与实务》综合练习C卷 (含答案)
doc 山东省重点小学三年级数学【下册】开学考试试题 (附解析)
doc 2020年六年级数学【上册】期末考试试题北师大版(I卷) 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试题B卷 (含答案)
doc 2020年一级建造师《建筑工程管理与实务》综合练习D卷 (附答案)
doc 山东省重点小学三年级数学【下册】开学考试试卷 附答案
doc 实验小学二年级数学下学期开学考试试题赣南版(I卷) 附答案
doc 实验小学二年级数学下学期开学考试试题豫教版(I卷) 含答案
doc 2019-2020年高三上学期期中阶段性测评 生物
doc 广东省重点小学四年级数学下学期期末摸底考试试题A卷 含答案
doc 云南省2020年实验小学一年级语文【上册】期末考试试题 含答案
doc 2020年六年级数学【上册】期末考试试题外研版B卷 附答案
doc 云南省2020年实验小学一年级语文【上册】期末摸底考试试题 含答案
doc 山东省重点小学三年级数学【下册】开学考试试题 附解析
doc 实验小学二年级数学下学期开学考试试题赣南版C卷 附答案
doc 实验小学二年级数学下学期开学考试试题部编版C卷 附答案
doc 云南省2020年实验小学一年级语文【上册】期末考试试卷 附答案
doc 实验小学二年级数学下学期开学考试试题部编版A卷 附解析
doc 2020年一级建造师《建筑工程管理与实务》综合练习D卷 (含答案)
doc 2019-2020年高三上学期期中质量检测英语试题 Word版含答案
doc 2019-2020年高三上学期期中质量评估化学试题
doc 山东省重点小学三年级数学【下册】开学考试试题 (含答案)
doc 2020年六年级数学【上册】期末考试试题外研版 含答案
doc 2019-2020年高三上学期期中质量检测生物试题含答案
doc 2020年一级建造师《建筑工程管理与实务》综合练习B卷 (附解析)
ppt 离散数学群环域格
ppt 离散数学等价偏序函数
doc 2020年六年级数学【上册】期末考试试题北师大版C卷 含答案
doc 云南省2020年实验小学一年级语文【下册】期中考试试题 附答案
doc 云南省2020年实验小学一年级语文【下册】开学考试试卷 附解析
doc 山东省重点小学三年级数学【下册】期中摸底考试试卷 (含答案)
doc 实验小学二年级数学下学期开学考试试题部编版A卷 附答案
ppt 《把酒问月精美》PPT课件
doc 实验小学二年级数学下学期开学考试试题部编版 含答案
doc 实验小学二年级数学下学期开学考试试题赣南版C卷 含答案
doc 实验小学二年级数学下学期开学考试试题豫教版(I卷) 附解析
doc 云南省2020年实验小学一年级语文【下册】期中摸底考试试卷 附解析
doc 2019-2020年高三上学期期中质量检测物理试题
ppt 离散数学绪论、命题
doc 2020年一级建造师《建筑工程管理与实务》综合练习D卷 含答案
doc 2020年六年级数学【上册】期末考试试题北师大版(I卷) 附解析

离散数学第十章基本图类及算法习题答案

 版权申诉  ppt " "设一个树中度为k的结点数是nk(2k),求它的叶的数目。 解:设n个结点的树有t个叶, 由已知 n=t+∑ni 2(n-1)=t+ ∑ini 消去式中的n: 2= t+ ∑(2-i)ni 即: t= ∑(i-2)ni + 2" "i=2" "i=2" "" "" "i=2" "" "i=3" "" "" " 习题十一 1 " "设e是连通图G的一条边,证明: e是割边当且仅当e含于G的每个生成树中. 证明: ()如果割边e不在G的某个生成树中,则G- e仍有生成树,即仍连通,与割边的定义相矛盾. ()如果e是每个生成树的公共边,则去掉e后G- e不再连通,即e为G 的割边." " 习题十一 10 " "树T中最长道路的起点和终点必都是T的叶. 证明: 设u到v的道路是树中最长道路,如果u或v不是叶,由道路唯一性,必有u或v的邻接结点不在该道路上,因此这条道路可延长至w,与最长条件矛盾。" " 习题十一 2 " "" "" "" "" "" "" "" "用Kruskal算法求图的一个最小生成树。 解:边按序排列:ab,gc,eg,ed,af,fd,fe,dc,fb,bd,ag,bc 按算法构造生成树边集为:{ab,gc,eg,ed,af,fd}, W(T)=8." "" "" "" "" "" "" "" "" "" "" "" "" "a" "g" "f" "e" "d" "c" "b" "1" "3" "2" "1" "3" "2" "1" "1" "4" "4" "6" "5" " 习题十一 12 " "" "" "" "" "" "" "" "" "" "" "用Kruskal定理证明Peterson图不是平面图。 证明:下面是Peterson图的一个子图, 它与k3,3的细分图同构,所以Peterson图不是平面图。" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" " " "设G是阶数不小于11的图,证明:G或G中至少有一个是非平面图。 证明:假设G和G都是平面图,可得n(n-1)/2 6n-12, 所以 n2-13n+24 0 可得n10,与已知矛盾。所以原题得证。" "" "" " 习题十二 3 " "证明:少于30条边的简单平面图至少有一个顶点的度不大于4。 证明:假设 5,可得 5n 2m 由平面性,2m 6n-12 再将n 12 代入5n 2m ,得m  30,与已知矛盾。所以原题得证。" "" " n 12" " 习题十二 5 " "若一平面图与其对偶图同构,则称这个平面图为自对偶图。推导自对偶图必须满足的结点数n与边数m的关系,并找出一个自对偶图。 解:如果G是自对偶图,在欧拉公式中必有n=f, 于是m=2(n-1)." " 习题十二 9 " "设G=(V,E)是一个具有2k(k>0)个奇数度结点的连通图。证明:G中必存在k条边不相重的简单道路P1,P2,…,Pk, 使得E=E(P1) E(P2) … E(Pk). 证明:把2k个奇数度结点分成两两一组的k组,然后每组结点新加一条边,所得图为欧拉图,故存在欧拉回路。 再去掉欧拉回路中的k条新加入的边,得到k条互无重复边的道路P1,P2,…,Pk, 即为所求。" " 习题十三 2 " "v9" "v6" "v3" "v1" "" "求图中,中国邮递员问题的解。 解:图中有4个奇数度结点v1,v6,v9,v3, 求两两之间最短长度: Pv1v6=3 (v1v6), Pv1v9=7 (v1v2v3v4v9), Pv1v3=4 (v1v2v3), Pv6v9=7 (v6v7v8v9), Pv3v6=6 (v3v8v7v6), Pv3v9=3 (v3v4v9), Pv1v6和Pv3v9满足最小性要求, 复制v1v6和v3v4v9的边,图中欧拉回路即为所求解。" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "v2" "v4" "v5" "v7" "v8" "v10" "" "2" "2" "1" "1" "1" "1" "3" "3" "v11" "3" "4" "4" "1" "5" "5" "6" "" "" "" "2" " 习题十三 5 " "证明:连通图G是平面欧拉图当且仅当其对偶图是平面二部图。 证明: “”:当G是平面欧拉图时,G的点度是偶数,对应G*的面度应是偶数,说明G*的回路都是偶长回路,从而G*是二部图。 “”:当G*是平面二部图时,它的面度都是偶数,因而G的各点度均为偶数,故G是平面欧拉图。 " "n个人定期围圆桌而坐,商讨事务,他们希望每人每次两旁的人都和以前的不同,这样的安排最多有多少种? 解:将人看作图的结点,邻座关系作为图的边。每次安排方式对应一个Hamilton回路。因为每人每次两旁的人都和以前不同,所以每2种安排方式对应2个无公共边的Hamilton回路。 因每个人都可与其余人邻座,所以本问题转化为在Kn中找出所有无公共边的Hamilton回路的个数。 Kn共有n(n-1)/2条边,每条Hamilton回路的长度为n,因此Kn中最多有(n-1)/2条无公共边的Hamilton回路。因此,最多有(n-1)/2种安排。 例如n=7时,共有3种就座方式,分别是: 1 2 3 4 5 6 7 1 1 3 5 7 2 4 6 1 1 4 7 3 6 2 5 1 " "" " 用2种以上办法判别下图不是Hamilton图。 解: ①用必要条件,选7个结点,去掉后剩9支。 ②注意观察,发现是平面二部图,因为所有回路都是偶长,那就可对结点进行二部划分:一部是7个,另一部是9个结点。但二部图要成为Hamilton图必须2部结点数相同。 ③ 2(f4(1)-f4(2))+4(f6(1)-f6(2))=0 f4(1)+f4(2)=12 f6(1)+f6(2)=1 无合理解。" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" " 习题十三 15


























 版权投诉/申诉   非法内容举报    本页不提供全部页面预览,未展示部分请购买并下载后观看使用