2022年系统分析师复习资料 .pdf

《2022年系统分析师复习资料 .pdf》由会员分享，可在线阅读，更多相关《2022年系统分析师复习资料 .pdf（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、反自反性集合 A 上的关系R，我们说它是反自反的，就是为真。也就是说，如果命题“对于A 中的任意元素x，都不在 R 中”为真，则R 是反自反的。(3) 对称性集合 A 上的关系R，我们说它是对称的，就是为真。也就是说，如果命题“对于A 中的任意元素x 和 y，若则必有”为真，则 R 是对称的。(4) 反对称性集合 A 上的关系R，我们说它是反对称的，就是为真。也就是说，如果命题“对于A 中的任意元素x 和 y，若且则必有”为真，则R 是反对称的。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 27 页学习必备欢迎下载因为等值于，所以，如

3、果对于 A 中的任意两个不相同的元素x 和 y，和不同时在 R 中，则 R 是反对称的。(5) 传递性集合 A 上的关系R，我们说它是传递的，就是为真。也就是说，如果命题“对于A 中的任意元素x、y 和 z，若且，则必有”为真，则R 是传递的。它们的定义及其在关系矩阵、关系图中的特征如表4.1 所示。表 4.1 除有以上定义外，还可以通过集合间的关系来描述关系的五种性质。1. 任何集合A 上的自反关系R 一定包含了A 上的恒等关系，即。2. A 上的反自反关系R 一定与不交，即。如果且，那么 R 既不是自反的，也不是反自反的。3. A 上的对称关系R 一定满足等式。4. 反对称关系R 则满足等

4、式。由此可以知道，如果R 既是对称的，又是反对称的，则。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 27 页学习必备欢迎下载5. 关于传递关系 R，它满足的条件是。本单元重点 ：关系概念与其性质，等价关系和偏序关系，函数. 图的概念，握手定理，通路、回路以及图的矩阵表示.一、重点内容1. 关系的概念包括定义、关系的表示方法：集合表示、矩阵表示、图形表示. 二元关系，是一个有序对集合，设集合A,B，,ByAxyxR，记作 xRy 二元关系的定义域：Dom(R)A； 二元关系的值域：Ran(R)B关系的表示方法：集合表示法：关系是集合，

