Induction and recursion
Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
大数据科学系/大连东软信息学院
Copyright By PowCoder代写 加微信 powcoder
Section 5.4
计算一对顶点之间的最短路径
判断任意两个顶点之间是否有路
设R 是A上的关系，R 可能具有某种性质P。
如果存在包含R 的具有性质P 的关系S，并且S 是所有包含R 且具有性质P 的关系的子集，那么S 叫作R 的关于性质P 的闭包。
注意，一个关系的具有某种性质的闭包不一定存在。
例：集合A={1，2，3}上的关系R={（1，1），（1，2），（2，1），（3，2）}不是自反的。
求一个包含关系R的尽可能小的自反关系？
把（2，2）和（3，3）加入到R 中。
∴R的自反闭包={(1，1)，(1，2)，(2，1)， (2，2），(3，2)， (3，3)}
∀x[x ∊A ⟶ (x, x) ∊ R]
定义：给定集合A上的关系R，对于R，可以通过把不在R中的所有形如（x, x）的有序对，加到关系R中，得到关系的自反闭包。
R的自反闭包 = R∪△，其中△={（x, x）|x ∈A}
定义：给定集合A上的关系R，对于xRy，可以通过增加所有形如（y，x）的有序对到关系R中，得到关系的对称闭包。
（x，y） ∈R，且 （y，x） ∉ R
R∪ R -1 是R的对称闭包
∀x∀y [(x,y) ∊R ⟶ (y,x) ∊ R]
传递闭包？怎么构建？
集合{1，2，3，4}上的关系 R={（1,3），（1,4），（2,1），（3,2）}
能否增加（1，2）、（2，3）、（2，4）以及（3，1）？
在有向图G中，从a到b的一条路径是图G中一条或多条边的序列，其中一条边的终点是下一跳边的始点。
即，存在一个元素的序列a,x1,x2,…,xn-1,b，且(a, x1) ∈R, (x1, x2) ∈R,…, (xn-1,b) ∈R，那么在R中存在一条从a到b的路径。
定理1：设R是集合A上关系。从a到b存在一条长为n的路径，当且仅当(a,b) ∈Rn。
序对 (x,y) 在关系 Rn 中，如果有长度为 n 的路径从 x 到 y 属于 R (跟随箭头的方向)。
寻找一个关系的传递闭包等价于在相关的有向图中确定哪些顶点对之间存在路径。
例1：设A = {a, b, c, d}，A上的关系 R = {(a, b), (b, a), (b, c), (c, d)}
定义：设R是集合A上的关系，连通性关系R*由形如(a,b)的有序对构成，使得在关系R中，从a到b之间存在一条长度至少为1的路径。
定理：关系R的传递闭包等于连通性关系R*。
例： 设A={a,b,c,d}, R是A上的二元关系，R ={(a,b),(b,a),(b,c),(c,d), (d,b)}分别求自反闭包、对称闭包和传递闭包。
设A={a,b,c,d}, R={(a,b),(b,a),(b,c),(c,d), (d,b)}
关系的传递闭包的求法
A={a,b,c}, R={(a,b),(b,c),(c,a)}
序对 (x,y) 在关系 Rn 中，如果有长度为 n 的路径从 x 到 y 属于 R (跟随箭头的方向)。
关系的传递闭包的求法
Warshall算法
思想：构造一些列的0-1矩阵，W0，W1，…，Wn，其中W0=MR 是这个关系的0-1矩阵，且Wk=[wij(k)]。如果存在一条从vi到vj的路径使得这条路径的所有内部顶点都在集合{v1,v2,…，vk}中，那么wij(k)=1，否则为0。
关系的传递闭包的求法
Warshall算法
分别考察a、b、c、d作为内部顶点的路径，则
W4就是传递闭包的矩阵
画出给定有向图所示关系的自反闭包和对称闭包的有向图。
设R是集合{0,1,2,3}上的关系，R={(0,1),(1,1),(1,2),(2,0),(2,2),(3,0)}
求：R的自反闭包，R的对称闭包，R的传递闭包
设R的关系图如下图所示，给出R的自反闭包、对称闭包和传递闭包的关系图。
求出下列{1,2,3,4}上关系的传递闭包。
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com