当前位置：文档之家 › 离散数学第7章

离散数学第7章

  • 格式：ppt
  • 大小：1.25 MB
  • 文档页数：94

下载文档原格式

  / 94

合集下载

离散数学课件

离散数学课件

1 1 1 c a c b b d a c c b
0 ¬ 1
1 0
《离散数学》
page: 4
7.1 运算 7.1.2 运算 3)几个术语 ②运算封闭性
y z
y
z=x*y
x
x
2013年10月25日星期五
作为运算（函数）z自然应该在A中，但当 x,y取自A的子集B时，Z是否也在B中？
《离散数学》
page: 5
o a b zl c zl d zl o a b c d zr zr zr zr zr
zl zl
如，R上的普通除法中的0，普通乘法中的0，集合交， 并运算中的空集与全集 page: 19
2013年10月25日星期五
《离散数学》
7.1 运算 7.1.3 运算的特殊元素，逆元，消去律 ③零元 设o为S上的二元运算，若存在元素，∀x↔S，有 zlox=zl (xozr=zr) ， 则称 zl(zr)为左（右）零元。 若运算o既有左零元zl，又有右零元zr，则其左右零元 必相等且惟一，此时称为运算o的零元z。
2013年10月25日星期五
《离散数学》
page: 10
7.1 运算 7.1.2 运算的性质 ③分配律 设о和*为S上的二元运算，若有∀x,y,z↔S，都有: x*(yоz)=(x*y)о(x*z) (左分配) (yоz)*x=(y*x)о(z*x) (右分配) 则称运算*对о是可分配的(*对о满足分配律) 。 如，R上普通乘对加,减法满足分配律，但加,减法对乘 除法不满足分配律。
2013年10月25日星期五
《离散数学》
page: 7
7.1 运算 7.1.2 运算的性质 ①交换律 设о为S上的二元运算，若有∀x,y↔S，都有 xoy=yox， 则称运算о是可交换的（运算满足交换律）。 如，R上普通的加，乘法满足交换律，而减，除法不 满足交换律。

离散数学7-树

离散数学7-树

(b)
(a)
V5
2
1
V7
8
9
V2
V4
2
3
V8
5
V1
V1
V4
V5
1
3
V7
V6
8
V4
2
V8
5
6
V1
1
V5
6
V7
V6
8
3
V8
5
6
V7
9
V3
(e)
V3
(f)
(g)
22
V2
V3
(h)
五.应用举例——求最小生成树
例3 用管梅谷算法求下图的最小生成树。
23
五.应用举例——求最小生成树
例3 用管梅谷算法求下图的最小生成树。
成圈。
首先证明T无简单回路。对n作归纳证明。
(i) n=1时,m=n-1=0,显然无简单回路；
(ii)假设顶点数为n-1时无简单回路，现考察顶点数是n的情况：此时至少有一
个顶点v其次数d(v)=1。因为若n个顶点的次数都大于等于2，则不少于n条边，但这与
m=n-1矛盾。
删去v及其关联边得到新图T’，根据归纳假设T’无简单回路，再加回v及其关联
边又得到图T，则T也无简单回路。
再由图的连通性可知，加入任何一边后就会形成圈，且只有一个圈，否则原图
中会含圈。
9
二. 基本定理——证明
证明(4):(3)(4)，即证一个无圈图若加入任一边就形成圈，
则该图连通，且其任何一边都是桥。
若图不连通,则存在两个顶点vi和vj，在vi和vj之间没有路，若
加边(vi,vj)不会产生简单回路，但这与假设矛盾。由于T无简单回

离散数学第七章图论习题课ppt课件

