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:
“Any relation to the land, the habit of tilling it, or mining it, or even hunting on it, generates the feeling of patriotism. He who keeps shop on it, or he who merely uses it as a support to his desk and ledger, or to his manufactory, values it less.”
—Ralph Waldo Emerson (1803–1882)
“Much poetry seems to be aware of its situation in time and of its relation to the metronome, the clock, and the calendar. ... The season or month is there to be felt; the day is there to be seized. Poems beginning “When” are much more numerous than those beginning “Where” of “If.” As the meter is running, the recurrent message tapped out by the passing of measured time is mortality.”
—William Harmon (b. 1938)
“There are two kinds of fathers in traditional households: the fathers of sons and the fathers of daughters. These two kinds of fathers sometimes co-exist in one and the same man. For instance, Daughter’s Father kisses his little girl goodnight, strokes her hair, hugs her warmly, then goes into the next room where he becomes Son’s Father, who says in a hearty voice, perhaps with a light punch on the boy’s shoulder: “Goodnight, Son, see ya in the morning.””
—Letty Cottin Pogrebin (20th century)