387
个编辑
更改
→数学性质
== Mathematical properties ==
== Mathematical properties ==
数学性质
=== Reachability, transitive closure, and transitive reduction ===
=== Reachability, transitive closure, and transitive reduction ===
可达性，传递闭包和传递归约
{{multiple image|image1=Tred-G.svg
{{multiple image|image1=Tred-G.svg
|width1=175|image2=Tred-Gprime.svg|width2=124|caption1=A DAG {{mvar|G}}|caption2=Transitive reduction of {{mvar|G}}}}
|width1=175|image2=Tred-Gprime.svg|width2=124|caption1=A DAG {{mvar|G}}|caption2=Transitive reduction of {{mvar|G}}}}
A [[multitree]] (also called a strongly unambiguous graph or a mangrove) is a directed graph in which there is at most one directed path (in either direction) between any two vertices; equivalently, it is a DAG in which, for every vertex {{mvar|v}}, the subgraph reachable from {{mvar|v}} forms a tree.<ref>{{citation | last1 = Furnas | first1 = George W. | author1-link = George Furnas | last2 = Zacks | first2 = Jeff | contribution = Multitrees: enriching and reusing hierarchical structure | doi = 10.1145/191666.191778 | pages = 330–336 | title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94) | year = 1994| isbn = 978-0897916509 | s2cid = 18710118 }}.</ref>
A [[multitree]] (also called a strongly unambiguous graph or a mangrove) is a directed graph in which there is at most one directed path (in either direction) between any two vertices; equivalently, it is a DAG in which, for every vertex {{mvar|v}}, the subgraph reachable from {{mvar|v}} forms a tree.<ref>{{citation | last1 = Furnas | first1 = George W. | author1-link = George Furnas | last2 = Zacks | first2 = Jeff | contribution = Multitrees: enriching and reusing hierarchical structure | doi = 10.1145/191666.191778 | pages = 330–336 | title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94) | year = 1994| isbn = 978-0897916509 | s2cid = 18710118 }}.</ref>
== Computational problems ==
== Computational problems ==