标题： 关于度数受限有向图的系统发育图 显示英文标题

标题： On the phylogeny graphs of degree-bounded digraphs

摘要： Hefner [K. A. S. Hefner, K. F. Jones, S. -R. Kim, R. J. Lundgren and F. S. Roberts: $(i,j)$ 竞争图，离散应用数学，32，(1991) 241-262] 描述了每个顶点的入度和出度最多为二且其竞争图是区间的无环有向图。 他们将每个顶点的入度和出度最多为二的无环有向图称为 $(2,2)$ 有向图。 在本文中，我们研究了 $(2,2)$ 有向图的系统发生图。 特别是，我们给出了 $(2,2)$ 有向图具有弦性系统发生图的充分条件和必要条件。 系统发生图在贝叶斯网络理论中也被称为道德图。 我们的工作受到与贝叶斯网络中证据传播相关问题的启发，了解哪些无环有向图的道德图是弦性的很有用。 显示英文摘要

摘要： Hefner [K. A. S. Hefner, K. F. Jones, S. -R. Kim, R. J. Lundgren and F. S. Roberts: $(i,j)$ competition graphs, Discrete Applied Mathematics, 32, (1991) 241-262] characterized acyclic digraphs each vertex of which has inderee and outdegree at most two and whose competition graphs are interval. They called acyclic digraphs each vertex of which has inderee and outdegree at most two $(2,2)$ digraphs. In this paper, we study the phylogeny graphs of $(2,2)$ digraphs. Especially, we give a sufficient condition and necessary conditions for $(2,2)$ digraphs having chordal phylogeny graphs. Phylogeny graphs are also called moral graphs in Bayesian network theory. Our work is motivated by problems related to evidence propagation in a Bayesian network for which it is useful to know which acyclic digraphs have their moral graphs being chordal.