离散数学-耿素云PPT(第5版)7.1-2

格式：ppt
大小：1.28 MB
文档页数：37

下载文档原格式

离散数学-耿素云PPT(第5版)7.1-2

32
用2叉有序树表示算式
每一个分支点放一个运算符. 二元运算符所在的分支点有2个儿子, 运算对象是以这2个儿子为根的根子树表示的子表达式, 并规定被减数和被除数放在左子树上; 一元运算符所在的分支点只有一个儿子, 运算对象是以这个儿子为根的根子树表示的子表达式.数字和变量放在树叶上.
33
14
基本割集的性质
连通图中的任一割集都可以表成对应它所含树枝的基本割集的对称差. 例如 {g,d}=Sd {a,b,e}=SaSb {a,e,c}=SaSc {b,e,f,d}=SbSd
15
无向图与最小生成树
对无向图或有向图的每一条边e附加一个实数w(e), 称作边e 的权. 图连同附加在边上的权称作带权图, 记作G=<V,E,W>. 设T是G的生成树, T所有边的权的和称作T的权, 记作W(T). 最小生成树: 带权图权最小的生成树避圈法 (Kruskal) ——求最小生成树的算法设G是n阶无向连通带权图G. (1) 按权从小到大排列边(环除外), 设W(e1)≤W(e2)≤…≤W(em). (2) 令T, i1, k0. (3) 若ei与T中的边不构成回路，则令TT{ei}, kk+1. (4) 若k<n-1, 则令ii+1, 转(3).
12
回路合并
合并回路C1和C2(C1C2): C1C2是C1和C2上的边的对称差构成的(一条或几条)回路.

13
基本回路的性质
连通图中的任一条回路都可以表成对应它所含弦的基本回路的合并. 例如, abcf=Cf aef=CeCf aedg=CeCg bcdgfe=CeCfCg
实例
例1 表示((b+(c+d))a)((ef)(g+h)(ij))的2叉有序树

离散数学ppt课件

02
集合论基础
集合的基本概念
总结词
集合是离散数学中的基本概念，是研究离散对象的重要工具。
详细描述
集合是由一组确定的、互不相同的、可区分的对象组成的整体。这些对象称为集合的元素。例如，自然数集、平面上的点集等。
集合的运算和性质
总结词
集合的运算和性质是离散数学中的重要内容，包括集合的交、并、差、补等基本运算，以及集合的确定性、互异性、无序性等性质。
生，1表示事件一定会发生。
离散概率论的运算和性质
概率的加法性质
如果两个事件A和B是互斥的，那么P(A或B)等于P(A)加上 P(B)。
概率的乘法性质
如果事件A和B是独立的，那么P(A和B)等于P(A)乘以P(B) 。
全概率公式
对于任意的事件A，存在一个完备事件组{E1, E2, ..., En}，使得P(Ai)>0 (i=1,2,...,n)，且E1∪E2∪...∪En=S，那么 P(A)=∑[i=1 to n] P(Ai)P(A|Ei)。
工程学科
离散数学在工程学科中也有着重要的应用，如计算机通信网络、控制系统、电子工程等领域。
离散数学的重要性
基础性
离散数学是数学的一个重要分支，是学习其他数学课程的基础。
应用性
离散数学在各个领域都有着广泛的应用，掌握离散数学的知识和方法对于解决实际问题具有重要的意义。
培养逻辑思维
学习离散数学可以培养人的逻辑思维能力和问题解决能力，对于个人的思维发展和职业发展都有很大的帮助。
详细描述
邻接矩阵是一种常用的表示图的方法，它是一个二维矩阵，其中行和列对应于图中的节点，如果两个节点之间存在一条边，则矩阵中相应的元素为1，否则为0。邻接表是一种更有效的表示图的方法，它使用链表来存储与每个节点相邻的节点。

离散数学第5讲PPT课件

