离散数学期中复习大纲

离散数学期中复习大纲

作者: _影沉_ | 来源:发表于2019-04-23 21:46 被阅读0次

离散数学期中复习大纲
关于最近
复习大纲
复习大纲
期中复习
期中复习
期中复习
0是自然数
下周计划
nodejs复习大纲

图论

边数 $e(G)$ 距离 $d(u,v)$ （最短）圈长 $g(G)$ 完全图 $K_n$ 完全二部图 $K_{m,n}$
连通分支数 $w(G)$ 边连通度（最小割边集基数） $\lambda (G)$ 点连通度 $K(G)$
顶点次数 $d_G(v)$ 最大次数 $\Delta (G)$ 最小次数 $\delta(G)$
面的次数 $deg(R)$

基本概念

图G 顶点V 边E
顶点的邻域、闭邻域
同构
Thm1. 减去任意一对顶点同构，那么同构
子图，支撑子图（生成子图），顶点集导出子图，边集导出子图
补图，自补图
完全图、二部图
途径迹（边不同）、路（点不同）、圈（点不同，首尾相连）
距离三公理：非负性、对称性、三角不等式
连通图、连通分支（极大连通子图）
割边/桥
Thm2. 连通分支数为k的p阶简单图最多边数为 $\begin{pmatrix} p-k+1\\2 \end{pmatrix}$
Cor. G为p阶简单图，则e(G)大于上值时，为连通图
Thm3. 无向图G中e为割边 $\iff$ e不在G的任何一个圈上

二部图

Thm4. 无向图G为二部图 $\iff$ G不含奇圈

顶点次数

Thm5. （Euler）无向图顶点次数之和为边数的二倍 $\Sigma_{v\in V(G)}=2e(G)$
Cor. 无向图有偶数个奇次点

正则图
Thm6. $d_1,d_2,...,d_n$ 为度序列 $\iff$ 它们之和为偶数
Thm7. 满足Thm6的度序列，前k个度之和小于等于 $K(k-1)+\Sigma_{k<i<=p}\min{\{k,d_i \}}\iff$ 对应的为简单图

树（无圈的连通图）

Thm8. 非平凡的简单图为树 $\iff$ 它的任意一对不同顶点之间恰有一条路相连
证： $(P_1\bigcup P_2)-e$ 中最短的uv路与e构成一个圈
Cor. T+uv有唯一的圈
Thm9. $e(T)=p-1$

树叶、悬挂点
Cor. 非平凡的树至少有两片树叶
证：顶点次数之和为2p-2大于等于2p-r
生成树（支撑树）
Thm10. 无向图有生成树 $\iff$ 连通
Cor. 连通图的边数大于等于p-1，等号成立 $\iff$ 为树
避图法、破图法

欧拉图与哈密顿图

闭欧拉迹、欧拉图（包含所有边）
Thm11. 非平凡图有欧拉迹 $\iff$ 每个顶点为偶次点
开欧拉迹、一笔画图
Thm12. 连通图含开欧拉迹 $\iff$ 恰有两个奇次点
哈密顿圈、哈密顿图、哈密顿路
Thm13. S为非空顶点集， $w(G-S)<=|S|$
证：只需证明哈密顿圈
Thm14.(Ore) 大于3阶简单图，任意一对uv，有 $d_G(u)+d_G(v)>=p$ 则必为哈密顿图
Cor. 若顶点度数均 $>=\frac{p}{2}$ 则为哈密顿图

平面图（任何两边不在顶点之外相交）

可平面图
Thm15. 一个图为可平面图 $\iff$ 把它画在球面上使任两弧（边）不在顶点之外的地方相交
Cor. 多面体对应的图为可平面图
内部面（有界）外部面（无界）面的次数（边数，两侧为同一面算两次）
Thm16. 面的次数之和为 $2e(G)$
Thm17.(Euler公式) 连通平面图有p顶点，q边，r面，则 $p-q+r=2$
证：找生成树，树只有外面
Cor.(Euler多面体公式) 多面体顶点为V，棱为E，面为F，则 $V-E+F=2$
Thm18. 每个面次数至少为3的p阶平面图， $q=e(G)<=\frac{n}{n-2}(p-2)$ ,等号成立当且仅当每个面次数相等。
Thm19.(Euler)正多面体只有正4、6、8、12、20面体
证：设每个面是正n边形，每个顶点恰好在k条棱上， $q=\frac{n}{n-2}(p-2), 2q=rn,2q=pk$
引入2度顶点、消去二度顶点、同胚
Thm20.（平面图判别定理）无向图为平面图 $\iff$ 不含同胚与 $K_5$ 或 $K_{3,3}$ 的子图

一阶逻辑

命题

命题联结词
（1 否定
（2 析取（或）
（3 合取（且）
（4 蕴含
（5 等价
合成公式
永真公式、可满足的
命题演算公式
（1 de Morgan律
（2 $\alpha \to \beta \equiv \neg \alpha \vee \beta$
（3 $\alpha \leftrightarrow \beta$ 有两种等价形式
5.析取范式与合取范式
（1 析取易见成假赋值，合取易见成真赋值
（2 第一步等价、蕴含，第二步否定词移动到最里，第三步分配律，析取->合取，合取->析取
极大项，极小项
主析取范式，主合取范式

一阶逻辑语言

skolern前束范式
（1 消等价蕴含
（2 否定词深入
（3 量词外提

相关文章

离散数学期中复习大纲
图论边数距离（最短）圈长完全图完全二部图连通分支数边连通度（最小割边集基数）点连通度顶点次数最大...
关于最近
上完课了，原本想着好好复习一下离散数学，毕竟这周五就期中考试了，但是最近发生的很多事，都让我无心学习，效率极低。所...
复习大纲
linux 20个命令 -- 课件\02_Linux\补充资料 --《必须掌握的20个linux命令.txt》 1...
复习大纲
复习大纲 2018.3.29创建，参考各位大佬的文章所拟的复习大纲，后面进一步完善(第一次写md，略丑) Andr...
期中复习
马上就要期中考试了，这两星期一直带着学生进行期中复习，在这两周里我的任务重心一直放在以下几点，尽自己的最大...
期中复习
酒后和乐小学陈鑫一、复习目标通过系统地复习，让学生能扎实地掌握本学期的所学的单词、句型和其他与课本所学的知识...
期中复习
期中语文考前5点复习策略马上该期中考试了，期中考前，语文这样复习能提10分，不信试试看。为什么...
0是自然数
我在复习离散数学的时候，发现笔记上对于集合N用红笔标记了“离散数学中认为0也是自然数”。瞟过一眼以后突然觉得奇怪，...
下周计划
1.课程设计提前四天完成 2.复习离散数学，线性代数完成
nodejs复习大纲
nodejs复习模块http 服务 let http = require('http'); http.cre...

网友评论

本文标题：离散数学期中复习大纲

本文链接：https://www.haomeiwen.com/subject/vafigqtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

热点阅读

关于我们|服务条款|联系我们|离散数学期中复习大纲|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！