第四章：关系及图.doc

4.1 Product Sets and Partitions 笛卡儿乘积与划分

1) An ordered pair (a , b) 一个有序对(a , b)是对象a和b以指定的次序，a先出现然后b出现的一个列举。
2) 如果A和B是两个非空的集合，定义笛卡儿乘积(product set or Cartesion product) A×B为a∈A 和b∈B的所有有序对（a , b）所组成的集合，Thus
A×B ＝{(a , b) | a ∈ A and b ∈B}
3) 定理一：且有card（A×B）＝card（A）•card（B）
4) 一个非空集合的划分（partition）或商集（ quotient set ）是A的非空子集的一个集合Þ，使得
1: A的每一个元素属于Þ中的某个集合：
2:如果A1和A2是Þ中的不同元素那么A1∩A2＝Ф
Þ中的集合称为划分中的块（block）或单元（cell）。

4.2 Relation and Digraphs 二元关系和又向图

1） 设A和B是非空集合，从A到B的关系（relation）R是A×B的一个子集，如果RA×B且（a, b）∈R,那么称a与b是R相关的（a is relation to b by R）记作：aRb，
如果a与b不是R相关的，记作a!Rb
通常A与B是相等的，这种情况下往往称R A×B是A上的关系，而不是A到A的关系。
2) 注：如果一个集合的全部元素（可以只是一个）都是有序对，则称这个集合为一个二元关系，记作R，对于某个二元关系R，如果（x，y）∈R，则记作rRy，如果（x，y）R，则记作x!Ry.
3) 设A，B为非空集合，则称A×B的任意子集所定义的二元关系为A到B的一个二元关系，特别是A＝B时，称A上的二元关系。
4）关系R的所有有序对的第一元素所组成的集合称为R的定义域（domain）即
Dom（R）={x| y ，(x, y) ∈R }
关系R的所有有序对的第二元素所组成的集合称为R的值域（range）即
Ran（R）={y| x ，(x, y) ∈R }
关系R的所有有序对的两个元素所组成的集合称为R的域（）即
Fld（R）= Dom（R） Ran（R）
显然，若R是从A到B的关系，Dom（R）＝A，Ran（R）＝B。
5）如果从A到B的关系且x∈A，定义R（x）是具有性质――x与y是R相关的――B中所有y所组成的集合，称为x的R－相关集（R－relation set of x），thus
R（x）＝{ y∈B| x R y }
Similarly，如果A1A，则R（A1）是具有性质――对A1中的某个元素x，x与y是R相关的，B中所有y所组成的集合，称为A1的R相关集（R－relation set of A1）,thus
R(A1)={y∈B|对A1中的某个元素x，xRy}
注：R（x）是关于x的集合，但里面所包含的元素却是(x, y)中的y，即第二元素
定理一;设R是从A到B的关系，A1 和A2 是A的子集，then
(a) 若A1 A2，则R（A1）R（A2）
(b) R（A1∪A2）＝R（A1）∪R（A2）
(c) R（A1∩A2）R(A1)∩R(A2)
定理二：设R和S 是从A到B的关系，如果A中有a，有R（a）＝S（a），then R＝S.
6） 果A＝{ …}和B＝{ …}分别包含n个和m个元素的有限集合，R 是 从到B的关系，那么可用m×n的矩阵，表示R，then

矩阵没MR称作R的矩阵（matrix of R）。
7） 关系的又向图,用内部标号小圆圈表示相应的定点（vertices），又向线段表示边（edge），所得的图称为又向图（direct graph）或 方向图（digrahp）。
4．3

4．4 Properties of Relations 二元关系的性质
自反关系
设R是集合 A 中的二元关系。对于每一个 x∈A来说，如果都有 xRx，亦即 ∈R，则称 R 是个自反的关系（reflexive）。
注:若关系矩阵具有自反性，则关系矩阵的主对角线上的元素都为“1”，关系图中的每个点都有环。
非自反关系
设 R 是集合 A 中的二元关系。对于每一个 x∈A 来说，如果都有 x!Rx，亦即 ∈R，则称 R 是个非自反的关系（irreflexive）。
注:如果是非自反关系，则矩阵主对角线上全为“0”，关系图中每个点都没有环。
注：显然存在既不是自反的也不是非自反的关系。

对称关系
设 R 是集合 A中的二元关系。对于每一个 x,y∈A 来说，如果每当有 xRy，则必定有 yRx，那么称 R 是个对称(symmetric)的关系。
ab ( a∈A ∧ b∈B ∧ a R b )→ b R a
注：如果关系对称，则其的关系矩阵是对称的，且在关系图中，若两点之间有边，则一定是方向相反的一对有向边。