() A. GH B. HG C. H => G D. G => H 4、设Ａ，Ｂ为任意命题公式，Ｃ为重言式，若Ａ∧ＣＢ∧Ｃ，那么ＡＢ是_________式（重言式、矛盾式或可满足式）。 5、命题公式（Ｐ→Ｑ）∨Ｐ的主合取范式为______，主析取范式为 _______。 6、化简下式：
第1页/共31页
第二章命题逻辑等值演算
等值演算法求解主析取范式的方法和步骤：
（1）化为析取范式A；
∨ ‫ר‬P （2）对A中的简单合取项补入没有出现的命题变元，即合取上（P
）
式，然后应用分配律展开；
（3）将析取式A中重复出现的合取项和相同的变元合并；
（4）除去析取范式中所有永假的合取项；
第2页/共31页
解：因为主析取范式是由所有的取值为1的极小项析取构成，而成真赋值所对应的即为极小项的编码，所以主析取范式为：
m0∨m3∨ m6
同理，主合取范式为：M1 ∧ M2 ∧ M4 ∧ M5 ∧ M7
第12页/共31页
第二章命题逻辑等值演算
2、判断公式的类型：设公式A中含有n个命题变项，则：
（1）A为重言式 A的主析取范式含全部2n个极小项。（2）A为矛盾式 A的主析取范式不含任何极小项，记A的主析取范式为 0。（3）A为可满足式 A的主析取范式至少含一个极小项。
第二章命题逻辑等值演算
以上六种情况对应公式分别为：
①(‫ר‬p∧‫ר‬q) ∧((‫ר‬p∧‫ר‬r)∨(p∧r)) ∧(‫ר‬p∧r) …①
② (‫ר‬p∧‫ר‬q) ∧(p∧‫ר‬r)∧((p∧r)∨(‫ר‬p∧‫ ר‬r)) …②
③
((‫ר‬p∧q)∨(p∧‫ר‬q))∧(‫ר‬p∧r)∧(‫ר‬p∧r)‫ר‬p∧q

离散数学配套课件PPT(第5版)第一部分数理逻辑联结词全功能集

3
复合联结词
与非式: pq(pq) 或非式: pq(pq)
和与, ∧,∨有下述关系: p(p∧p)pp p∧q( p∧q)(pq)(pq)(pq) p∨q(p∧q)(p)(q)(pp)(qq)
4
复合联结词(续)
ppp p∧q(pp)(qq) p∨q(pq)(pq)
13
例ቤተ መጻሕፍቲ ባይዱ续)
解编号
极小项
角码标记
1 x1∧x2∧x3∧x4 2 x1∧x2∧x3∧x4 3 x1∧x2∧x3∧x4
1110 * 1011 * 0111 *
4 x1∧x2∧x3∧x4 1010 * 5 x1∧x2∧x3∧x4 0101 * 6 x1∧x2∧x3∧x4 0011 *
1.5 联结词全功能集
联结词全功能集与非联结词,或非联结词
1
联结词的全功能集
定义设S是一个联结词集合，如果任何n(n1) 元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词全功能集.
说明：若S是联结词全功能集，则任何命题公式都可用S中的联结词表示.
设S1, S2是两个联结词集合，且S1 S2. 若S1是全
x y
x∧y x y
x∨y x
x
与门
或门
非门
8
组合电路的例子
(x∨y)∧x的组合电路
x y
x y
第一种画法
x 第二种画法
9
例
例楼梯的灯由上下2个开关控制, 要求按动任何一个开关都能打开或关闭灯. 试设计一个这样的线路. 解 x,y:开关的状态, F:灯的状态, 打开为1, 关闭为0. 不妨设当2个开关都为0时灯是打开的.
(5,7) x1∧x3∧x4 001 *

离散数学的ppt课件

科学中的许多问题。
03
例如，利用图论中的最短路径算法和最小生成树算法
等，可以优化网络通信和数据存储等问题。
运筹学中的应用
01
运筹学是一门应用数学学科，主要研究如何在有限资源下做出最优决策，离散数学在运筹学中有着广泛的应用。
02
利用离散数学中的线性规划、整数规划和非线性规划等理论，可以解决运筹学中的许多问题。
并集是将两个集合中的所有元素合并在一起，形成一个新的集合。
详细描述
例如，{1, 2, 3}和{2, 3, 4}的并集是 {1, 2, 3, 4}。
总结词
补集是取一个集合中除了某个子集以外的所有元素组成的集合。
详细描述
例如，对于集合{1, 2, 3}，{1, 2}的补集是{3}。
集合的基数
总结词
）的数学分支。
离散数学的学科特点
03
离散数学主要研究对象的结构、性质和关系，强调推
理和证明的方法。
离散数学的应用领域
计算机科学
01
离散数学是计重要的工具和方法。
通信工程
02
离散数学在通信工程中广泛应用于编码理论、密码学、信道容
量估计等领域。
集合的基数是指集合中元素的数量。
详细描述
例如，集合{1, 2, 3}的基数是3，即它包含三个元素。
03 图论
图的基本概念
顶点
图中的点称为顶点或节点。
边
连接两个顶点的线段称为边。
无向图
边没有方向，即连接两个顶点的线段可以是双向的。
有向图
边有方向，即连接两个顶点的线段只能是从一个顶点指向另一个顶点。
研究模态算子（如necessity、possibility）的语义和语法。

