|
Polytree
In mathematics, and more specifically in graph theory, a polytree (also called directed tree, oriented tree; . or singly connected network.) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, a polytree is formed by assigning an orientation to each edge of a connected and acyclic undirected graph. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic. A polytree is an example of an oriented graph. The term ''polytree'' was coined in 1987 by Rebane and Pearl.. Related structures * An arborescence is a directed rooted tree, i.e. a directed acyclic graph in which there exists a single source node that has a unique path to every other node. Every arborescence is a polytree, but not every polytree is an arborescence. * A multitree is a directed acyclic g ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sumner's Conjecture
Sumner's conjecture (also called Sumner's universal tournament conjecture) is a conjecture in extremal graph theory on oriented trees in tournaments. It states that every orientation of every n-vertex tree is a subgraph of every (2n-2)-vertex tournament. David Sumner, a graph theorist at the University of South Carolina, conjectured in 1971 that tournaments are universal graphs for polytrees. The conjecture was proven for all large n by Daniela Kühn, Richard Mycroft, and Deryk Osthus. Examples Let polytree P be a star K_, in which all edges are oriented outward from the central vertex to the leaves. Then, P cannot be embedded in the tournament formed from the vertices of a regular 2n-3-gon by directing every edge clockwise around the polygon. For, in this tournament, every vertex has indegree and outdegree equal to n-2, while the central vertex in P has larger outdegree n-1. Thus, if true, Sumner's conjecture would give the best possible size of a universal graph for polytree ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