离散数学第七章图论习题课ppt课件
有环和平行边，u至多与其余n-1个结点中每一个 有一条边相连接，即deg(u)≤n-1，因此，⊿ (G) ＝maxdeg(u)≤n-1。
24
设G是一个n阶无向简单图，n是大于等于3的 奇数。证明图G与它的补图中度数为奇数的结 点个数相等。
证明： 因为G是n阶无向简单图，且n是大于等于3的奇数，
故无向图的结点数为奇数，则所对应的n阶完全图 中每个结点的度数为n-1即为偶数， 利用奇数+奇数=偶数，偶数+偶数=偶数，所以， 在G中结点度数为奇数的结点，在其补图中的度 数也应为奇数，故G和其补图的奇数结点个数也 是相同的。
25
P286 1、在无向图G中，从结点u到结点v有一条长度为 偶数的通路，从结点u到结点v又有一条长度为奇 数的通路，则在G中必有一条长度为奇数的回路。
(4) D中长度为4的回路有多少条？ 答： 长度为4的回路为11条。
(5) D中长度4的通路有多少条？其中有几条是回路？ 答：长度4的通路88条，其中22条为回路。
(6) 写出D的可达矩阵。 44的全1矩阵。
17
简单无向图 G 必有2结点同度数。
证: 令 G={v1,…,vn}，
(2) n阶非连通的简单图的边数最多可为n-1阶连通图 加上一个孤立点，所以边数为(n-1)(n-2)/2，最少为0。
20
一个图如果同构于它的补图，则该图称为自补图。
1)一个图是自补图，其对应的完全图的边数必为偶数; 2)证明：若n阶无向简单图是自补图，则n=4k或n=4k+1
（k为正整数）。 解：
平面图的对偶图
无向树及其性质 根树及其应用
地图着色与平 面图着色
3
4
一、无向图与有向图

离散数学第七章群与环

离散数学第七章群与环
然而，在给出的运算下该集合是一个幺半群。 例7.16 在一般意义下的乘法运算下，所有非零实数组成的集合构成一个群。 a≠0的逆是1/a。
7.2 群
定义 7.9 若群G是有穷集，则称G是有限群，否则称为无限群。群G的基数 称为群G的阶。含有单位元的群称为平凡群。
7.2 群
例7.17 <Z，+>是无穷群，<S，⊙>，其中S={a，b，c}，⊙的运算表如表7.3 可以验证，<S，⊙>是群，a为幺元，b和c互为逆元；又因为|G|=3，故<S， ⊙>是3阶群。 ⊙ a b c a a b c b b c a c c a b
半群 群 子群与群的陪集分解 循环群与置换群 环与域
7.3.1 子群的概念
子群就是群的子代数。 定义 7.13 给定群G，H是G的子集，使得 （1）G的单位元eH ， （2）如果a和bH ，那么abH ， （3）如果aH ，那么 H。
则称H为G的一个子群，（1）和（3）说明H是G的子幺半群。如果
PART 01 PART 02 PART 03 PART 04 PART 05
半群 群 子群与群的陪集分解 循环群与置换群 环与域
7.4 循环群与置换群
定义7.15 设<G，>是群，若a∈G，对x∈G，k∈Z，有x= ，则称<G， >是循环群，记作G=<a>，称a是群<G，>的生成元。
例 7.11 给定<Z，+>和<Q，*>，其中Z和Q分别为整数集和有理数集，+和*
分别是一般意义下的加法和乘法。可知<Z，+>是群，0是幺元，每个元素
i∈Z的逆元为-1；<Q，*>不是群，1是幺元，0无逆元。但<Q-{0}，*>是群。

第7章 图论 [离散数学离散数学(第四版)清华出版社]

第7章 图论 [离散数学离散数学(第四版)清华出版社]

6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
21
例：
a j i h c g d
1(a)
无 向 图
b
f
e