离散数学(修订版)-耿素云

例如 A = { a, b, c, …, z } Z = { 0, ±1, ±2, … }
谓词表示法: 用谓词来概括集合中元素的属性. 例如:B = { x | x R 且 x2 - 1 = 0 } 集合B表示方程x2 - 1 = 0的实数解集.
图示法:用一个圆来表示, 圆中的点表示集合中的元素. 许多集合可用两种方法来表示, 如: B = { -1, 1 }. 有些集合不能用列元素法表示, 如: 实数集合, 不能列举出
6.2 集合的运算
中山大学计算机科学系
18
集合的基本运算有并(Union), 交(Intersection)和相对
补(Relative Complement).
定义6.7 设A和B为集合, A与B的并集A∪B, 交集A∩B, B对A
的相对补集A-B分别定义如下:
A∪B = { x | x A∨x B }
常用的集合名称:
N: 自然数集合(本课程中认为0也是自然数)
Z: 整数集合
Q: 有理数集合
R: 实数集合
C: 复数集合
6.1 集合的基本概念
中山大学计算机科学系
10
集合有三种表示方法:列元素法、谓词表示法和图示法.
列元素法:列出集合中的所有元素, 各元素之间用逗号隔开, 并把它们用花括号括起来.
《离散数学》(修订版) 耿素云、屈婉玲, 高等教育出版社, 2004年
教学参考书
《离散数学》
王兵山、王长英、周贤林、何自强编, 国防科技大学出版社, 1985年
《离散数学》
檀凤琴、何自强编著, 科学出版社, 1999年
《离散数学》
孙吉贵、杨凤杰、欧阳丹彤和李占山, 高等教育出版社, 2002年
《离散数学》

离散数学第7章PPT课件

3 v1e1v2e5v5e6v4e4v2e5v5e7v6
…………
初级通路简单通路复杂通路
第38页/共94页
例1、(2)
图(2)中过v2的回路 (从 v2 到 v2 )有：
1 v2e4v4e3v3e2v2
长度3
2 v2e5v5e6v4e3v3e2v2
长度4
3 v2e4v4e3v3e2v2e5v5e6v4e3v3e2v2 长度7
第34页/共94页
一、通路，回路。 2、简单通路，简单回路。简单通路 (迹) 简单回路 (闭迹) 复杂通路 (回路)
第35页/共94页
一、通路，回路。 3、初级通路，初级回路。初级通路 (路径) 初级回路 (圈)
初级通路 (回路) 简单通路 (回路)，
但反之不真。
4、通路，回路的长度—— 中边的数目。
补图的概念， 5、图的同构的定义。
第4页/共94页
一、图的概念。 1、定义。
无序积 A & B (a,b) a A b B
无向图 G V , E
E V &V ， E 中元素为无向边，简称边。
有向图 D V, E
E V V ， E 中元素为有向边，简称边。
第5页/共94页
一、图的概念。 1、定义。
2、握手定理。
定理1：设图 G V , E 为无向图或有向图，
V v1,v1,
则
,vn，E m ( m为边数)，
n
d (vi ) 2m
i 1
第20页/共94页
n
2、握手定理 d (vi ) 2m i 1
推论：任何图中，度为奇数的顶点个数为偶数。
定理2：设D V, E 为有向图，
第36页/共94页

离散数学课件第一章

