Glossary of Graph Theory - Direction

Direction

A directed arc, or directed edge, is an ordered pair of endvertices that can be represented graphically as an arrow drawn between the endvertices. In such an ordered pair the first vertex is called the initial vertex or tail; the second one is called the terminal vertex or head (because it appears at the arrow head). An undirected edge disregards any sense of direction and treats both endvertices interchangeably. A loop in a digraph, however, keeps a sense of direction and treats both head and tail identically. A set of arcs are multiple, or parallel, if they share the same head and the same tail. A pair of arcs are anti-parallel if one's head/tail is the other's tail/head. A digraph, or directed graph, or oriented graph, is analogous to an undirected graph except that it contains only arcs. A mixed graph may contain both directed and undirected edges; it generalizes both directed and undirected graphs. When stated without any qualification, a graph is almost always assumed to be undirected.

A digraph is called simple if it has no loops and at most one arc between any pair of vertices. When stated without any qualification, a digraph is usually assumed to be simple. A quiver is a directed graph which is specifically allowed, but not required, to have loops and more than one arc between any pair of vertices.

In a digraph Γ, we distinguish the out degree dΓ+(v), the number of edges leaving a vertex v, and the in degree dΓ-(v), the number of edges entering a vertex v. If the graph is oriented, the degree dΓ(v) of a vertex v is equal to the sum of its out- and in- degrees. When the context is clear, the subscript Γ can be dropped. Maximum and minimum out degrees are denoted by Δ+(Γ) and δ+(Γ); and maximum and minimum in degrees, Δ-(Γ) and δ-(Γ).

An out-neighborhood, or successor set, N+Γ(v) of a vertex v is the set of heads of arcs going from v. Likewise, an in-neighborhood, or predecessor set, N-Γ(v) of a vertex v is the set of tails of arcs going into v.

A source is a vertex with 0 in-degree; and a sink, 0 out-degree.

A vertex v dominates another vertex u if there is an arc from v to u. A vertex subset S is out-dominating if every vertex not in S is dominated by some vertex in S; and in-dominating if every vertex in S is dominated by some vertex not in S.

A kernel in a (possibly directed) graph G is an independent set S such that every vertex in V(G) \ S dominates some vertex in S. In undirected graphs, kernels are maximal independent sets. A digraph is kernel perfect if every induced sub-digraph has a kernel.

An Eulerian digraph is a digraph with equal in- and out-degrees at every vertex.

The zweieck of an undirected edge is the pair of diedges and which form the simple dicircuit.

An orientation is an assignment of directions to the edges of an undirected or partially directed graph. When stated without any qualification, it is usually assumed that all undirected edges are replaced by a directed one in an orientation. Also, the underlying graph is usually assumed to be undirected and simple.

A tournament is a digraph in which each pair of vertices is connected by exactly one arc. In other words, it is an oriented complete graph.

A directed path, or just a path when the context is clear, is an oriented simple path such that all arcs go the same direction, meaning all internal vertices have in- and out-degrees 1. A vertex v is reachable from another vertex u if there is a directed path that starts from u and ends at v. Note that in general the condition that u is reachable from v does not imply that v is also reachable from u.

If v is reachable from u, then u is a predecessor of v and v is a successor of u. If there is an arc from u to v, then u is a direct predecessor of v, and v is a direct successor of u.

A digraph is strongly connected if every vertex is reachable from every other following the directions of the arcs. On the contrary, a digraph is weakly connected if its underlying undirected graph is connected. A weakly connected graph can be thought of as a digraph in which every vertex is "reachable" from every other but not necessarily following the directions of the arcs. A strong orientation is an orientation that produces a strongly connected digraph.

A directed cycle, or just a cycle when the context is clear, is an oriented simple cycle such that all arcs go the same direction, meaning all vertices have in- and out-degrees 1. A digraph is acyclic if it does not contain any directed cycle. A finite, acyclic digraph with no isolated vertices necessarily contains at least one source and at least one sink.

An arborescence, or out-tree or branching, is an oriented tree in which all vertices are reachable from a single vertex. Likewise, an in-tree is an oriented tree in which a single vertex is reachable from every other one.

Read more about this topic:  Glossary Of Graph Theory

Famous quotes containing the word direction:

    Our vices always lie in the direction of our virtues, and in their best estate are but plausible imitations of the latter.
    Henry David Thoreau (1817–1862)

    The learned and the studious of thought have no monopoly of wisdom. Their violence of direction in some degree disqualifies them to think truly.
    Ralph Waldo Emerson (1803–1882)

    From cradle to grave this problem of running order through chaos, direction through space, discipline through freedom, unity through multiplicity, has always been, and must always be, the task of education, as it is the moral of religion, philosophy, science, art, politics and economy; but a boy’s will is his life, and he dies when it is broken, as the colt dies in harness, taking a new nature in becoming tame.
    Henry Brooks Adams (1838–1918)