离散数学课件--.ppt

一、关系的闭包 定义：给定 A中关系R,若A上另一个关系R′， 满足：⑴R?R′； ⑵R′是自反的(对称的、传递的)； ⑶R′是“最小的”，即对于任何A上自反(对称、传递)的 关系R″,如果R?R″,就有R′?R″。 则称R′是R的自反(对称、传递)闭包。 记作r(R)、s(R)、t(R))(reflexive、symmetric、transitive) 2.计算方法 1.给定 A中关系R,则 r(R)=R∪IA。 proof：令R‘ =R∪IA,显然R’是自反的和R? R‘ ，下面证明R’是“最小的”：如果有A上自反关系R“且R? R”,又IA? R“,所以 R∪IA? R”,即R‘ ? R“ 。所以R’就是R的自反闭包。 即r(R)=R∪IA 。 2.给定 A中关系R,则 s(R)=R∪RC 。 证明方法与1类似。 【example】正整数集合上的关系R={(a,b)|ab}的对称闭包是 多少？ Solution： R的对称闭包是关系 R ∪RC ={(a,b)|ab} ∪ {(b,a)|ab} ={(a,b)|a≠b} 二、有向图的路径 使用有向图表示关系有助于构造关系的传递闭包 。为此引入 一些需要用到的术语。 通过沿有向图的边(按照这条边的箭头指示的相同方向)移动有 向图就得到一条有向图中的路径。 定义1：在有向图G中从a到b的一条路径是G中一条或多条 边的序列(x0,x1),(x1, x2),(x2, x3),…,(xn-1, xn),其中 x0=a, xn=b. 即一个边的序列，其中一天的终点和路径中下一条边 的起点相同。这条路径记为x0, x1,…, xn-1, xn,长度为n 。在同一定点开始和结束的路径叫做回路或圈。 注：有向图的一条路径可以多次通过一个顶点。此外，有 向图的一条边也可以多次出现在一条路径中。 【example】下面哪些路径是图9的有向图中的路径： a，b，e，d； a，e，c，d，b； b，a，c，b，a，a，b； d，c； c，b，a； e，b，a，b，a，b，e 这些路径的长度是多少？这个列表中的哪些路径是回路？ Solution： 因为(a，b)、(b，e)和(e，d)都是边，a,b,e,d是长为3的路径 因为(c，d)不是边，a,e,c,d,b不是路径。 因为(b，a)，(a，c)，(c,b)，(b,a)，(a,a)和(a,b)都是边，b ，a，c，b，a，a，b是长为6的路径。 我们也看到，因为(d,c)是边，d,c是长为1的路径。 还有由于(c,b)和(b,a)是边，c,b,a是长为2的路径。 (e,b)，(b，a)，(a，b)，(b，a)，(a，b)，(b，e)都是边 ，因此e，b，a，b，a，b，e是长为6的路径。 两条路径b，a，c，b，a，a，b和e，b，a，b，a，b，e 是回路，因为它们在同一顶点开始和结束。 路径a，b，e，d；c，b，a；d，c不是回路 把有向图的定义推广到关系可知，如果存在一个元素的 序列 a,x1,x2,…,xn-1,b 具有(a,x1)∈R, (x1,x2)∈R,…, (xn-1,xn)∈R, 那么在R中存在一条从a到b的路径。 从关系中的路径定义可以得到定理1。 定理1：设R是集合A上的关系。从a到b存在一条长为1的路径， 当且仅当（a，b）∈Rn。 Proof： 使用数学归纳法证明。 根据定义，从a到b存在一条长为1的路径，当且仅当 （a，b）∈R。因此当n=1时定理为真。 假定对于正整数n定理为真，这是归纳假设。从a到b存 在一条长为n+1的路径，当且仅当存在元素c ∈A使得从a 到c存在一条长为1的路径，即(a,c) ∈R,以及一条从c到b 的长为n的路径，即(c,b) ∈Rn. 因此由归纳假设，从a到b存在一条长为n+1的路径，当 且仅当存在一个元素c，使得(a,c) ∈R和(c,b) ∈Rn。但是 存在这样一个元素，当且仅当(a,b) ∈Rn+1。 因此，从a到b存在一条长为n+1的路径，当且仅当 (a,b) ∈Rn+1。定理得证。 三、传递闭包 定义2：设R是集合A上的关系。连通性关系R*由对(a,b)构成 ，使得在R中从顶点a到b之间存在一条至少长为1的路径。 因为Rn由对(a,b)构成，使得存在一条从a到b的长度为n的 路径，从而R*是所有集合Rn的并