离散数学习题课 此页可以删除.

Slides:



Advertisements
Similar presentations
喜迎 G20 中国 CONTENTS 目 录目 录 1 中国美食 2 中国守护神 美食美食,顾名思义就是美味的食 物,贵的有山珍海味,便宜的 有街边小吃。但是不是所有人 对美食的标准都是一样的,其 实美食是不分贵贱的,只要是 自己喜欢的,就可以称之为美 食。吃前有期待、吃后有回味 的东西。美食遭遇心情的时候,
Advertisements

庄子思想 天地与我并生 万物与我为一 形而上的本体观念 法则、规范、不可思议之事. 庄子作品 极富想象力和浪漫色彩,擅用寓(寄托)言,《史 记》载: “ 其著书十余万言,大抵率寓言也 ” 。 又称《南华经》、《南华真经》 内篇 7 ,外篇 15 ,杂篇 11 《庄子》内容 《逍遥游》《齐物论》《养生主》《人间世》
1 ——含山县新教师集中培训 2015年10月17日 教学常规和课堂教学技能 含山县环峰第二小学 吴保东.
学分制改革为大学英语教学带来的 挑战与机遇 —— 武汉科技大学交流报告. Contents 武汉科技大学外国语学院简介 一 四 我校学分制改革后大学英语教学改革探索 二 学分制改革为大学英语教学带来的挑战 三 学分制改革为大学英语教学带来的机遇.
第五章 企业所得税、个人所得税.
九十五年國文科命題知能 研習分享.
因为爱,我们让研修果实更香甜 ——阜阳市临泉县小语1班第三期简报 编辑 葛泽付.
第三章 民事诉讼法的基本原则 教学目的和要求: 明确我国民事诉讼法基本原则的意义,确立依据及其分类,掌握民事诉讼法的特有原则。 1
必修2 第一单元 古代中国经济的基本结构和特点
甘肃小吃 文产二班 陶方 羊肉泡 牛肉面 暖锅.
财经法规与会计职业道德 与教材配套的应试指导,基于教材进行归纳总结“考什么”“怎么考”“怎么练”.
考点二 政治文明 ——英法美代议制民主的确立.
第七章 企业盈利能力分析 本章重点:   总资产收益率、净资产收益率、资本保值增值率、销售净利率、基本每股收益、每股股利、市盈率、股利支付率的概念计算以及分析评价。 难点: 总资产收益率、净资产收益率、每股收益的计算与应用;对影响盈利能力的其他因素的理解。
第五单元 社会生活的变迁 第1课时 衡量变化的尺子 ——— 时间和纪年 新围初中 王济洪.
第四讲 生物技术的安全性和伦理问题.
第二单元 生产、劳动与经营 第六课 投资理财的选择 一.储蓄存款和商业银行.
文明史观 文明史观,通常被称为文明史研究范式,是研究历史的一种理论模式。人类社会发展史,从本质上说就是人类文明演进的历史。
第3课 收复新疆.
案例分析题 主讲蔡影.
第十章 会计档案 本章主要介绍了五方面的内容:(1)会计档案的概念和内容;(2)会计档案归档;(3)会计档案的保管期限;(4)会计档案的查阅、复制和交接;(5)会计档案的销毁 本章属于非重点章, 三年试卷中所占分值各为6分、7分、7分。
1.6 中国人口迁移.
高三政治二轮复习系列课件 专题十一  中华文化与民族精神.
第十一单元 第24讲   第十一单元 世界经济的全球化趋势.
解排列组合问题的常用策略.
第三单元 发展社会主义民主政治.
常用逻辑用语复习课 李娟.
3.3 资源的跨区域调配 ——以南水北调为例 铜山中学 李启强.
9.1 抽签的方法合理吗.
北京市高中生技术设计创意大赛 服装再造设计项目培训
第十二单元 第28讲 第28讲 古代中国的科技和文艺   知识诠释  思维发散.
第6讲 近代中国的新方向—— 五四运动至新中国成立.
上海交通大学 概率论第一、二章测验题 大学数学教研室 童品苗.
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
第三节 格林公式及其应用(2) 一、曲线积分与路径无关的定义 二、曲线积分与路径无关的条件 三、二元函数的全微分的求积 四、小结.
第十课 创新意识与社会进步 1.辩证的否定观:辩证否定、形而上学的否定观
课标版 政治 第一课 美好生活的向导.
七 年 级 数 学 第二学期 (苏 科 版) 复习 三角形.
初中数学八年级下册 (苏科版) 10.4 探索三角形 相似的条件(2).
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
动物激素的调节及其在农业生产中的应用(B级)
政治第二轮专题复习专题七 辩 证 法.
《美国的两党制》选考复习 温州第二高级中学 俞优红 2018年6月14日 1.
2012版中考二轮复习历史精品课件北师大版 (含2011中考真题) 专题五世界近代史
在数学的天地里,重要的不是我们知道什么,而是我们怎么知道什么。     
使用矩阵表示 最小生成树算法.
无向树和根树.
第 五 章 图 论 (第二部分) 1. 通路 2. 图的连通性.
第八章 运动和力 第1节 牛顿第一定律和惯性 (第2课时  惯性).
实数与向量的积.
线段的有关计算.
2.3等腰三角形的性质定理 1.
2.6 直角三角形(二).
⑴当∠MBN绕点B旋转到AE=CF时(如图1),比较AE+CF与EF的大小关系,并证明你的结论。
12.2全等三角形的判定(2) 大连市第三十九中学 赵海英.
结束 放映 1.1 数制及编码 数制及其转换 编码 返回 2019/5/1.
复习: 若A(x1,y1,z1) , B(x2,y2,z2), 则 AB = OB - OA=(x2-x1 , y2-y1 , z2-z1)
基础会计.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
树和图 tree and graph 蔡亚星.
空间平面与平面的 位置关系.
第七、八次实验要求.
樂理教學                 茄苳國小蔡逸凡老師.
高中数学必修 平面向量的基本定理.
直线的倾斜角与斜率.
第2节 大气的热力状况 基础知识回顾 重点难点诠释 经典例题赏析.
3.4 角的比较.
离散数学─归纳与递归 南京大学计算机科学与技术系
专题八 欧美代议制的确立与发展 (17—19世纪) 英    美 法 德 选修:日本 俄国.
最小生成树 最优二叉树.
Presentation transcript:

