文档介绍：传输闭包、 即在数学中, 在集合 X 上二元关系 R 传输闭包是包含 R X 上最小传输关系。
比如, 假如 X 是(生或死)人集合而 R 是关系“为父子”, 则 R 传输闭包是关系“x 是 y 祖先”。 再比如, 假如 X 是空港集合而关系 xRy 为“从空港 x 到空港 y 有直航”, 则 R 传输闭包是“可能经一次或数次航行从 x 飞到 y”。
存在性和描述
对于任何关系 R, R 传输闭包总是存在。 传输关系任何家族交集也是传输。 深入, 最少存在一个包含 R 传输关系, 也就是平凡: X × X。 R 传输闭包给出自包含 R 全部传输关系交集。
我们能够用更具体术语来描述 R 传输闭包以下。 定义在 X 上一个关系 T, 称 xTy 当且仅当存在有限元素(xi)序列, 使得 x = x0 而且
x0Rx1, x1Rx2, …, xn−1Rxn 和 xnRy
形式上写为
轻易检验出关系 T 是传输而且包含 R。 深入, 任何包含 R 传输关系也包含 T, 所以 T 是 R 传输闭包。
证实 T 是包含 R 最小传输关系
设 A 是任何元素集合。
假定: GA 传输关系 RAGA TAGA。 所以 (a,b)GA(a,b)TA. 所以, 特定 (a,b)RA。
现在经过 T 定义, 我们知道了 n (a,b)RnA。 接着, i, in eiA。 所以, 有从 a 到 b 路径以下: aRAe1RA...RAe(n-1)RAb。
不过, 经过 GA 在 RA 上传输性, i, in (a,ei)GA, 所以, (a,e(n-1))GA (e(n-1),b)GA, 所以经过 GA 传输性, 我们得到了 (a,b)GA。 矛盾于 (a,b)GA。
所以, (a,b)AA, (a,b)TA (a,b)GA。 这意味着 TG, 对于任何包含 R 传输 G。 所以, T 是包含 R 最小传输闭包。
推论
假如 R 是传输, 则 R = T。
用途
注意两个传输关系并集无须须是传输。 为了保持传输性, 必需采取传输闭包。 比如, 这出现在取两个等价关系或预序并时候。 为了取得新等价关系或预序, 必需选择传输闭包(自反性和对称性 — 在等价关系情况下 — 是自动)。
有向无环图(DAG)传输闭包是 DAG 可抵达性关系和一个严格偏序。
和复杂性关系
在计算复杂性理论中, 复杂度类 NL 严格对应于可使用一阶逻辑和传输闭包表示逻辑句子集合。 这是因为传输闭包性质有亲密关系于 NL-完全问题 STCON, 找到在一个图中有向路径。 类似, 类 L 是一阶逻辑带有交换传输闭包。 在向二阶逻辑增加了传输闭包时候, 我们得到 PSPACE。
相关概念
关系 R 传输简约是有 R 作为它传输闭包最小关系。 通常说它不是唯一。
Warshall传输闭包算法学****和实现
1、 问题引入
一个有n个顶点有向图传输闭包为: 有向图中初始路径可达情况能够参见其邻接矩阵A, 邻接矩阵中A[i,j]表示i到j是否直接可达, 若直接可达, 则A[i,j]记为1, 不然记为0; 两个有向图中i到j有路径表示从i点开始经过其它点（或不经过其它点）能够抵达j点, 假如i到j有路径, 则将T[i