5、有类似于集合的表示方法. 列举法，如R, ；描述法：如,ByAxyxR关系矩阵：RAB，R 的矩阵njmibRaRbarrMjijiijnmijR,.,2, 1,.,2, 101,)(关系图：R 是集合上的二元关系，若R，由结点 aI画有向弧到bj构成的图形 . 2. 几个特殊的关系空关系；唯一是任何关系的子集的关系. 全关系AAAbabaEA,恒等关系,AaaaIA，MI是单位矩阵 . 3. 关系的运算关系的集合运算，有并、交、补、差和对称差. 复合关系,2121RcbRbabcaRRR使，有复合关系矩阵：21RRRMMM(布尔运算 )，有结合律：(R S) TR (S T) 逆关系,1Ry

6、xxyR，TRRMM1，(R S)1=S1R1. 4. 关系的性质自反性RxxAx,； 矩阵RM的主对角线元素全为1；关系图的每个结点都精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 27 页学习必备欢迎下载有自回路 . 反自反性RxxAx,；矩阵RM的主对角线元素全为0；关系图的每个结点都没有自回路. 对称性若Ryx,，则Rxy,；矩阵RM是对称矩阵，即jiijrr；关系图中有向弧成对出现,方向相反 . 反对称性若Ryx,且Rxy,，则x=y 或若yxRyx,， 则Rxy,；矩阵RM不出现对称元素. 传递性若Rba,且Rcb,，则Rc

7、a,；在关系图中， 有从 a 到 b 的弧，有从 b 到 c 的弧，则有从a 到 c 的弧 . 判断传递性较为困难. 可以证明： R 是集合 A 上的二元关系，(1) (1)R是自反的IAR; (2)R是反自反的IAR; (3)R是对称的RR 1；(4)R是反对称的RR1IA；(5)R是传递的R R R. 关系的性质所具有的运算见表41. 表 4 1 二元运算的并、交、补、差、逆、复合具有的性质表运算关系性质自反性反自反性对称性反对称性传递性R1 R1R2 R1R2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 27 页学习必备欢迎下

8、载R1R2 R1R2 IA 由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.故IA，EA是等价关系 .具有反自反性、对称性、反对称性和传递性。是偏序关系 . 关系性质的判定，可以用定义、关系矩阵或关系图.传递性的判定，难度稍大. 也常如下判定：不破坏传递性的定义，可认为具有传递性. 例如可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性；5. 关系的闭包设 R 是非空集合A 上的二元关系，在关系R 中，添加最少的有序对，新关系用R 表示，使得 R 具有关系的自反(对称、 传递 )性质， R就是 R 的自反 (对称、传递 )闭包，记作 r(R) ，s

9、(R)和 t(R)。闭包的求法 ：定理 12：AIRRr)(；定理 13：1)(RRRs；定理 14 的推论：niiRRt1)(6. 等价关系和偏序关系极大 (小)元、最大 (小)元问题等价关系和偏序关系是具有不同性质的两个关系. 偏序关系等价关系传递性反对称性对称性自反性等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a 到 b，从 b 到 c 各有一条有向弧线，则从a 到 c 一定有有向弧线。等价类 ，若 R 是等价关系，与R 中的某个元素等价的元素组成的集合，就是R 的一个等价类， aR= b bA aRb.偏序集的哈斯图偏序集概念和偏序集的哈斯图

10、。哈斯图的画法： (1) 用空心点表示结点，自环不画；(2) 若 a b，则结点b 画在上边， a 画在下边，并画a 到 b 的无向弧； (3) 若,则R，此时， a 到 c 的有向弧不画出. 确定任一子集的最大(小 )元，极大 (小)元 . 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 27 页学习必备欢迎下载极大 ( 小 ) 元、最大 (小) 元、界一个子集的极大( 小) 元可以有多个，而最大( 小 ) 元若有，只能惟一 . 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于

11、子集中的任一元素；可以与某一元素相等，最大下界也是同样 . 7. 函数函数 , 设 f 是集合 A 到 B 的二元关系，aA, b B,且f，且 Dom(f)=A， f 是一个函数 (映射 ). 函数是一种特殊的关系.集合 A B 的任何子集都是关系，但不一定是函数. 函数要求对于定义域A 中每一个元素a，B 中有且仅有一个元素与a 对应，而关系没有这个限制. 二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同. 函数的类型单射若)()(2121afafaa满射f(A)= B. 即)(,xfyAxBy使得双射单射且满射 . 复合函数,:,:,:CAgfCBgBAf则即)()