离散数学习题课 此页可以删除

目录 Contents 1 作业讲解 2 课堂练习

目录 Contents 1 作业讲解 2 课堂练习

习题一 2.简单图G中,如果m>1/2(n-1)(n-2),证明G不存在孤立节点。 知识点:图的边,孤立节点

习题一 拉塞姆定理:任意6个人必定3个是彼此认识或彼此不认识. 证明: 在平面上用6个点A、B、C、D、E、F分别代表参加集会的任意6个人.如果两人以前彼此认识,那么就在代表他们的两点间连成一条红线;否则连一条蓝线.考虑A点与其余各点间的5条连线AB,AC,…,AF,它们的颜色不超过2种.根据抽屉原理可知其中至少有3条连线同色,不妨设AB,AC,AD同为红色.如果BC,BD ,CD 3条连线中有一条(不妨设为BC)也为红色,那么三角形ABC即一个红色三角形,A、B、C代表的3个人以前彼此相识:如果BC、BD、CD 3条连线全为蓝色,那么三角形BCD即一个蓝色三角形,B、C、D代表的3个人以前彼此不相识.

习题一 用图论语言来说,本题等价于对K9(9个点的完全图)的边进行红蓝染色,那么必有一个红色K3或一个蓝色K4。下证之: (1)如果K9中有一个点v1引出至少4条红边,不妨设v1v2,v1v3,v1v4,v1v5为红边。这时 v2,v3,v4,v5四个点所成的K4中或者每条边都是蓝色(即存在蓝色K4),或者至少有一条边是红色(即存在红色K3)。 (2)如果K9中每个点引出的红边少于4条,那么每点至少引出5条蓝边。 由于蓝边总数的2倍>=5*9=45,从而蓝边总数的2倍>=46,从而至少有一点v1引出6条蓝边,设为v1v2,v1v3,v1v4,v1v5,v1v6,v1v7为蓝边,这时v2,v3...v7所成的K6中必有一个同色三角形,如果是红色,则存在红色K3,如果是蓝色,并上v1点后形成蓝色K4。

习题三 1.一棵树有n2个结点的度为2,n3个结点的度为3 ……,nk个结点的度为k, 问有几个度为1的结点。

习题三 2.证明树中最长道路的两个端点一定都是树叶。 证明:设L 是树T 的一条最长路,L 中的结点依次为 v1, v2 , …,vk。因为L 中各结 点都有边相连,所以它们的度数均大于或等于1。 若deg (v1)>1, 则除了边(v1, v2)外,还存在边(v1, v’) 。因为树中不存在回 路,故v’不属于集合{ v1, v2 , …, vk },于是,(v’,v1, v2 , …, vk)是T 的一条新的路, 其长度比L 更长。这与L 是T的最长路矛盾。 所以deg (v1)=1,类似可证deg (vk)=1。

习题三 14.给出字符串state act as a seat (a)最优二进制编码 (b)如果不带空格,求该字符串的最优二进制编码 (a) 各字符出现的次数为 s t a e c 空格: 3 4 5 1 1 4

习题三 14.给出字符串state act as a seat (a)最优二进制编码 (b)如果不带空格,求该字符串的最优二进制编码 (a) 各字符出现的次数为 s t a e c 空格: 3 4 5 1 1 4

习题三 16.求最短树 用Kruskal 算法。先将权排序,而后按权由小到大选边7 条(构成回路时所选边 不放入),可得一棵最小生成树(总权为22):

目录 Contents 1 作业讲解 2 课堂练习

题目答案

题目答案

题目答案

题目答案

谢 谢!