【精品】系统分析师复习资料(数学基础知识).doc

《【精品】系统分析师复习资料(数学基础知识).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、系统分析员考试复习一数学《计算机数学基础(1)》第三单元辅导.五种性质的定义欧拉图25哈密顿图26平面图26《计算机数学基础(1)》第三单元辅导五种性质的定义我们己经看到，在一•个很小的集合上就可以定义很多个不同的关系。但是真正有实际意义的只是其中很少的一部分，它们一般都是有着某些性质的关系。设R是集合A上的关系，R的性质主要有以下五种：门反性、反1‘1反性、对称性、反对称性和传递性。⑴自反性集合A上的关系我们说它是自反的，就是)为真。也就是说，如果命题“对于A中的任意元索兀，都在R中”为真，则/?是白反的。(2)反白反性集合A上的关系/?,我们说

2、它是反白反的，就是'巩兀丘"—鈕)为真。也就是说，如果命题“对于4屮的任意元索x,都不在R屮”为真，则R是反白反的。(3)对称性集合4上的关系R,我们说它是对称的，就是％矽(％妙为真。也就是说，如果命题“对于A屮的任意元索x和y,若eR则必有为真，则尺是对称的。(4)反对称性集合A上的关系R,我们说它是反对称的，就是'X矽(X矽心^Txf)为真。也就是说，如果命题“对于a屮的任意元索兀和)，，若eR且<尹,兀》°尺则必有兀二尹”为真，则尺是反对称的。因为以矽（喲等值于办唄奶2&））,所以，如果对于A中的任意两个不相同的元索

3、x和y,>和<^X>不同时在R屮，则R是反对称的。（5）传递性集合A上的关系R,我们说它是传递的，就是*°恥（确2屁Tx&）为真。也就是说，如果命题“对于人中的任意元素X、y和Z,若y>eR且，则必有z>eR”为真，则尺是传递的。它们的定义及其在关系矩阵、关系图屮的特征如表4.1所示。表4.1自反性反自反性对称性反对称性传谨性定义Vxe^,有€RoPxgA,有€R,则€Ro若>€7?且,贝IJ<7,r>空Ro若>€R且eR,贝IJeRo关系矩阵的特点主对角线元素全是1.

4、主对角线元素全是0.矩阵为对称矩阵。如果厂&=19且心八则廿0o关系图的特点图中每个顶点都有环。图中每个顶点都没环。如果两个顶点之间有辺，一定是一对方向相反的辺。如果两个顶点之间有辺，一定是条有向辺。如果顶点勺到心有边.，卩到忑有边.，则有禺到心有边.除有以上定义外，述可以通过集合间的关系来描述关系的五种性质。1.任何集合4上的白反关系R一定包含了A上的恒等关系，即OUR。2.A上的反自反关系R—定与乙不交，即^HA=0o如果厶门尺工0且匚笑R,那么R既不是自反的，也不是反自反的。3.A上的对称关系R一定满足等式=Ro4.反对称关系R则满足等式An

5、A_1-^。由此可以知道，如果/?既是对称的，乂是反对称的，则1.关于传递关系/?,它满足的条件是RoRgR。本单元重点：关系概念与其性质，等价关系和偏序关系，函数.图的概念，握手定理,通路、冋路以及图的矩阵表示.一、重点内容1.关系的概念包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.•二元关系，是一个有序对集合，设集合4Q/?={xeAA-yeB},记作乂心二元关系的定义域：Dom(/?)U4；二元关系的值域：Ran(R)U〃•关系的表示方法：集合表示法：关系是集合，有类似于集合的表示方法.列举法，如R={vl,l>,vl,2

6、>}；描述法：如关系矩阵:RqAXB,尺的矩阵1ajRbj'i=1,2...,加,、0aiRbjJ=1,2,...,关系图：R是集合上的二元关系，若a.heA}=AxA恒等关系4={<04〉d&A},妙是单位矩阵.3.关系的运算•关系的集合运算，有并、交、补、差和对称差.•复合关系/?=/?]•/?2=[3bjigagR2)复合关系矩阵：MR二MR,XMR2(和尔运算)，有结合律：(R・S)・T=R・(

7、S・T)•逆关系尺"={

8、g/?；矩阵Mr的主对角线元素全为1；关系图的每个结点都有自回路.•反自反性Vxe；矩阵Mr的主对角线元素全为0；关系图的每个结点都没有自冋路.•对称性若<兀』>€尺，则<”兀>丘尺；矩阵Mr是对称矩阵，即5=5；关系图屮有向弧成对出现，方向相反.•反对称性若<^y>^R且

9、Jx=y或若eR,x^y，则^R.矩阵Mr不出现对称元素.•传递性若wR且wR,则<

10、a,c>wR；在关系图屮，有从。到〃的弧,有从b到c的弧,则有从a到c的弧.判断传递性较为困难.可以证明：R是集合A上的二