图的连通性
04
CHAPTER
逻辑基础
命题逻辑中的基本概念包括命题、真值和逻辑运算，通过这些基本概念可以表达和推理复杂的命题关系。
命题逻辑在计算机科学、人工智能、自动化等领域有广泛应用，是形式化方法的重要基础。
命题逻辑是研究命题之间关系的逻辑分支，主要涉及命题的否定、合取、析取、蕴含等基本运算。
命题逻辑
详细描述
集合的运算包括并集、交集、差集等。并集是指两个或多个集合合并为一个新的集合，包含所有元素；交集是指两个或多个集合中共有的元素组成的集合；差集是指从一个集合中去掉另一个集合中的元素后剩余的元素组成的集合。这些运算在离散数学中有着广泛的应用。
总结词
集合的运算
集合的基数是指集合中元素的个数，通常用大写字母表示。
鸽巢原理
THANKS
感谢您的观看。
集合论
图论是研究图（由节点和边构成的结构）的数学分支，它广泛应用于计算机科学和工程学科。
图论
逻辑是离散数学的另一个重要分支，它研究推理的形式和规则，是计算机科学和人工智能的基础。
逻辑
组合数学是研究计数、排列和组合问题的数学分支，它在计算机科学和统计学中有重要的应用。
组合数学
离散数学的研究内容
02
CHAPTER
离散数学课件第一章
目录
绪论集合论基础图论基础逻辑基础组合数学基础
01
CHAPTER
绪论
离散数学是研究离散对象（如集合、图、树等）的数学分支，它不涉及连续的量或函数。
离散数学的定义
离散数学的起源
离散数学的特点
离散数学的起源可以追溯到古代数学，如欧几里得几何和数论。
离散数学强调结构、关系和组合，而不是连续性和微积分。

离散数学讲义ppt课件

课程概况
教材：
《离散数学（第三版）》，耿素云等编著清华大学出版社，2004年3月
参考书：
（1）《离散数学(第二版)》及其配套参考书《离散数学题解》作者：屈婉玲，耿素云，张立昂清华大学出版社
（2）《离散数学》焦占亚主编电子工业出版社 2005年1月
2
课程概况
选修课/必修课：选修周学时：3（学时）上课周：1－16周总学时：48（学时）
3
课程内容及学时安排
第一篇数理逻辑（14学时）
第一章命题逻辑（8）第二章谓词逻辑（6）
第二篇集合论（12学时）
第三章集合（4）第四章二元关系与函数（8）
第四篇图论（14学时）
第七章图论（8）第八章一些特殊图（4）第九章树（2）
4
课程考核
第四篇代数系统（8学时）
第5、6章图论（8）
所以，伊勒克持拉既知道并且又不知道这个人是她的哥哥。
20
NO.3 M：著名的理发师悖论是伯特纳德·罗素提出的。一个理发师的招牌上写着：告示：城里所有不自己刮脸的男人都由我给他们刮脸，我也只给这些人刮脸。 M：谁给这位理发师刮脸呢？ M：如果他自己刮脸，那他就属于自己刮脸的那类人。但是，他的招牌说明他不给这类人刮脸，因此他不能自己来刮。 M：如果另外一个人来给他刮脸，那他就是不自己刮脸的人。但是，他的招牌说他要给所有这类人刮脸。因此其他任何人也不能给他刮脸。看来，没有任何人能给这位理发师刮脸了！
P
Q
PQ
P
0
0
0
1
0
1
0
1
1
0
0
0
1
1
1

离散数学第五版第四章(耿素云屈婉玲张立昂编著) ppt课件

