In graph theory, a polytree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph (DAG) for which there are no undirected cycles either. Equivalently, a polytree is a directed graph formed by giving a direction to each edge of a forest. The name "polytree" was coined by Rebane and Pearl (1987), and is sometimes referred to as "singly connected network" (Kim and Pearl, 1983).

PropertyValue
dbpedia-owl:thumbnail
dbpprop:abstract
  • In graph theory, a polytree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph (DAG) for which there are no undirected cycles either. Equivalently, a polytree is a directed graph formed by giving a direction to each edge of a forest. The name "polytree" was coined by Rebane and Pearl (1987), and is sometimes referred to as "singly connected network" (Kim and Pearl, 1983). Every directed tree is a polytree, but not every polytree is a directed tree. The picture on the right shows a polytree which is not a directed tree. Polytrees often are encountered in Bayesian networks. In fact, some problems can be solved in polytrees in polynomial time but take exponential time in general networks. Polytrees are self-similar. Each sub-portion of a polytree is also a polytree.
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • In graph theory, a polytree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph (DAG) for which there are no undirected cycles either. Equivalently, a polytree is a directed graph formed by giving a direction to each edge of a forest. The name "polytree" was coined by Rebane and Pearl (1987), and is sometimes referred to as "singly connected network" (Kim and Pearl, 1983).
rdfs:label
  • Polytree
owl:sameAs
skos:subject
foaf:depiction
foaf:page
is owl:sameAs of