Causal and Temporal Structures
Graphs that have vertices representing events, and edges representing causal relations between events, are often acyclic. For instance, a Bayesian network represents a system of probabilistic events as nodes in a directed acyclic graph, in which the likelihood of an event may be calculated from the likelihoods of its predecessors in the DAG. In this context, the moral graph of a DAG is the undirected graph created by adding an (undirected) edge between all parents of the same node (sometimes called marrying), and then replacing all directed edges by undirected edges.
Another type of graph with a similar causal structure is an influence diagram, the nodes of which represent either decisions to be made or unknown information, and the edges of which represent causal influences from one node to another. In epidemiology, for instance, these diagrams are often used to estimate the expected value of different choices for intervention.
Family trees may also be seen as directed acyclic graphs, with a vertex for each family member and an edge for each parent-child relationship. Despite the name, these graphs are not necessarily trees, because of the possibility of marriages between distant relatives, but the time ordering of births (a parent's birthday is always prior to their child's birthday) causes these graphs to be acyclic. For the same reason, the version history of a distributed revision control system generally has the structure of a directed acyclic graph, in which there is a vertex for each revision and an edge connecting pairs of revisions that were directly derived from each other.
Read more about this topic: Directed Acyclic Graph
Famous quotes containing the words causal, temporal and/or structures:
“There is the illusion of time, which is very deep; who has disposed of it? Mor come to the conviction that what seems the succession of thought is only the distribution of wholes into causal series.”
—Ralph Waldo Emerson (1803–1882)
“Science is the language of the temporal world; love is that of the spiritual world. Man, indeed, describes more than he explains; while the angelic spirit sees and understands. Science saddens man; love enraptures the angel; science is still seeking, love has found. Man judges of nature in relation to itself; the angelic spirit judges of it in relation to heaven. In short to the spirits everything speaks.”
—Honoré De Balzac (1799–1850)
“The American who has been confined, in his own country, to the sight of buildings designed after foreign models, is surprised on entering York Minster or St. Peter’s at Rome, by the feeling that these structures are imitations also,—faint copies of an invisible archetype.”
—Ralph Waldo Emerson (1803–1882)