离散数学 二元关系 PPT课件

问如何安排任务的加工次序，使截止时间D最 小？——最优调度问题
单机调度----拓扑排序
拓扑排序
构造一个包含某个给定部分序的全序的过程 。
拓扑排序算法----
1
对有限集T上给定的部分序R，产生一个全序S
Step1: (初始化)
2
3
令 k=1， T‘=T
Step2: (取下一个元素)
While T’ ≠
机器j的停止时间 Dj=max {sj(tk) | tk ∈Tj} + L(tk)
所有任务的截止时间
D=max{ Dj | j=1,2,…,m}
R={<ti,tj>|t1, tj∈T,i=j 或ti完成后tj才可开始加工} 一个可行调度是T的划分{T1,T2,…Tm},
Ti≠,由安排在机器cj上加工的所有任务组成，
多机调度
对任务集Tj,j=1,2,…,m,存在调度函数 sj: TjN，且满足下 述条件 (1)i, 0≤i<D, |{tk |tk∈T, sj(tk) ≤ i < sj(tk)+L(tk)}| ≤ 1 j=1,2,…,m 表示D之前的每个时刻 i，每台机器cj上至多只有一个任 务正在加工 (2) tk∈Ti, tj∈Tj, <tj, tj>∈R si(tk)+L(tk)≤sj(tL) i, j=1,2,…,m, i ≠ j 表示若任务tk与tj有偏序约束，则tk完成后tj才能开始加工
第4章 二元关系与函数
4.1 集合的笛卡儿积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数
集合论在计算机科学中的应用

1。 GS :
2 。
4。
。 3
关系的集合运算
关系就是集合 ∩、∪、-、和补运算对关系也适用 特别的

R=(A×BBiblioteka -R思考题设A和B分别是n元和m元有限集，则共有多 2mn 少个不同的A到B的关系？ 设A(和B)都是非空有限集，则A上的空关系、 恒等关系和A上(A到B的)全关系的关系图和 关系矩阵有何特点。 怎样通过关系图和关系矩阵求domR和ranR

|A1×A2×…×An|=|A1|·|A2|·|A3|…｜An|
例

设A={a,b}, B={1,2,3}, C={p,q}, D={0}, E=Φ
(a) A×B={〈a,1〉,〈a,2〉,〈a,3〉,〈b,1〉,〈b,2〉,〈b,3〉} (b) A×B ×C = {〈a,1,p〉,〈a,1,q〉,〈a,2,p〉,〈a,2,q〉, 〈a,3,p〉,〈a,3,q〉,〈b,1,p〉,〈b,1,q〉, 〈b,2,p〉,〈b,2,q〉,〈b,3,p〉,〈b,3,q〉} (c) C×D= {〈p,0〉,〈q,0〉} (d) D×(C2)= D×{〈p,p〉,〈p,q〉,〈q,p〉,〈q,q〉} ={〈0,〈p,p〉〉,〈0,〈p,q〉〉,〈0,〈q,p〉〉,〈0,〈q,q〉〉} (e) D×C ×C = {〈0, p,p〉,〈0, p,q 〉, 〈0, q,p 〉, 〈0, q,q 〉} (f) A×E= Φ
RA×B， A到B的二元关系R可用m×n阶矩阵 表示：MR=(rij)m×n，其中
rij=
1,如果aiRbj 0,如aiRbj
则称矩阵MR=［rij］是R的关系矩阵

例
A={a1,a2},B={b1,b2,b3}

则关系R的各次幂为： R0 =A ={<1,1> ， <2,2> ， <3,3> ， <4,4> ， <5,5>} R1=R
R2= R • R={<1,1>，<2,2>，<1,3>，<2,4>， <3,5>}
R3=R2 • R={<1,2>，<2,1>，<1,4>，<2,3>， <2,5>}
R4= R3 • R={<1,1>，<2,2>，<1,5>，<2,4>，
从关系图来看关系的n次幂
R：
1
2
3
4
5
R2：
1
2
3
4
5
R2就是从R的关系图中的任何一个结点x出发，长 为2的路径，如果路径的终点是y，则在R2 的关系 图中有一条从x到y的有向边。其他以次类推：
R3：
1
2
3
4
5
R4：
1
2
3
4
5
定理 设|A|=n，R A×A，则必有i，j∈N， 0≤i＜j≤2n2，使得Ri=Rj。
＝R5，R7＝R6•R＝R5，…，Rn＝R5 (n＞5) 故Rn{R0,R1,R2,R3,R4,R5}。
S0=IA,S1＝S,
S2＝S•S＝{<a,c>,<b,d>,<c,e>,<d,f>}， S3＝S•S•S＝S2•S＝{<a,d>,<b,e>,<c,f>}， S4＝S3•S＝{<a,e>,<b,f>}， S5＝S4•S＝{<a,f>}， S6＝S5•S＝Φ， S7＝Φ， …， 故，Sn{S0,S1,S2,S3,S4,S5,S6}

第七章 §1
二元关系
有序对与笛卡尔积
定义 两个元素 x 与 y 按一定顺序排列构成的二 元组称为一个有序对（或序偶） ，记为〈x,y〉 ，称 x 为第一元素，y 为第二元素。 性质 (1) x ≠ y ⇒ 〈 x , y 〉 ≠ 〈 y , x 〉 (2) 〈 x , y〉 = 〈 u, v 〉 ⇔ x = u ∧ y = v
∀x∀y( x , y ∈ A ∧ 〈 x , y〉 ∈ R ∧ 〈 y, x〉 ∈ R → x = y)
则称 R 是反对称的。
例 A={1,2,3}， R1 = {〈1,1〉 , 〈 2, 2〉} ，
R2 = {〈1,1〉 , 〈 2,1〉 , 〈1, 2〉}， R3 = {〈1, 2〉 , 〈1, 3〉} R4 = {〈1, 2〉 , 〈1, 3〉 , 〈 2,1〉}
G F = {〈 2, 2〉 , 〈 2, 3〉 , 〈 2, 4〉 , 〈 3, 4〉}
例 F = { 〈 x , y〉 | x 是 y 的父亲
G = { 〈 x , y〉 | x 是 y 的母亲 H = { 〈 x , y〉 | x 是 y 的兄弟 R = { 〈 x , y〉 | x 是 y 的姐妹
⎡0 ⎢1 M=⎢ ⎢0 ⎢0 ⎣ 1 0 0⎤ 0 1 0⎥ ⎥ 0 0 1⎥ 0 0 0⎥ ⎦
1 0 1⎤ 0 1 0⎥ ⎥ 0 0 0⎥ 0 0 0⎥ ⎦
由此计算，依次得
⎡1 ⎢0 M2 = ⎢ ⎢0 ⎢0 ⎣ 0 1 0⎤ ⎡0 ⎢1 1 0 1⎥ ⎥， M 3 = ⎢ 0 0 0⎥ ⎢0 ⎢0 0 0 0⎥ ⎦ ⎣
R1 既对称又反对称 R2 对称但不反对称 R3 反对称但不对称 R4 既不对称也不反对称
性质
(1) (2)