2(b)
7(j) 8(g) 9(d) 10(i)
6(e)
3(c) 4(h)
5(f)
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
22
例：
1(b)
有向图
第四部分：图论（授课教师：向胜军）
6
[定义] 相邻和关联
在无向图G中，若e=(a, b)∈E，则称a与 b彼此相邻(adjacent)，或边e关联 (incident) 或联结(connect) a, b。a, b称为边e的端点或 结束顶点(endpoint)。 在有向图D中，若e=<a, b>∈E，即箭头 由a到b，称a邻接到b，或a关联或联结b。a 称为e的始点(initial vertex)，b称为e的终点 (terminal/end vertex)。
证明思路：将图中顶点的度分类，再利用定理1。
6/27/2013 6:02 PM 第四部分：图论（授课教师：向胜军） 9
[定理3] 设有向图D=<V, E>有n个顶点，m 条边，则G中所有顶点的入度之和等于所 有顶点的出度之和，也等于m。
即：
d ( v i ) d ( v i ) m.
i 1 i 1
n
n
证明思路：利用数学归纳法。
6/27/2013 6:02 PM
第四部分：图论（授课教师：向胜军）
10
一些特殊的简单图：
(1) 无向完全图Kn(Complete Graphs)

离散数学(第二版)第7章格和布尔代数和

离散数学(第二版)第7章格和布尔代数和
第七章 格和布尔代数
离散数学(第二版)第7章格和布尔代 数和
第七章 格和布尔代数
7.1 格 与 子 格
本章将讨论另外两种代数系统——格与布尔代数， 它 们与群、 环、 域的基本不同之处是： 格与布尔代数的基集 都是一个偏序集。 这一序关系的建立及其与代数运算之间 的关系是介绍的要点。 格是具有两个二元运算的代数系统， 它是一个特殊的偏序集， 而布尔代数则是一个 特殊的格。
于是， 我们有下列对偶原理。
第七章 格和布尔代数
定理7.1.2 如果命题P在任意格〈L， 〉上成立， 则
将L中符号∨， ∧，
∧， ∨，
P*在任意格〈L， 〉上也成立， 这里P*称为P的对偶式。
在上述对偶原理中， “如果命题P在任意格〈L， 〉
上成立”的含义是指当命题P中的变量取值于L中， 且上确
界运算为∨， 下确界运算为∧， 则P对于它们也成立。
第七章 格和布尔代数
再设a=a∧b， 则a∨b=(a∧b)∨b=b(由吸收律)， 即
a∨b=b。
最后， 设b＝a∨b， 则由a a∨b可得a b。
因此， (1)中3个命题的等价性得证。
(2) 因为 a a∨b， a a∨c, 故a (a∨b)∧(a∨c)。 又
因为
b∧c b a∨b b∧c c a∨c
条件是b a, 则〈L, 也是偏序集。 我们把偏序集〈L, 和〈L, 称为是相互对偶的。 并且它们所对应的哈
斯图是互为颠倒的。 关于格我们有同样的性质。 定理7.1.1 若〈L, 是一个格， 则〈L, 也是一
个格, 且它的并、 交运算∨r, ∧r对任意a, b∈L满足 a∨rb=a∧b，a∧rb=a∨b
证明 先证幂等性成立。 由吸收律知 a∧a＝a∧(a∨(a∧b))＝a a∨a＝a∨(a∧(a∨b))＝a

离散数学第七章二元关系


19
证明
(2) 任取<x,y>, <x,y>∈(FG)1 <y,x>∈FG t (<y,t>∈F∧<t,x>∈G) t (<x,t>∈G1∧<t,y>∈F1) <x,y>∈G1 F1 所以 (F G)1 = G1 F1
20
关系运算的性质
定理7.3 设R为A上的关系, 则 RIA= IAR=R <x,y> <x,y>∈RIA t (<x,t>∈R∧<t,y>∈IA) t (<x,t>∈R∧t=y∧y∈A) <x,y>∈R
例如 A = P(B) = {,{a},{b},{a,b}}, 则 A上的包含关系是 R = {<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>, <{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>} 类似的还可以定义： 大于等于关系, 小于关系, 大于关系, 真包含关系等.
注意： 关系矩阵适合表示从A到B的关系或A上的关系（A,B为有 穷集） 关系图适合表示有穷集A上的关系
11
实例
例4 A={1,2,3,4}, R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}, R的关系矩阵MR和关系图GR如下：
1 1 0 0 0 0 1 1 MR 0 0 0 0 0 1 0 0
10
关系的表示

