更改

<font color="#ff8000"> 埃里克·韦斯坦因 Eric W. Weisstein</font>推测[13]，n个顶点的标号有向无环图的数量与其中所有特征值都为正实数的n*n逻辑矩阵的数量相同。这一点随后被<font color="#ff8000"> McKay</font> et al. (2004) 证实，证明采用了<font color="#ff8000"> 双射法Bijective</font>：一个矩阵A是有向无环图的一个<font color="#ff8000"> 邻接矩阵Adjacency matrix</font>，当且仅当A + I 是一个所有特征值都为正数的逻辑矩阵，其中I 为<font color="#ff8000"> 单位矩阵 Identity matrix</font>。因为一个有向无环图不允许<font color="#ff8000"> 自环Self-loops</font>，它的邻接矩阵的对角线必定全为0。因此，加上I 保持了所有矩阵因子都是0或1的特性。[13]

<font color="#ff8000"> 埃里克·韦斯坦因 Eric W. Weisstein</font>推测[13]，n个顶点的标号有向无环图的数量与其中所有特征值都为正实数的n*n逻辑矩阵的数量相同。这一点随后被<font color="#ff8000"> McKay</font> et al. (2004) 证实，证明采用了<font color="#ff8000"> 双射法Bijective</font>：一个矩阵A是有向无环图的一个<font color="#ff8000"> 邻接矩阵Adjacency matrix</font>，当且仅当A + I 是一个所有特征值都为正数的逻辑矩阵，其中I 为<font color="#ff8000"> 单位矩阵 Identity matrix</font>。因为一个有向无环图不允许<font color="#ff8000"> 自环Self-loops</font>，它的邻接矩阵的对角线必定全为0。因此，加上I 保持了所有矩阵因子都是0或1的特性。[13]

=== Related families of graphs ===

=== Related families of graphs 相关概念 ===

{{multiple image

{{multiple image

|image1=Polytree.svg|caption1=A [[polytree]], a DAG formed by [[Orientation (graph theory)|orienting]] the edges of an undirected tree 一个多树，一个 DAG，其中每个从单个顶点(红色)可到达的子图是一棵树

|image1=Polytree.svg|caption1=A [[polytree]], a DAG formed by [[Orientation (graph theory)|orienting]] the edges of an undirected tree  

|image2=Butterfly multitree.svg|caption2=A [[multitree]], A DAG in which each subgraph reachable from a single vertex (red) is a tree 一个多边形是一个有向图形成的定向的边自由树。每棵多叶树都是一个 DAG。特别是，这是真正的树枝形成的所有边缘向外从树根。

|image2=Butterfly multitree.svg|caption2=A [[multitree]], A DAG in which each subgraph reachable from a single vertex (red) is a tree  

|width2=254<!---adjust to make both images the same height-->  

|width2=254<!---adjust to make both images the same height-->  

}}

}}

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 , the subgraph reachable from  forms a tree.

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 , the subgraph reachable from  forms a tree.

A [[polytree]] is a directed graph formed by orienting the edges of a [[tree (graph theory)|free tree]].<ref>{{citation | last1 = Rebane | first1 = George | last2 = Pearl | first2 = Judea | author2-link = Judea Pearl | contribution = The recovery of causal poly-trees from statistical data | pages = 222–228 | title = in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 | url = ftp://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf | year = 1987 }}{{Dead link|date=July 2019 |bot=InternetArchiveBot |fix-attempted=yes }}.</ref>Every polytree is a DAG. In particular, this is true of the [[Arborescence (graph theory)|arborescences]] formed by directing all edges outwards from the roots of a tree.

A [[polytree]] is a directed graph formed by orienting the edges of a [[tree (graph theory)|free tree]].<ref>{{citation | last1 = Rebane | first1 = George | last2 = Pearl | first2 = Judea | author2-link = Judea Pearl | contribution = The recovery of causal poly-trees from statistical data | pages = 222–228 | title = in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 | url = ftp://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf | year = 1987 }}{{Dead link|date=July 2019 |bot=InternetArchiveBot |fix-attempted=yes }}.</ref>Every polytree is a DAG. In particular, this is true of the [[Arborescence (graph theory)|arborescences]] formed by directing all edges outwards from the roots of a tree.

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 ==