12、(xfgxgf. 复合成立的条件是：)(Dom)(Rangf一般fggf，但)()(hgfhgf复合函数的性质：如果 f,g 都是单射的，则f g 是单射的；如果 f,g 都是满射的，则f g 是满射的；如果 f,g 都是双射的，则f g 是双射的；如果 f,g 是单射的，则f 是单射的；如果 f,g 是满射的，则g 是满射的；如果 f ,g 是双射的，则f 是单射的， g 是满射的 . 反函数若 f：AB 是双射，则有反函数f1：BA,)(,1AabafBbabf，fffggf11111)(,)(二、实例例 4.1 设集合 Aa,b, R是 P(A)上的包含关系，写出R 的表达式和关系矩阵.

13、 解 用描述法表示；)(,yxAPyxyxR用列举法表示：因为, ,)(AbaAP，所以精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 27 页学习必备欢迎下载, , ,AAAbbbAaaaAbaR关系矩阵：1000110010101111RM，关系图如图41 例 4.2 设 A1,2,3, 用列举法给出A 上的恒等关系IA，全关系EA，A 上的小于关系,yxAyxyxLA及其逆关系和关系矩阵. 解3 ,3,2,2,1 ,1AIAAIE ,2, 3,1 , 3,3, 2,1 ,2,3, 1,2, 13 ,2,3 , 1,2, 1AL,

14、LA的逆关系2, 3,1 , 3,1, 21AL000100110ALM0110010001ALM. 有TLLAAMM1例 4.3 设集合 A2,3,4, B=4,6,7, C=8,9,12,14 . R1是由 A 到 B 的二元关系， R2是由 B到 C 的二元关系，定义如下：,1baabaR整除是素数且,2cbcbR整除求复合关系21RR，并用关系矩阵表示. 解6 , 3,6, 2,4, 21R,14, 7,12,6,12,4,8 , 42R因此21RR, 0000100114327641RM1000010001017641412982RMab A图 41 精选学习资料 - - - - -

15、 - - - - 名师归纳总结 - - - - - - -第 7 页，共 27 页学习必备欢迎下载21RRRMMM000010011100001000101(布尔运算 )000001000101432141298例 4.4 试判断图42中关系的性质：1 1 1 2 3 2 3 2 3 (a) (b) (c) 图 42 例 4.4 图解图 42 中(a)的关系在集合 1,2,3 上是对称的，因为结点1 与 2， 1 与 3 之间的有向弧是成对出现且方向相反.图 42 中(b)是反自反的，因为每个结点都没有自回路. 它也是反对称的，因为两条边都是单向边，它又是传递的，容易求出R, 满足 R R=R

16、. 图 42 中(c)的关系自反的，反对称的、但不是传递的. 因为 2 到 1 有边， 1 到 3 有边，但 2 到 3 没有边 . 例 4.5 设集合 A1,2,3,4,5, R 是 A 上的关系，定义为R ,IA试判断 R 是(1) A 上的自反关系；(2) A 上的对称关系；(3) A 上的反对称关系；(4) A 上的传递关系 . 解 写出关系矩阵MR，作关系图，如图43. 1000011000111001111011111RM, (1) (1) 因为RxxAx),(,(或 MR的主对角线元素皆为1，或关系图中每个结点都有自回路)，故 R 是自反关系 . (2) 因为RR) 1 , 2(

17、,)2 , 1 (而(或 MR不是对称矩阵，或关系图中每对结点都没有成对出15 2 3 4 图 43 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 27 页学习必备欢迎下载现的方向相反的弧)，故 R 不是对称关系. (3) 因为RR) 1 , 3(,31,)3 , 1 (则且(或 MR中当 i j 时 , mij=0, 则 mji=1，或关系图中每对结点没有成对的有向弧)，故 R 是反对称关系 . (4) 因 为 不 难 验 证RcaRcbRbaAcba),(,),( ,),( ,有( 或 关 系 图 中就有有向弧到有有向弧到有有向弧

18、到cacbbaAcba,), 故 R 是传递关系 . 例 4.6 设集合 Aa,b,c,d,定义 R , 求 r(R),s(R),t(R). 解 求自反闭包，R 不具有自反性，由自反性的定义，只需在R 上添加 IA，于是r(R)=RIA=,， 其中下画线者为添加元素. s(R)=1RR=R,= , t(R)=432RRRR=R, =, , 例 4.7 设集合 Aa,b,c,d,e ，定义 A 上的二元关系AIdeedabbaR,1,2edddccbbabbaR判断 R1，R2是否为等价关系？分析 判断等价关系，就是验证是否具有自反性、对称性和传递性. 解 写出 R1的关系矩阵，11000110

19、000010000011000111RM图 44 由关系矩阵可知，R1具有自反性和对称性. 由关系图 (图 44)可知它具有传递性，故R1是等价关系 . R2不是等价关系，因为),(),(22ReeRaa或，故 R 不具有自反性 . abecd精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 27 页学习必备欢迎下载注意：自反性，对称性和传递性之一不具备，就是破坏了等价关系的定义. 事实上22,RdeRed但，故 R2不具有对称性；2,Rab，2,Raa但，R2也不具有传递性. 对例 4.7 的 R1进行分类：元素a，因为bbabbaaa

20、,均属于 R1，所以 a生成的等价类,1baaR或记作1Rb. 元素 c，因为1,Rcc，所以 c 生成的等价类1ccR; 类似地，d 生成的等价类,1eddR1Re. 例 4.8 设集合 A18 的正整数因子 ， 为整除关系，说明是偏序关系 . 分析 偏序关系只需验证自反性、反对称性和传递性.解 集合 A1,2,3,6,9,18 ，整除关系为IA, , , 容易验证IA，故有自反性；(a,b), a b, 则(b,a)，有反对称性；x,y,z A, 且,则，具有传递性 . 所以 是偏序关系 . 画的关系图和哈斯图如图45(a)和(b)：(关系图与哈斯图不是一回事) 18 18 1 9 6 9

21、 2 6 2 3 3 1 (a) 的关系图(b) 的哈斯图图 45 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 27 页学习必备欢迎下载的最大元是18，极大元是18，最小元、极小元均为1. 若子集 B1 2,3,6 ，则 B1最大元和极大元都是6，无极小元 . 上界为 6，18; 下界为 1，上确界为6，下确界为1. 若子集 B2 3,6,9, 则 B2无最大元，极大元为6,9，最小元和极小元都是3, 上界为 18，下界为 3,1，上确界为18，下确界为3. 若子集 B3=1,2,3, 则极大元 2,3, 无最大元 .极小元和最小

22、元均为1. 上界 18,6, 上确界是 6，而不能是9. 下界和下确界为1. 例 4.9确定以下各题的f 是否为从 A 到 B 的函数，并对其中的函数f：AB 指出它是单射，满射或双射？如果不是，请说明理由. (1)9 ,5,6,2,10,4,9 , 3,8 , 1,10,9, 8,7, 6,5 ,4 ,3,2, 1fBA; (2) A,B 同(1), f=,; (3) A,B 同(1), f=,; (4) A,B 为实数集，xxxf2)(; (5) A,B 同(4)，3)(xxf; (6) A,B 同(4)，xxf)(; (7) A,B 同(4)，xxf1)(; (8) A,B 为正整数集，

23、1)(xxf; (9) A,B 同(8)，1111)(xxxxf; (10) A,B 为正实数集，1)(2xxxf. 解(1) f 是从 A 到 B 函数， 但不是单射， 因为 f(3)=f(5)=9；也不是满射， 因为 7Ran(f). (2) f 不是从 A 到 B 函数，因为Dom(f)=1,2,3,4A. (3) f 不是从 A 到 B 函数，因为1 Dom(f), f(1)=7 和 9. (4) f 是从 A 到 B 函数，但不是单射，因为f(0)=f(1)=0 ；也不是满射，因为该函数的最小值是 1/4，所以 Ran(f)是), 4/1，不是整个实数集. (5) f 是从 A 到