反对称关系
设 R 是集合 A 中的二元关系。对于每一个 x,y∈A 来说，如果每当有 xRy 和 yRx，就必有 x=y，那么称 R 是个反对称(antisymmetric)的关系。
ab ( a∈A ∧ b∈B ∧ a R b ∧ b R a )→ a=b
注：如果关系是反对称性，则其在其关系矩阵中的任何非主对角线上的元素和与其对称的元素不会同时为“1”，而在关系图中，如果两点之间有边的，则一定有且只有一条有向边。
注：对于任意a，b∈A，当a≠b且（a，b）R，（b，a）R时，则此时为对称，也为反对称，即在关系矩阵中，只有主对角线才有“1”，但不一定全为“1”。
非对称关系――――――――――不作要求，看看就好
ab ( a∈A ∧ b∈B ∧ (a, b) ∈R )→ (b, a) R
显然，一个非对称关系的关系矩阵主对角线上全为“0”，所以是非自反，同时也是反对称的，由于是两中关系的特例，了解即可。
可传递关系
设 R 是集合 X 中的二元关系。对于每一个 x,y,z∈A来说，如果每当有 xRy 和 yRz，就必有 xRz，则称 R 是个可传递的关系。
注：如果从某点出发经过两条边可以到达另一点，则一定有一条边从此点领接到那点，或者没有任何点可以经过两条边到另一个点，就可判定R是可传递的。
4．5 Equivalence Relations
等价关系
设是 X 一个集合和 R 是 X 中的二元关系，如果关系 R 是自反的、对称的和可传递的，则称 R 是个等价关系。
划分
给定非空集合 S，又设非空集合 A= 和 ={1,2,...m}。对于任何 i,j，如果满足
(1) S
(2) =S
(3) = 或 =
则称集合 A 是集合 S 的划分（Partition）。
注：对于任何有穷集合，最小划分是由作为类的集合本身构成；而最大划分则是由仅包含单个元素的类组成。
等价类
设 R 是集合 A 的等价关系，对于任何 x∈A 来说，定义集合A 为：
={y|(yA) ∧(yRx)}
则称集合是由 xA 生成的关系 R 的等价类（equivalence classes）。
4．6
我把他跳过了，应为写的是计算和画图。不过存在伪码。
4.7 Operations on Relations
complementary relation 补 thus

inverse 逆 thus

and

and

reflexive closure 自反闭包 symmetric closure 对称闭包 transitive closure 传递闭包
对集X上的二元关系R，有时候希望R具有一些有用的性质，这就需要在R中增加一些序偶，但又希望R不要变得太大。闭包运算就能解决这一问题。 
设R为X上的二元关系，若有另一个关系R′满足：
1）  R′是自反的（对称，可传递的）；
2）  R′ÊR；
3）对任何自反的(对称的，传递的)关系R″，若R″ÊR，就有R″Ê R′，则称关系R′为R的自反（对称，传递）闭包，记作：r ( R ), (S (R),t (R)) 
设R为X上的二元关系，则
1）R是自反的，当且仅当r(R)=R；
2）R是对称的，当且仅当S(R)=R；
3）R是传递的，当且仅当t(R)=R。
2）
定义1：关系的合成
设 R 是从集合 X 到集合 Y 的关系，并且 S 是从集合 Y 到集合 Z 的关系。于是，可把从 X 到 Z 的关系
RS 定义成 RS={|(xX)(zZ)(y)((yY)(R)(S))}
通常称 RS 是关系 R 和 S 的合成关系。从 R 和 S 求得 RS 的运算，称为关系的合成。

4.8 Transitive Closure and Warshall’s Algorithm

下表是我认为比较容易的Warshall算法：

因为第一列在第一行和第四行有“1”存在，所以在第一行和第四行线，如图右

因为W的下标是“0”，所以要选择第一行和第一列。

同理，由于第一行中在第一列和第二列中存在“1”，所以在第一，二列划线，图右

在横线和竖线的交点的矩阵位置改为“1”，无论原先其是否位“1”。得到

因为第二列在第一行和第四行有“1”存在，所以在第一行和第四行线，如图右

因为W的下标是“1”，所以要选择第二行和第二列。

同理，由于第二行中在第三列中存在“1”，所以在第三列划线，图右

在横线和竖线的交点的矩阵位置改为“1”，无论原先其是否位“1”。得到

因为第三列在第一、二行和第四行有“1”存在，所以在第一、二行和第四行线，如图右

因为第三行中没有“1”，所以无法划线，得图右

因没有交点，所以也无法标“1”，就无须再改得W3

由于第四列全为“0”，自然无法划线，即没有交点，所以有W4

有此可知，有

看来我的任务也完成了，真是不好意思啊，由于我的偷懒，到现在才上传，里面定有很多疏漏，望大家多多指教。^_^

由于考试考得是重点，所以我省略了本章的一些知识点，入度 和 出度，大家若是想了解，就也去看看。

^_^ ^_^ 谢谢啊 。