离 散 数 学
9
关系图举例
• 例:设A={1,2,3,4,5} , R={<1,1>,<1,2>,<3,2>,<1,4>,<5,4>,<5,1>}, 则,R的关系图GR如下:
1
5 4 3
离 散 数 学
10
2
下面关系图有什么性质
a b c a b d c b a c
(a)
自反,反对称, 传递
(b)
离 散 数 学
15
逆关系
定义2.2.3 设R是A到B的二元关系,令: R–1={<y,x>|<x,y>∈R},称为R的逆关系。 显然,(R–1)–1=R 。 定理2.2.3 设R是A到B的二元关系, S是B到C的 二元关系,则:(R • S) –1 = S–1 • R–1 证明:∵任意<x,z>∈(R • S) –1 <z,x>∈R • S 存在y∈B,使得<z, y>∈R且 <y, x>∈S <y,z>∈ R–1且<x,y>∈ S–1 <x,z>∈S–1 • R-1
离 散 数 学
8
关系的图的表示
• 一个在有穷集合A上的二元关系R可以用 一个有向图GR表示。令| A | = n ,〈 i, j 〉 表示A中第i个元素和第j个元素的序偶, GR=〈V,E〉, | V | = n ,V中的每个结 点分别表示A中的一个元素。ninj E, 即从结点i到结点j有一条有向边,当且仅 当〈 i,j 〉 R。
2
2
离 散 数 学
2
二元关系几个性质的定义
定义2.1.2 设R是定义在集合A上的二元关系: