For faster navigation, this Iframe is preloading the Wikiwand page for 传递闭包.

传递闭包

维基百科,自由的百科全书


此条目翻译品质不佳。 (2017年4月14日)翻译者可能不熟悉中文或原文语言,也可能使用了机器翻译。请协助翻译本条目或重新编写,并注意避免翻译腔的问题。明显拙劣的翻译请改挂((d|G13))提交删除。

数学中,集合X上的二元关系 R传递闭包是包含RX上的最小的递移关系

例如,如果 X 是由人组成的集合(不论人活着与否)而R是关系“为父子”,则 R 的传递闭包是关系“xy 的祖先”。再比如,如果 X 是空港的集合而关系 xRy 为“从空港 x 到空港 y 有直航”,则 R 的传递闭包是“可能经一次或多次航行从 x 飞到 y”。

存在性和描述

对于任何关系 RR 的传递闭包总是存在的。传递关系的任何家族的交集也是传递的。进一步地,至少存在一个包含 R 的传递关系,也就是平凡的: X × XR 传递闭包给出自包含 R 的所有传递关系的交集。

我们可以用更具体术语来描述 R 的传递闭包如下。定义在 X 上的一个关系 T,称 xTy 当且仅当存在有限的元素(xi)序列,使得 x = x0 并且

x0Rx1, x1Rx2, …, xn−1RxnxnRy

形式上写为

容易检查出关系 T 是传递的并且包含 R。进一步地,任何包含 R 的传递关系也包含 T,所以 TR 的传递闭包。

证实 T 是包含 R 的最小传递关系

A 是任何元素的集合。

假定: GA 传递关系 RAGA TAGA。所以 (a,b)GA(a,b)TA. 所以,特定的 (a,b)RA

现在通过 T 的定义,我们知道了 n (a,b)RnA。接着,i, in eiA。所以,有从 ab 路径如下: aRAe1RA...RAe(n-1)RAb

但是,通过 GARA 上的传递性,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 作为它的传递闭包的最小关系。一般来说它不唯一。

算法

计算图的传递闭包的有效算法可见于 here页面存档备份,存于互联网档案馆)。最简单的技术是Floyd-Warshall算法

引用

  • Lidl, R. and Pilz, G., 1998, Applied abstract algebra, 2nd edition, Undergraduate Texts in Mathematics, Springer, ISBN 0-387-98290-6

外部链接

{{bottomLinkPreText}} {{bottomLinkText}}
传递闭包
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.