Directed Graph - Basic Terminology

Basic Terminology

An arc is considered to be directed from to ; is called the head and is called the tail of the arc; is said to be a direct successor of, and is said to be a direct predecessor of . If a path made up of one or more successive arcs leads from to, then is said to be a successor of, and is said to be a predecessor of . The arc is called the arc inverted.

An orientation of a simple undirected graph is obtained by assigning a direction to each edge. Any directed graph constructed this way is called an "oriented graph". A directed graph is an oriented simple graph if and only if it has neither self-loops nor 2-cycles.

A weighted digraph is a digraph with weights assigned to its arcs, similarly to a weighted graph. In the context of graph theory a digraph with weighted edges is called a network.

The adjacency matrix of a digraph (with loops and multiple arcs) is the integer-valued matrix with rows and columns corresponding to the nodes, where a nondiagonal entry is the number of arcs from node i to node j, and the diagonal entry is the number of loops at node i. The adjacency matrix of a digraph is unique up to identical permutation of rows and columns.

Another matrix representation for a digraph is its incidence matrix.

See Glossary of graph theory#Direction for more definitions.