387
个编辑
更改
跳到导航
跳到搜索
第35行：
第35行： − + − {{multiple image − |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 − |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 [[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>
→Related families of graphs 相关概念
<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 相关概念 ===
===相关概念 ===
多重树（英语：polytree）由将自由树的边定向（英语：orienting）而得到。[14] 多重树必定是有向无环图。对于有根树，将其所有边赋予指离根的方向也可以得到有向无环图，即树状图。
多重树（英语：polytree）由将自由树的边定向（英语：orienting）而得到。[14] 多重树必定是有向无环图。对于有根树，将其所有边赋予指离根的方向也可以得到有向无环图，即树状图。
强明确树（英语：multitree）是每两个顶点最多被一条路径所连接的有向无环图。等价的说，它是满足以下性质的一个有向无环图：对于图中每个顶点v，从v可达的顶点组成一颗树。[16]
强明确树（英语：multitree）是每两个顶点最多被一条路径所连接的有向无环图。等价的说，它是满足以下性质的一个有向无环图：对于图中每个顶点v，从v可达的顶点组成一颗树。[16]