证明：设A=、B={1}、C={2}、D={3}
(AB)×(CD)={<1,2>、<1,3>}
(A×C)(B×D)={<2,1>、<2,3>}
所以：等式不成立（3）(A-B)×(C-D)=(A×C)-(B×D)
证明：设A={1}、B={1}、C={2}、D={3}
(A-B)×(C-D)=
(xAyB) (xAyC)
<x,y>A×B <x,y>A×C
<x,y>(A×B)(A×C) PPT课件
9
4.1迪卡尔乘积与二元关系
5) 迪卡尔乘积运算对并和交运算满足分配律，即： (4)（BC）×A= (B×A)(C×A）
证明：对于任意的<x,y>
<x,y>（BC）×A
PPT课件
24
4.1迪卡尔乘积与二元关系
例5：设A={a,b}，R是P(A)上的包含关系， R={<x,y>|x,yP(A)xy}
解：P(A)={,{a},{b},{a,b}} R={<, >,<,{a}>,<,{b}>,<,{a,b}>, <{a},{a}>,<{a},{a,b}>,<{b},{b}>, <{b},{a,b}>,<{a,b},{a,b}>}
PPT课件
16
4.1迪卡尔乘积与二元关系
例4：设A,B,C,D为任意集合，判断真假。（1）A×B=A×CB=C 证明：若A=，B={1}，C={2} 则A×B=A×C=，而BC。所以：命题真假不定
PPT课件
17

离散数学耿素云PPT第版

3
通路与回路(续)
在两种意义下计算圈的个数 ① 定义意义下在无向图中, 一个长度为l(l3)的圈看作2l个不同的圈. 如v0v1v2v0 , v1v2v0v1 , v2v0v1v2, v0v2v1v0 , v1v0v2v1 , v2v1v0v2看作6个不同的圈. 在有向图中, 一个长度为l(l3)的圈看作l个不同的圈. ② 同构意义下所有长度相同的圈都是同构的, 因而是1个圈.
(2) 若通路(回路)中所有顶点(对于回路, 除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径, 初级回路又称作圈.
(3) 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路).
1
通路与回路实例
2
通路与回路(续)
说明: 表示方法
① 用顶点和边的交替序列(定义), 如=v0e1v1e2…elvl ② 用边的序列, 如=e1e2…el ③ 简单图中, 用顶点的序列, 如=v0v1…vl ④ 非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v5 环是长度为1的圈, 两条平行边构成长度为2的圈. 在无向简单图中, 所有圈的长度3; 在有向简单图中, 所有圈的长度2.
4
通路与回路(续)
定理在n阶图G中，若从顶点u到v（uv）存在通路，则从u到v存在长度小于等于n1的通路. 推论在n阶图G中，若从顶点u到v（uv）存在通路，则从u到v存在长度小于等于n1的初级通路.
定理在一个n阶图G中，若存在v到自身的回路，则一定存在v到自身长度小于等于n的回路. 推论在一个n阶图G中，若存在v到自身的简单回路，则存在v到自身长度小于等于n的初级回路.
6
点割集
记 Gv: 从G中删除v及关联的边 GV : 从G中删除V 中所有的顶点及关联的边 Ge : 从G中删除e GE: 从G中删除E中所有边

上课用课件离散—耿素云

1.2 命题公式及其赋值 p q r 例（ 1 ） (2)r q p q p
定义5.公式A， 1)若A在所有赋值下的取值均为真，则称A为永真式； 2）若A在所有赋值下的取值均为假，则称A为永假式； 3）若至少有一组赋值使A的值为真，则称A为可满足式。
2.1 命题公式的等值式
例：（p q)与p q p (q r ),( p q) r,( p q) r
基本等值式（A，B，C为任意命题公式）
交换律：A B A B, A B B A 结合律：A B C A B C , A B C A B C 分配律：A B C A B A C A B C A B A C
是自然语言中的“如果，则”，“若，则” 的逻辑抽象。
有位父亲对儿子说：“如果我去书店，就一定给你买电脑报“。问：在什么情况下，
p F F T T
q F T F T
p q T T F T

父亲算失信呢？
1.1 命题和命题联结词
注意：①“只要p，就q„，’因为p，所以q”，“p仅当q”， ‘只有q，才p“，”除非q才p“，”除非q，否则非p“都可抽象为p→q。 ②p，q可以没有任何内在联系。例：1.如果3＋3＝6，那么雪是白的。 2.除非我能工作完成了，我才去看电影。 3.只要天下雨，我就回家。 4.我回家仅当天下雨。 p→q的逻辑关系为q是p的必要条件或p是q的充分条件。
1.2 命题公式及其赋值
定义4.将公式A在其全部赋值下的真值情况列成表，称为A的真值表。
真值表的构造步骤：（ 1）若公式F 共有（ n n 1)个变元，则真值表第一行的n个变元，公式写在第n 1列。（2）写出n个变元的所有可能取值（2n 种）,按从低到高的顺序写出公式的各层次。（3）在不同赋值下求出各层次的真值及F的真值。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