离散数学第7章群、环和域

所以，(x∗y)∗z=x∗(y∗z)，故<R,*>是一个半群。 7.1.2 独异点 定义7.1.3 设G,*是半群，如果运算*的单位元eG，
则称半群G,*为含幺半群或独异点。
第7章 群、环和域
若G,*为独异点，且*是可交换的，则称G,*为可换 的独异点。
例如，设A是任一集合，P (A)是A的幂集合。集合并运算 ∪在P (A)上是封闭的，并运算∪的单位元P (A)，所以半 群<P (A),∪>是独异点；交运算∩在P (A)上也是封闭的，交运 算∩的单位元AP (A)，所以半群<P (A),∩>也是独异点。显
第7章 群、环和域
⑴ (a–1)–1=a ⑵ a*b有逆元，且(a*b)–1=b–1*a–1 证明：⑴ 因a*a–1=a–1*a =e，故(a–1)–1=a ⑵ 因(a*b)*(b–1* a–1)=(a*(b*b–1)*a–1
=a*e*a–1=a*a–1=e 又
(b–1* a–1)*(a*b)=(b–1*a–1)*(a*b) =b–1*(a–1*a)*b=b–1*e*b=b–1*b=e
第7章 群、环和域
返回总目录
第7章 群、环和域
第7章 群、环和域
7.1半群和独异点
7.1.1广群和半群 代数系统<S,*>又称为广群。 定义7.1.1 设<S,*>是代数系统，*是S上的二元运算，如 果*满足结合律，则称代数系统<S,*>为半群。
例如，代数系统<I,＋>、R,·、<P(a),∪>、<P(a),∩>、
则称该群为阿贝尔(Abel)群，或称可交换群。 整数加法群I,＋中的加法运算是可交换的，所以，整
数加法群是阿贝尔群，群R-0,·中的乘法运算也是可交 换的，所以，R-0,·也是阿贝尔群。

离散数学第七章图的基本概念


4.无向图的连通性
若无向图G中任何两顶点都连通,则称G是连通图.
对于任意的无向图G.设V1,V2,…,Vk是顶点之间连通关系的 等价类,则称他们的导出子图为G的连通分支.用p(G)表示G 的连通分支数.
V1 e1
e2 e3
V3
e4 V2
V4
a
de
h
i
b
c
f
g
5.有向图的连通性
若略去有向图D中各边的键头,所得无向图是无向连通图,则 称D是弱连通图(或称D是连通图).
(2) mij d (vi )(i 1,2,..., n)
j 1
mn
nm
n
(3) mij mij d(vi ) 2m
j1 i1
i1 j1
i 1
m
(4) mij 0 vi是孤立点 j 1
(5)若第j列与第k列相同, 则说明e j与ek为平行边.
2.有向图的关联矩阵
设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em} 1, vi为ej的始点
e1,e2,e3},{e1,e2,
e2
e4},{e9}等边割集 ,e9是桥.
e3 V4
e5 e6
V5 e4
V6
e9
V7
7.3 图的矩阵表示
1.无向图的关联矩阵
设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}
令mij为顶点vi与ej的关联次数, 则称(mij)n×m为G的关联矩阵.记为M(G)
若Γ 满足:vi-1,vi为ei的端点(若G为有向图,vi-1是ei的始 点,vi是ei的终点)i=1,2,…,k,则称Γ 为G中通路,v0,vk分 别称为通路的始点和终点,Γ 中边的数目k称为通路长度.

