| << Chapter < Page | Chapter >> Page > |
(From Wikipedia, the free encyclopedia)
A directed graph or digraph G is an ordered pair G: = (V,A) with
An arc e = (x,y) is considered to be directed from x to y; y is called the head and x is called the tail of the arc; y is said to be a direct successor of x, and x is said to be a direct predecessor of y. If a path leads from x to y, then y is said to be a successor of x, and x is said to be a predecessor of y. The arc (y,x) is called the arc (x,y) inverted.
A directed graph is called symmetric if every arc belongs to it together with the corresponding inverted arc. A symmetric loopless directed graph is equivalent to an undirected graph with the pairs of inverted arcs replaced with edges; thus the number of edges is equal to the number of arcs halved.
A variation on this definition is the oriented graph, which is a graph (or multigraph; see below) with an orientation or direction assigned to each of its edges. A distinction between a directed graph and an oriented simple graph is that if x and y are vertices, a directed graph allows both (x,y) and (y,x) as edges, while only one is permitted in an oriented graph. A more fundamental difference is that, in a directed graph (or multigraph), the directions are fixed, but in an oriented graph (or multigraph), only the underlying graph is fixed, while the orientation may vary.
A directed acyclic graph, occasionally called a dag or DAG, is a directed graph with no directed cycles.
A quiver is simply a directed graph, but the context is different. When discussing quivers emphasis is placed on representations of the graph where vector spaces are attached to the vertices and linear transformations are attached to the arcs.
Mixed graph
A mixed graph G is a graph in which some edges may be directed and some may be undirected. It is written as an ordered triple G := (V, E, A) with V, E, and A defined as above. Directed and undirected graphs are special cases.
(From Wikipedia, the free encyclopedia)
An undirected graph can be viewed as a simplicial complex C with a single-element set per vertex and a two-element set per edge. The geometric realization |C| of the complex consists of a copy of the unit interval [0,1] per edge, with the endpoints of these intervals glued together at vertices. In this view, embeddings of graphs into a surface or as subdivisions of other graphs are both instances of topological embedding, homeomorphism of graphs is just the specialization of topological homeomorphism, the notion of a connected graph coincides with topological connectedness, and a connected graph is a tree if and only if its fundamental group is trivial.
Other simplicial complexes associated with graphs include the Whitney complex or clique complex, with a set per clique of the graph, and the matching complex, with a set per matching of the graph (equivalently, the clique complex of the complement of the line graph). The matching complex of a complete bipartite graph is called a chessboard complex, as it can be also described as the complex of sets of non-attacking rooks on a chessboard.
The canonical application of topological sorting is in scheduling a sequence of jobs. The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be done (for example, washing machine must finish before we put the clothes to dry). Then, a topological sort gives an order in which to perform the jobs. This has applications in computer science, such as in instruction scheduling, ordering of formula cell evaluation in spreadsheets, dependencies in makefiles, and symbol dependencies in linkers.
 |
The graph shown to the left has many valid topological sorts, including: FIXME: A LIST CAN NOT BE A TABLE ENTRY.7,5,3,11,8,2,10,97,5,11,2,3,10,8,93,7,8,5,11,10,9,23,5,7,11,10,2,8,9 |
The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges (Θ(|V|+|E|)).
One of these algorithms works by choosing vertices in the same order as the eventual topological sort. First, find a list of "start nodes" which have no incoming edges and insert them into a queue Q (at least one such node must exist if graph is acyclic). Then,
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
remove a node n from Q
output n
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into Q
if graph has edges then
output error message (graph has a cycle)
If this algorithm terminates without outputing all the nodes of the graph, it means the graph has at least one cycle and therefore is not a DAG, so a topological sort is impossible. Note that, reflecting the non-uniqueness of the resulting sort, the structure Q need not be a queue; it may be a stack or simply a set.
An alternative algorithm for topological sorting is based on depth-first search. Loop through the vertices of the graph, in any order, initiating a depth first search for any vertex that has not already been visited by a previous search. The desired topological sorting is the reverse postorder of these searches. That is, we can construct the ordering as a list of vertices, by adding each vertex to the start of the list at the time when the depth first search is processing that vertex and has returned from processing all children of that vertex. Since each edge and vertex is visited once, the algorithm runs in linear time.
Notification Switch
Would you like to follow the 'Data structures and algorithms' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|