14
基本割集的性质
连通图中的任一割集都可以表成对应它所含树枝的基本割集的对称差. 例如 {g,d}=Sd {a,b,e}=SaSb {a,e,c}=SaSc {b,e,f,d}=SbSd
15
无向图与最小生成树
对无向图或有向图的每一条边e附加一个实数w(e), 称作边e 的权. 图连同附加在边上的权称作带权图, 记作G=<V,E,W>. 设T是G的生成树, T所有边的权的和称作T的权, 记作W(T). 最小生成树: 带权图权最小的生成树避圈法 (Kruskal) ——求最小生成树的算法设G是n阶无向连通带权图G. (1) 按权从小到大排列边(环除外), 设W(e1)≤W(e2)≤…≤W(em). (2) 令T, i1, k0. (3) 若ei与T中的边不构成回路，则令TT{ei}, kk+1. (4) 若k<n-1, 则令ii+1, 转(3).
32
用2叉有序树表示算式
每一个分支点放一个运算符. 二元运算符所在的分支点有2个儿子, 运算对象是以这2个儿子为根的根子树表示的子表达式, 并规定被减数和被除数放在左子树上; 一元运算符所在的分支点只有一个儿子, 运算对象是以这个儿子为根的根子树表示的子表达式.数字和变量放在树叶上.
33
22
最优2叉树
定义设2叉树T有t片树叶v1, v2, …, vt, 树叶的权分别为w1, w2, …, wt, 称 W ( t ) wi l ( vi ) 为T的权, 其中 l(vi)是vi的层数. 在所有权为w1, w2, …, wt 的t片树叶的2叉树中, 权最小的2叉树称为最优 2叉树. 例如
i 1 t
W(T1)=47
W(T2)=54
W(T3)=42
23
求最优2叉树的算法
Huffman算法: 给定实数w1, w2, …, wt,
① 作t片树叶, 分别以w1, w2, …, wt为权.
② 在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点, 添加一个新分支点, 以这2个顶点为儿子, 其权等于这2个儿子的权之和. ③ 重复②, 直到只有1个入度为0 的顶点为止.
实例
例1 表示((b+(c+d))a)((ef)(g+h)(ij))的2叉有序树
中序行遍: ((b+(c+d))a)((ef)(g+h)(ij)) 前序行遍: ((b(cd))a)((ef)((gh)(ij))) 后序行遍: ((b(cd))a)((ef)((gh)(ij)))
第7章树.2 根树及其应用
1
7.1 无向树及生成树
无向树与森林生成树与余树基本回路与基本回路系统基本割集与基本割集系统最小生成树与避圈法
2
无向树
无向树: 无回路的连通无向图平凡树: 平凡图森林: 每个连通分支都是树的非连通的无向图树叶: 树中度数为1的顶点分支点: 树中度数2的顶点右图为一棵12阶树. 注:本章中所讨论的回路均指简单回路或初级回路
注:中序行遍的结果是原式
34
波兰符号法
波兰符号法(前缀符号法): 按前序行遍法访问表示算式的2叉有序树, 并舍去所有括号. 例1(续) b+cdaef+ghij
8
生成树
设G为无向连通图 G的生成树: G的生成子图并且是树生成树T的树枝: G在T中的边生成树T的弦: G不在T中的边生成树T的余树 T : 所有弦的集合的导出子图注意：T 不一定连通, 也不一定不含回路. 黑边构成生成树红边构成余树
9
生成树的存在性
定理任何无向连通图都有生成树. 证用破圈法. 若图中无圈, 则图本身就是自己的生成树. 否则删去圈上的任一条边, 这不破坏连通性, 重复进行直到无圈为止,剩下的图是一棵生成树. 推论设n阶无向连通图有m条边, 则mn1.
12
回路合并
合并回路C1和C2(C1C2): C1C2是C1和C2上的边的对称差构成的(一条或几条)回路.

13
基本回路的性质
连通图中的任一条回路都可以表成对应它所含弦的基本回路的合并. 例如, abcf=Cf aef=CeCf aedg=CeCg bcdgfe=CeCfCg
例如
28
l p
i 1 i
t
i
最佳前缀码
设要传输的电文中含有t个字符, 字符ai出现的频率为pi, 它的编码的长度为li, 那么100个字符的电文的
编码的期望长度是100 l i pi . 称编码期望长度最小
i 1
t
的2元前缀码为最佳2元前缀码.
在用2叉树产生2元前缀码时, 每个二进制串的长度等于它所在树叶的深度, 因而权为100p1, 100p2, , 100pt的最优2叉树产生的2元前缀码是最佳2元前缀码. 于是, 给定字符出现的频率, 可以用Huffman算法产生最佳2元前缀码.
10
基本回路与基本回路系统
定义设T是连通图G的一棵生成树, 对每一条弦e, 存在惟一的由弦e和T的树枝构成的初级回路Ce, 称 Ce为对应于弦e的基本回路. 称所有基本回路的集合为对应生成树T的基本回路系统.
求基本回路的算法: 设弦e=(u,v), 先求T中u到v的路径uv, 再加上弦e. 例如 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基={Ce, Cf, Cg}.
5
无向树的性质(续)
定理设T 是 n 阶非平凡的无向树，则T中至少有两片树叶. 证设T有x片树叶, 由握手定理及前面的定理， 2(n-1)x+2(n-x) 解得 x2.
6
例题
例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶点全是树叶. 试求树叶数, 并画出满足要求的非同构的无向树. 解用树的性质m=n1和握手定理. 设有x片树叶，于是 n=1+2+x=3+x, 2m=2(2+x)=13+22+x 解得x=3，故T有3片树叶. T的度数列为1, 1, 1, 2, 2, 3 有2棵非同构的无向树.
16
实例
例求图的一棵最小生成树
w(T)=38
17
7.2 根树及其应用有向树与根树家族树与根子树有序树根树与有序树的分类
r叉(有序)树, r叉正则(有序)树, r叉完全正则(有序) 树最优2叉树与Huffman算法前缀码与最佳前缀码中序行遍法、前序行遍法、后序行遍法波兰符号法与逆波兰符号法
(3) 若ab且a可达b, 则称a是b的祖先, b是a的后代. 设v为根树的一个顶点且不是树根, 称v及其所有后代的导出子图为以v为根的根子树.
21
根树的分类
有序树: 将根树同层上的顶点规定次序 r叉树:根树的每个分支点至多有r个儿子 r叉正则树: 根树的每个分支点恰有r个儿子 r叉完全正则树: 树叶层数相同的r元正则树 r叉有序树: 有序的r叉树 r叉正则有序树: 有序的r叉正则树 r叉完全正则有序树: 有序的r叉完全正则树
如 {0,10,110, 1111}, {10,01,001,110}是2元前缀码 {0,10,010, 1010} 不是前缀码
27
前缀码(续)
一棵2叉树产生一个二元前缀码: 对每个分支点, 若关联2条边, 则给左边标0, 右边标1; 若只关联1条边, 则可以给它标0(看作左边), 也可以标1(看作右边). 将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处, 所得的字符串构成一个前缀码.
29
实例
例在通信中，设八进制数字出现的频率如下： 0：25% 4：10% 1：20% 5：10% 2：15% 6：5% 3：10% 7：5%
采用2元前缀码, 求传输数字最少的2元前缀码 , 并求传输 10n(n2)个按上述比例出现的八进制数字需要多少个二进制
数字？若用等长的 (长为3) 的码字传输需要多少个二进制数
31
行遍2叉有序树
行遍(周游)根树T : 对T 的每个顶点访问且仅访问一次. 行遍2叉有序树的方式： ① 中序行遍法: 左子树、根、右子树 ② 前序行遍法: 根、左子树、右子树 ③ 后序行遍法: 左子树、右子树、根当不是正则树时, 左子树或右子树可缺省
例如, 中序行遍: b a (f d g) c e 前序行遍: a b (c (d f g) e) 后序行遍: b ((f g d) e c) a
字? 解用Huffman算法求以频率(乘以100)为权的最优2叉树. 这
里 w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25.
30
例(续) 编码: 0---01 1---11 2---001 3---100 4---101 5---0001 6---00000 7---00001 传100个按比例出现的八进制数字所需二进制数字的个数为 W(T)=285. 传10n(n2)个所用二进制数字的个数为2.8510n, 而用等长码(长为3)需要用 310n个数字.
18
有向树与根树
有向树: 基图为无向树的有向图根树: 有一个顶点入度为0, 其余的入度均为1的非平凡的有向树树根: 有向树中入度为0的顶点树叶: 有向树中入度为1, 出度为0的顶点内点: 有向树中入度为1, 出度大于0的顶点分支点: 树根与内点的总称顶点v的层数: 从树根到v的通路长度树高: 有向树中顶点的最大层数
3
树的应用
英国数学家凯莱(Arthur Cayley)于19世纪中叶研究饱和碳氢化合物CnH2n+2的同分异构体时提出树的概念. 当n=1,2,3时, 都只有一棵非同构的树; 当n=4时, 有2棵不同构的树.
甲烷

离散数学-耿素云PPT(第5版)7.1-2

合集下载