24、B 的双射函数，因为3xf是严格单调，且RRff)(:. (6)(6) f 不是从 A 到 B 函数，因为因为负实数没有定义. (7)(7) f 不是从 A 到 B 函数，因为0没有对应值 . (8)(8) f 是从 A 到 B 函数，且f 是单射，因为易验证11,212121nnnnNnn精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 27 页学习必备欢迎下载但 f 不是满射，因为1 Ran(f). (9) f 是从 A 到 B 函数，且f 是满射，因为), 0), 1(),0)(Ran), 1)(Domfff，且是是但不是单射，因

25、为f(1)=f(2)=1. (10)f 是从 A 到 B 函数，但f 不是单射，如x0, f(x)=f(x1). 当 x=1 时 ，f(1)=1/2 是极大值， Ran(f)是(0,1/2)，不是整个正实数集，故f 不是满射 . 例 4.10图 46 中，定义了函数f,g,h1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 f gh 图 46 求： (1) f,g,h 的像 ; (2) f g, h f, g g; (3) 指出 f,g,h 中哪些是单射，满射和双射(4) f,g,h 中哪些函数存在反函数，给出其反函数的表达式. 解(1) f(A)

26、=1,2,4, g(A)=A, h(A)=1,3 (2) f g=, h f=, g g=, (3) 只有 g 是单射，又是满射，即为双射. (4) 只有 g 有反函数g1：AA，且满足 , g1, 例 4.11 单项选择题1.设集合 A1,2 ，B= a,b,c,C= c,d, 则 A(BC)( ) (A), (B) , (C), (D), 答案 ：(B) 解答 ：,2, 1)(,ccCBAcCB，故选择 (B). 2. 设 A0, a,B=1, a,3, 则 AB 的恒等关系是( ) (A) , (B) , (C) , (D) , 精选学习资料 - - - - - - - - - 名师归纳

27、总结 - - - - - - -第 12 页，共 27 页学习必备欢迎下载答案 ：(A) 解答 ：因为 AB0,1,3, a,故 AB 的恒等关系IAB, 应该选择(A) . 3. 设集合 Aa,b,c,A 上的二元关系R, 不具备关系 ( )性质 . (A) 传递性(B) 反对称性(C) 对称性(D) 自反性答案 ：(D) 解答 ：只有每个结点都有自回路，才具有自反性，R 缺少 . 故应选 (D) . 4. 设集合,3214321bbbBaaaaA是从 A 到 B 的函数，,21ba,341322bababa，则是( ) (A) 双射(B) 满射但不是单射(C) 单射但不是满射(D) 非单射

28、也非满射答案 ：(B) 解答 ：因为(A)=B,故是满射，但是(a1)= (a2)=b2,故不是单射 . 所以应选 (B). 例 12 填空题1. 设 R1，R2是集合 A 1,2,3,4 上的二元关系 ,其中R1, R2=, 则 R1R2答案 ：, 解答 ：由合成的定义：,3 ,1,321 ,4, 1,4112121RRRR2142RR4, 1,3 , 121RR3. 设21,RRdcbaA是 A 上的二元关系，,21ddbccbbbaaRddcbbbaaR则 R2是 R1的闭包答案 ：对称解答 ：在 R1的基础上添加,此时关系矩阵是对称矩阵，故R2是 R1的对称闭包三、练习题1. 设 A1

29、,2,3,4, R 是 A 上的二元关系，其关系矩阵为精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 27 页学习必备欢迎下载0001100000011001RM试求(1) R 的关系表达式；(2) Dom( R)和 Ran(R)；(3) R R 中有多少个有序对(4) R1的关系图中有多少条自回路? 2. 设集合 A1,2,3,4, A 上的二元关系R1, R2, R3, 求213113221,;,RRRRRRRRR3. 设集合,dcbaA判定下列关系，哪些是自反的，对称的，反对称的，传递的？,54321dbcaRccbbaaRdc

30、RadcbaaRabaaR4. 设 A1,2,3,4,5,6, 定义 A 上的二元关系R, , (1) 判定 R 是否为等价关系？(2) 若是等价关系，写出A 的关于 R 的等价类 . 5. 设 A1,2,3,4,5, R 是 A 上的二元关系R, (1) 试写出 R 的关系矩阵和关系图；(2) 证明 R 是 A 上的偏序关系，并画出哈斯图；(3) 若 BA，且 B2,3,4,5, 求 B 的最大元，最小元，极大元极小元最小上界和最大下界. 6. 设 R，Z，N 分别表示实数、整数和自然数集，定义函数f1,f2,f3,f4, 试确定它们的性质. )()5()1,()(,:3),3(mod)(,

31、:)(,:2)(,:44321fnnnfNNNfxxxfNNfxxfNZfxfRRfx的余数除四、练习题答案1.1. (1) , (2) 1,2,3,4, 1,4 (3) 7 个是 , (4) 1 个是 2. 21RR=, 32RR=, 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 27 页学习必备欢迎下载1 R=, 注意： R1是相对于全关系EA而言的 . 31RR, 21RR, 3. R1反对称的、传递的；R2反对称的、传递的；R3反自反的、反对称的、传递的；R4传递的； R5反自反的、反对称的、传递的. 4. (1) 是等价关

32、系；(2) 等价类分别为 2,3,6, (1,4), 5 5. (1) 1110001000011000001000001RM, 关系图如图47 (2) 不难验证 R 具有自反性；由关系图看出 R 具有传递性；由反对称性的等价定义，易知 R 具有反对称性，故R 是偏序关系 . 作的哈斯图 (图 48). (3) 当 B2,3,4,5 时， B 的极大元为2，4；极小元为2， 5；B 无最大元和最小元；B 无上界和下界 . 6. f1双射；f2满射不单射； f3不单射也不满射；f4单射不满射；f4(5)=(5,6) 一、重点内容1. 图的基本概念图是一个有序对，V 是结点集， E 是边集，当V

33、, E 有限时， 称为有限图；否则称无限图. 1 3 2 4 5 图 47 4 3 2 1 5 图 48 哈斯图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 27 页学习必备欢迎下载无向边 , 与无序结点 (v,u)相关联的边；有向边，与有序结点相关联的边 . 无向图，每条边都是无向边的图，记作G ; 每条边都是有向边的图，记作D. 混合图，既有有向边，也有无向边的图. 平凡图，仅有一个结点的图；零图，边集为空集的图，即仅有结点的图. 自回路 (环)，关联于同一个结点的边.无向平行边，联结相同两个结点的多于1 条的无向边；有向平行边

34、，联结两个结点之间的多于1 条且方向相同的有向边.简单图，不含平行边和自回路的图. 在无向图G中，与结点v(V)关联的边数，即为结点度数 deg(v)或 d(v).；在有向图中，结点v的出度和入度之和为度数. 在有向图D中，以 v(V)为起点的边之条数为出度 deg(v)；以 v(V)为终点的边之条数为 入度 deg(v).最大度数，(G)maxd(v) v V ；最小度数，(G)=min d(v) v V 有n 个 结 点 的 且 每 对 结 点 都 有 边 相 连 无 向 简 单 图 ， 无 向 完 全 图Kn. 此 时 有) 1(21nnE；有 n 个结点的且每对结点之间都有两条方向相反

35、的边相关连的有向简单图为有向完全图，.此时有)1(nnE设 G, V，E 的子集 V ,E 构成的图G =是图 G 的子图 ；若 GG 且 GG，(VV 或 EE)，G 是 G 的真子图 . 生成子图，设图 G, 若 EE, 则图 是的生成子图 . 即结点与原图G相同的子图，为生成子图. 补图G=，设 G, 以 V 为结点集，以使G 成为完全图所添加的边为边集E 的图，就是图G 的补图 G ,.，即 是完全图 , 其中 EE . 图的同构，设G1=和 G2=, 存在双射f：V1V2，(vi,vj)E1, 当且仅当(f(vi),f(vj)E2，且 (vi,vj)与 (f(vi),f(vj)的重数

36、相同 . 则 G1G2. 同构充分条件：建立两个图的对应关系，这个关系是双射函数. 同构必要条件：结点数相同；边数相同；度数相同的结点个数相同. 握手定理设 G=，有VvEv2)deg(, 在图 D中，VvVvvv)(deg)(deg精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 27 页学习必备欢迎下载握手定理推论：奇数度结点的个数为偶数个.度数序列 . 2 通路、回路、图的连通性通路与通路的长度，设图 G ，Vv0,v1, , vn,E= e1,e2, , em,结点与边的交替序列 v0e1v1e2vi1eivi,为结点 v0到结

37、点 vi的通路 . v0,vi是通路的起点和终点. 通路中边的数目就是通路的 长度 . 回路，起点和终点重合的通路. 边不重复的通路(回路 )称简单通路 (回路 )； 结点不重复的通路(回路 )， 称初级通路 (回路 )；边有重复的通路(回路 )，称 复杂通路 (回路 ). 连通与连通图，无向图G 中，结点u,v 存在通路，则u,v 是连通的， G 中任意结点u,v都是连通的，G 是连通图 . 连通分支P(G)， 设 G， V 的连通等价类V1， V2， , Vm,子图 G(V1),G(V2), , G(Vm)称为连通分支. 点割集与割点，设无向图G ，存在结点集VV，使得 P(GV )P(G

38、)，而任意 VV ，有 P（GV ）P(G)，VFT1 称为图 G 的点割集 . 若 V 是单元集 v ，v 叫做割点 . 边割集与割边，设无向图G ，存在边集EE，使得 P(GV )P(G)，而任意EE ，有 P （GE ）P(G)，EFT2 称为图 G 的边割集 . 若 E 是单元集 e，e 叫做割边 (桥). 注意：点割集和边割集的两个 条件 . 有向图的连通，有向图中，任意一对结点之间至少有一个结点可达另一结点是单侧连通；任何一对结点都相互可达是强连通；略去有向图D 边的方向成为无向连通图是弱连通.由定义可知：强连通必是单侧连通必是弱连通 . 3. 图的矩阵表示 (无向图 )关联矩阵设

39、 G=, mEnV,，关联矩阵M(G)=mnijm,其中 mij=vi与 ej的关联次数 ( 行为结点，列为边) . 具有性质：21miijm( 列元素之和为2) ；)deg(1imjijvm, 若01mjijm, 表明 vi是孤立点 ; mmnimjij211, 即所有元素之和等于边数的2 倍;平行边的列的元素完全对应相同. (无向图 )相邻矩阵设 G, mEnV,，相邻矩阵A(G)=nija，其中 aij=vi与 vj相关联的边的条数( 行、列均为结点). 具有性质 :精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 27 页学习必

40、备欢迎下载 A( G) 是对称矩阵；)deg()(11iniijmjijvaa；01mjija若，表明 vi是孤立点 ; (有向图 )关联矩阵设 D, mEnV,，关联矩阵M(D)=mnijm，其中为始点，为终点不关联与为终点为始点jijijiijvvvvvvm10,1(结点为行，边为列). 具有性质：01niijm( 列元素之和为 0 ； )deg(1imjijvm; mmmnimjijnimjij1111)1()1( ( 有向图 ) 邻接矩阵设 D=, mEnV,，邻接矩阵A(D)=nija,其中 aij=邻接 vi与 vj的边的条数( 与 A( G) 类似 )(以行和列均为结点)具有性质

41、：manimjij11 (有向图 )可达矩阵设 D=，mEnV,，可达矩阵P(D)=nijp，其中否则可达01jiijvvpEDADADAEDBDPnn)(.)()()()(121二、实例例 5.1 设 G(V,E)是一个无向图，,.,821vvvV),(),(),(),(),(),(),(87434551133221vvvvvvvvvvvvvvE(1) G的V ，E 各是多少？(2) 画出 G 的图解；(3) 指出与 v3邻接的结点，以及与v3关联的边；(4) 指出与 e1关联的结点；(5) 该图是否有孤立结点和孤立边？(6) 求出各结点的度数；解(1) G=中，有V =8 个结点，E=7

42、条边的图，故又称是8 阶图 .(2) 所给图 G 的一个图解，如图51. (3) 结点 v1, v2, v4与 v3邻接， v3关联v2e4 e1v1e2v3v7e7 v6e5精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 27 页学习必备欢迎下载的边为 e1, e2, e3.(4)与边 e1关联的结点为v2, v3.(5) 结点 v6是孤立点； e5是孤立边 . (6) deg(v1)=3，deg(v2)=2， deg(v3)=3，deg(v4)=2deg(v5)，deg(v6)=0，deg(v7)=1=deg(v8). 例 5.2

43、 设图 G 是具有 3 个结点的完全图，试问(1) G 有多少个子图？(2) G 有多少个生成子图？(3) 如果没有任何两个子图是同构的，则G 的子图个数是多少？将它们构造出来. 解 (1) 因为只有1 个结点的子图有313个 (平凡子图 )；2 个结点的子图有6223个；3 个结点的子图有82338个；所以， G 共有 368 17 个子图 . (2) G 的生成子图，含有G 的所有结点， G 有 3 条边，构成子图时，每条边有选中或不选中两种可能，所以G 的生成子图的个数是23 8 个 . (3) G 的所有不同构的子图有7 个，如图5 2所示 . 例 5.3 给定图 G=,如图 53，(

44、1)(1)在 G 中找出一条长度为7 的通路；(2) 在 G 中找出一条长度为4 的简单通路 ; (3)在 G 中找出一条长度为5 的初级通路 ; (4) 在 G 中找出一条长度为8 的复杂通路 ; (5)在 G 中找出一条长度为7 的回路；(6) 在 G 中找出一条长度为4 的简单回路 ; (7) 在 G 中找出一条长度为5 的初级回路解 所选通 (回)路都不一定是唯一的. G1 G2G3 G4G5G6 G7图 52 v1v4 v5v8v3 v2v7 v6图 53 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 27 页学习必备欢迎

45、下载(1) 长度为 7 的通路： v1 v4 v3 v7 v8 v6v5v2(2) 长度为 4 的简单通路：(v1, v4),( v4, v3),( v3,v7),( v7, v4) (边不重复的通路) (3) 长度为 5 的初级通路：v1 v5 v2 v6 v8 v4(结点不重复的通路) (4) 长度为 8 的复杂通路：(v1, v5),( v5, v8),( v8, v7),( v7, v6),( v6, v8), ( v8, v5),( v5, v4),( v4, v3)(边有重复的通路) (5) 长度为 7 的回路： v1 v4 v3 v7 v8 v6v5v1(6)长度为 4 的简单回

46、路：( v1, v4),( v4, v8),( v8,v5),( v5, v1)(边不重复的通路) (7)长度为 5 的初级回路： v1 v5 v6 v7 v4 v1(除起点和终点外，结点不重复的通路) 例 5.4 设图 54，V= a,b,c,d,e G1,E1=( a,b）,(b,c),(c,d),(a,e); G2 ,E2=( a,b),(b,e),(e,b),(a,e),(d,e); G3,E3=( a,b),(b,e),(e,d),(c,c);G4,E4=,; G5,E5=,; G6,E6=,. 试问：(1) 哪些图是有向图？哪些图是无向图？(2) 哪些是简单图？(3) 哪些是强连通

47、图？哪些是单侧连通图？哪些是弱连通图？解 (1) G1, G2, G3是无向图； G4, G5, G6是有向图 . (2) G1, G4, G5中既无平行边，也无自回路，是简单图. (3) G5是强连通图 (必是单侧连通图和弱连通图)；G4是单侧连通图 (为什么？ )(也是弱连通图)；G6只是弱连通图. 例 5.5 求例 5.4 中图 (1)G2的关联矩阵，(2)图 G3的相邻矩阵，(3)图 G5的关联矩阵、(4)图 G5邻接矩阵以及从b 到 c,d 长度为 3 的通路条数，从b 到 b 长度为 2 的回路的条数以及长度为 3 的通路共有多少条，长度不超过3 的通路条数和回路的条数；(5)图

48、G5的可达矩阵 . 解 (1)已知图 G2的结点集V2= a,b,c,d,e, 边集E2=( a,b),(b,e),(e,b),(a,e),(d,e),54321eeeee，n=5,m=5. G2是无向图，由关联矩阵的定义，mnijmGM)(2，其中 mij=vi与 ej关联的次数 .于是有aaaaaabe be b e beb e b ecdcdc dcd cd cd(G1) (G2) (G3) (G4) (G5) (G6) 图 54 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 27 页学习必备欢迎下载1100011100000

49、000001111001)(254321edcbaGMeeeee(2) 因为 G3为 V3= a,b,c,d,e, E3=( a,b),(b,e),(e,d),(c,c) ，是无向图，由相邻矩阵的定义，nijaGA)(3，其中 aij=vi与 vj关联的边的次数. n=5,故相邻矩阵为0101010000002001000100010)(3edcbaGAedcba(3) 有向图 G5，V5= a,b,c,d,e, E5=, ，由关联矩阵的定义nijmGM)(5，其中当vi为 ej的始点时， mij=1；当 vi为 ej的终点时， mij= 1；当 vI与 ej不关联时， mij=0. 于是所求

50、关联矩阵为100011000011000011000011100011)(5654321edcbaGMeeeeee(4) 图 G5的邻接矩阵为A(G5)=0000110000010000010100010. A2(G5)=0001000001100000101000101，A3(G5)=0010100010000011010101010从 A3(G5)可知，从结点b 到结点 c,d 各有 1 条、 0 条长度为3 的通路 . 从 b 到 b 长度为 2 的回路有 1 条；长度为3 的通路共5151)3(ijija=9 条；长度不超过3 的通路共有22 条，其中回路是2 条. 精选学习资料 -