离散数学--第7章 图论-2(路与连通)

u1 v4 v1 v4 v3 u4 v2 u4 u3 G2 v3 u u13 v1 u2 v2 u2
15
连通图可以看成是只有一个连通分支的图，即 w(G ) 1 。
返回 结束
7.2.2 图的连通性
4、有向图的连通
强连通—— G 中任一对顶点都互相可达 (双向) 连通 单向连通—— G 中任一对顶点至少一 向可达
路
10
(vi v j ) ，则从 vi 到 v j 存在长度小于等于
n 1的路。
证明思路：多于n-1条边的路中必有重复出现的结点，反 复删去夹在两个重复结点之间的边之后，剩余的边数不会 超过n-1条边。
v n 在一个 阶图中，若从顶点 i 到 v j 存在 推论：
通路(vi v j ) ，则从 vi 到 v j 存在长度小于等于
返回 结束
7.2.2 图的连通性
7.2.2 图的j 存在路，称 有向图中，从 vi 到 v j 存在路，称 (注意方向) 2、短程线，距离。 短程线——连通或可达的两点间长度最短的 路。 距离——短程线的长度，
12
vi 到 v j 是 连通的(双向)。 vi 可达 v j 。
1 v1e1v2e5v5e7v6 2 v1e1v2e2v3e3v4e4v2e5v5e7v6
3 v1e1v2e5v5e6v4e4v2e5v5e7v6
…………
初级通路
简单通路
复杂通路
返回 结束
7.2.1 路
例1、(2)
7
图(2)中过 v 2 的回路 (从 v 2 到 v 2 )有：
1 v2e4v4e3v3e2v2 2 v2e5v5e6v4e3v3e2v2
7.2 路与连通
内容：图的通路，回路，连通性。 重点：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

