离散数学中给定集合,给定相容关系且知道简化矩阵,如何求此集合的覆盖?

如题所述

集合上的相容关系是指具有自反和对称的关系,由于它具有自反性,故它的关系矩阵的对角线上的元素均为1,由于它具有对称性,故它的关系矩阵一定是对称矩阵,集合X有6个元素,它的关系矩阵是6阶矩阵,考虑到该矩阵是对称矩阵且对角线上的元素均为1,故只要写出对角线以下的元素即可,如果补上对角线上的1即是下面的简化形式:
x1
1
x2
1
1
x3
1
1
1
x4
0
0
1
1
x5
0
1
1
1
1
x6
1
0
1
0
1
1
x1
x2
x3
x4
x5
x6
集合上的一个覆盖是由集合的子集做为元素构成的集合,这些子集也称为块,集合的元素至少在一个块(子集)中,同块的元素必具有关系R,给定关系矩阵如何求覆盖?下面给一种方法,
首先考虑元素x1所在的块,从关系矩阵中看出x1与x2,x6有关系R,故{x1,x2,x6}是一个块,该块中没有出现x3,x4,x5,接下来再考虑元素x3所在的块,从关系矩阵中看出x3与x4,x5,x6有关系R,故{x3,x4,x5,x6}是一个块,这两块已包含了X的所有元素,故这两个块构成的集合就是X的一个覆盖,此时覆盖是
{{x1,x2,x6},{x3,x4,x5,x6}}
温馨提示:答案为网友推荐,仅供参考
相似回答