Relation To Other Kinds of Graphs
A polytree is a directed graph formed by orienting the edges of a free tree. Every polytree is a DAG. In particular, this is true of the arborescences formed by directing all edges outwards from the root of a tree. A multitree (also called a strongly ambiguous graph or a mangrove) is a directed graph in which there is at most one directed path (in either direction) between any two nodes; equivalently, it is a DAG in which, for every node v, the set of nodes reachable from v forms a tree.
Any undirected graph may be made into a DAG by choosing a total order for its vertices and orienting every edge from the earlier endpoint in the order to the later endpoint. However, different total orders may lead to the same acyclic orientation. The number of acyclic orientations is equal to |χ(-1)|, where χ is the chromatic polynomial of the given graph.
Any directed graph may be made into a DAG by removing a feedback vertex set or a feedback arc set. However, the smallest such set is NP-hard to find. An arbitrary directed graph may also be transformed into a DAG, called its condensation, by contracting each of its strongly connected components into a single supervertex. When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are empty, and its condensation is the graph itself.
Read more about this topic: Directed Acyclic Graph
Famous quotes containing the words relation to, relation and/or kinds:
“To be a good enough parent one must be able to feel secure in one’s parenthood, and one’s relation to one’s child...The security of the parent about being a parent will eventually become the source of the child’s feeling secure about himself.”
—Bruno Bettelheim (20th century)
“There is a certain standard of grace and beauty which consists in a certain relation between our nature, such as it is, weak or strong, and the thing which pleases us. Whatever is formed according to this standard pleases us, be it house, song, discourse, verse, prose, woman, birds, rivers, trees, room, dress, and so on. Whatever is not made according to this standard displeases those who have good taste.”
—Blaise Pascal (1623–1662)
“Don’t matter how much money you got, there’s only two kinds of people: there’s saved people and there’s lost people.”
—Bob Dylan [Robert Allen Zimmerman] (b. 1941)