设 V v1,v1,L ,vn为图 G 的顶点集，称 d(v1), d(v2),L , d(vn) 为G 的度数序列。
2、握手定理。
定理1： 设图 G V , E 为无向图或有向图，
V v1,v1,L ,vn，E m ( m为边数)，
n
则
d (vi ) 2m
i 1
n
2、握手定理 d (vi ) 2m i 1
E (v1,v2),(v2,v2),(v2, v3),(v1, v3),(v1, v3),(v1, v4)
图形表示如右：
e2
v1
v5
e1
e6
v2 e4 e5
v4
e3
v3
例1、(2) 有向图 D V , E ，V v1,v2,v3,v4,v5
E v1, v2 , v3, v2 , v3, v2 , v3, v4 , v2, v4 , v4, v5 , v5, v4 , v5, v5
对有向图相应地还有 (D) ， (D) ，
(G) ， (G) 。
如例1的(2)中，
d (v2 ) d (v2 ) d (v2 )
13 4 d (v1) d (v1) d (v1)
10 1
d (v5 ) d (v5 ) d (v5 ) 2 2 4
(D) 4， (D) 1 。
如例1的(1)中，
v1
v5
e1与 v1, v2 关联的次数均为1， e1
e6
e2 与 v2 关联的次数为2， e2 v2 e4 e5
v4
边 e1, e4 , e5 , e6都是相邻的， v5 为孤立点，v4 为悬挂点，
e3 v3
e6 为悬挂边，e2 为环，e4 , e5 为平行边，重数2，
G 为多重图。
推论：任何图中，度为奇数的顶点个数为偶数。
定理2： 设D V , E 为有向图，
V v1,v1,L ,vn ，E m，则
n
n
d (vi ) d (vi ) m 。
i 1
i 1
例2、(1) (3,3, 2,3) ，(5, 2,3,1, 4)能成为图的度数
序列吗？为什么？
(2) 已知图G 中有10条边，4个3度顶点，其余顶 点的度数均小于3，问 G中至少有多少个顶点？
为什么？
三、子图，补图。
1、子图定义： 设G V , E ，G' V ', E ' 是两个图，若V ' V ，且 E ' E ，则称 G ' 是 G 的子图，G是 G ' 的母图，记作 G ' G 。 真子图—— G ' G且 G ' G (即V ' V 或
E ' E )。 生成子图—— G ' G 且 V ' V 。
孤立点——无边关联的点。
环——一条边关联的两个顶点重合，称此边 为环 (即两顶点重合的边)。
3、相关概念。 (2) 悬挂点——只有一条边与其关联的点，所
对应的边叫悬挂边。 (3) 平行边——关联于同一对顶点的若干条边
称为平行边。平行边的条数称为重数。 多重图——含有平行边的图。 简单图——不含平行边和环的图。
3、相关概念。
(2)
0 vi与ek不关联
无向图关联的次数 1 vi与ek关联1次
2 vi与ek关联2次(ek为环)
1 vi为ek的始点
有向图关联的次数 0 vi与ek不关联
(无环)
1 vi为ek的终点
3、相关概念。 (2)
相邻 点边的的相相邻邻————两两点边间有有公边共，端称点此，两称点此相两邻边相邻
图无 有向 向图 图GD
V,E V,E
V 记为V (G), E记为E(G) V 记为V (D), E记为E(D)
2、图的表示法。 有向图，无向图的顶点都用小圆圈表示。
无向边 (a,b) ——连接顶点 a, b 的线段。
有向边 a,b ——以 a 为始点，以 b 为终点的有向线段。
例1、(1) 无向图G V , E ，V v1,v2,v3,v4,v5
图论简介
图论是一个古老的数学分支，它起源于游戏 难题的研究。图论的内容十分丰富，应用得相当 广泛，许多学科，诸如运筹学、信息论、控制论、 网络理论、博弈论、化学、生物学、物理学、社 会科学、语言学、计算机科学等，都以图作为工 具来解决实际问题和理论问题。随着计算机科学 的发展，图论在以上各学科中的作用越来越大， 同时图论本身也得到了充分的发展。本课程在第 七，八，九各章中介绍与计算机科学关系密切的 图论的内容。
补图的概念， 5、图的同构的定义。
一、图的概念。 1、定义。
无序积 A& B (a,b) a A b B
无向图 G V , E E V &V ， E 中元素为无向边，简称边。
有向图 D V , E E V V ， E 中元素为有向边，简称边。
一、图的概念。
1、定义。
无序积 A& B (a,b) a A b B
4、完全图
设G V , E 为 n 阶无向简单图，若G 中每个 顶点都与其余 n 1个顶点相邻，则称G为n 阶
无向完全图，记作 Kn 。
若有向图D 的任一对顶点 u, v(u v)，既有有向 边 u, v 又有有向边 v,u ，则称D 为有向完全图。
例如：
K4
K5
二、顶点的度数，握手定理。 1、顶点的度数 (简称度)。
无向图G V , E ，vi 的度数记 d (vi )，指与vi
相关联的边的条数。
有向图G V , E ，vi 的度数
d (vi ) d (vi ) d (vi )
二、顶点的度数，握手定理。 1、顶点的度数 (简称度)。
最大度 (G) maxd(v) v V 最小度 (G) mind(v) v V
图形表示如右：
3、相关概念。
(1) 有限图—— V , E都是有限集的图。 n 阶图—— V n 的图。
零图—— E 的图。特别，若又有 V 1 ，
称平凡图。
(2) 关联 (边与点关系)——设边 ek (vi , v j ) (或 vi , v j )，则称 ek 与 vi (或 v j)关联。
第七章 图的基本概念
第一节 无向图及有向图
内容：有向图，无向图的基本概念。 重点：1、有向图，无向图的定义，
2、图中顶点，边，关联与相邻，顶点 度数等基本概念，
3、各顶点度数与边数的关系
n
d (有向图，无向图的基本概念。 重点：4、简单图，完全图，子图，