Directed graph

From Wikipedia for FEVERv2
(Redirected from Digraph (mathematics))
Jump to navigation Jump to search

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by edges, where the edges have a direction associated with them. Directed graph_sentence_0

Definition Directed graph_section_0

In formal terms, a directed graph is an ordered pair G = (V, A) where Directed graph_sentence_1

Directed graph_unordered_list_0

  • V is a set whose elements are called vertices, nodes, or points;Directed graph_item_0_0
  • A is a set of ordered pairs of vertices, called arrows, directed edges (sometimes simply edges with the corresponding set named E instead of A), directed arcs, or directed lines.Directed graph_item_0_1

It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of vertices, which are usually called edges, arcs, or lines. Directed graph_sentence_2

The aforementioned definition does not allow a directed graph to have multiple arrows with the same source and target nodes, but some authors consider a broader definition that allows directed graphs to have such multiple arrows (namely, they allow the arrows set to be a multiset). Directed graph_sentence_3

More specifically, these entities are addressed as directed multigraphs (or multidigraphs). Directed graph_sentence_4

On the other hand, the aforementioned definition allows a directed graph to have loops (that is, arrows that directly connect nodes with themselves), but some authors consider a narrower definition that doesn't allow directed graphs to have loops. Directed graph_sentence_5

More specifically, directed graphs without loops are addressed as simple directed graphs, while directed graphs with loops are addressed as loop-digraphs (see section Types of directed graphs). Directed graph_sentence_6

Types of directed graphs Directed graph_section_1

See also: Graph (discrete mathematics) § Types of graphs Directed graph_sentence_7

Subclasses Directed graph_section_2

Directed graph_unordered_list_1

  • Symmetric directed graphs are directed graphs where all edges are bidirected (that is, for every arrow that belongs to the digraph, the corresponding inversed arrow also belongs to it).Directed graph_item_1_2
  • Simple directed graphs are directed graphs that have no loops (arrows that directly connect vertices to themselves) and no multiple arrows with same source and target nodes. As already introduced, in case of multiple arrows the entity is usually addressed as directed multigraph. Some authors describe digraphs with loops as loop-digraphs.Directed graph_item_1_3
    • Complete directed graphs are simple directed graphs where each pair of vertices is joined by a symmetric pair of directed arrows (it is equivalent to an undirected complete graph with the edges replaced by pairs of inverse arrows). It follows that a complete digraph is symmetric.Directed graph_item_1_4
    • Oriented graphs are directed graphs having no bidirected edges (i.e. at most one of (x, y) and (y, x) may be arrows of the graph). It follows that a directed graph is an oriented graph if and only if it hasn't any 2-cycle.Directed graph_item_1_5
      • Tournaments are oriented graphs obtained by choosing a direction for each edge in undirected complete graphs.Directed graph_item_1_6
      • Directed acyclic graphs (DAGs) are directed graphs with no directed cycles.Directed graph_item_1_7
        • Multitrees are DAGs in which no two distinct directed paths from a single starting vertex meet back at the same ending vertex.Directed graph_item_1_8
        • Oriented trees or polytrees are DAGs formed by orienting the edges of undirected acyclic graphs.Directed graph_item_1_9
          • Rooted trees are oriented trees in which all edges of the underlying undirected tree are directed either away from or towards the root.Directed graph_item_1_10

Digraphs with supplementary properties Directed graph_section_3

Directed graph_unordered_list_2

  • Weighted directed graphs (also known as directed networks) are (simple) directed graphs with weights assigned to their arrows, similarly to weighted graphs (which are also known as undirected networks or weighted networks).Directed graph_item_2_11
    • Flow networks are weighted directed graphs where two nodes are distinguished, a source and a sink.Directed graph_item_2_12
  • Rooted directed graphs (also known as flow graphs) are digraphs in which a vertex has been distinguished as the root.Directed graph_item_2_13
    • Control flow graphs are rooted digraphs used in computer science as a representation of the paths that might be traversed through a program during its execution.Directed graph_item_2_14
  • Signal-flow graphs are directed graphs in which nodes represent system variables and branches (edges, arcs, or arrows) represent functional connections between pairs of nodes.Directed graph_item_2_15
  • Flow graphs are digraphs associated with a set of linear algebraic or differential equations.Directed graph_item_2_16
  • State diagrams are directed multigraphs that represent finite state machines.Directed graph_item_2_17
  • Commutative diagrams are digraphs used in category theory, where the vertices represent (mathematical) objects and the arrows represent morphisms, with the property that all directed paths with the same start and endpoints lead to the same result by composition.Directed graph_item_2_18
  • In the theory of Lie groups, a quiver Q is a directed graph serving as the domain of, and thus characterizing the shape of, a representation V defined as a functor, specifically an object of the functor category FinVctK where F(Q) is the free category on Q consisting of paths in Q and FinVctK is the category of finite-dimensional vector spaces over a field K. Representations of a quiver label its vertices with vector spaces and its edges (and hence paths) compatibly with linear transformations between them, and transform via natural transformations.Directed graph_item_2_19

Basic terminology Directed graph_section_4

An arrow (x, y) is considered to be directed from x to y; y is called the head and x is called the tail of the arrow; y is said to be a direct successor of x and x is said to be a direct predecessor of y. Directed graph_sentence_8

If a path leads from x to y, then y is said to be a successor of x and reachable from x, and x is said to be a predecessor of y. Directed graph_sentence_9

The arrow (y, x) is called the inverted arrow of (x, y). Directed graph_sentence_10

The adjacency matrix of a multidigraph with loops is the integer-valued matrix with rows and columns corresponding to the vertices, where a nondiagonal entry aij is the number of arrows from vertex i to vertex j, and the diagonal entry aii is the number of loops at vertex i. Directed graph_sentence_11

The adjacency matrix of a directed graph is unique up to identical permutation of rows and columns. Directed graph_sentence_12

Another matrix representation for a directed graph is its incidence matrix. Directed graph_sentence_13

See direction for more definitions. Directed graph_sentence_14

Indegree and outdegree Directed graph_section_5

For a vertex, the number of head ends adjacent to a vertex is called the indegree of the vertex and the number of tail ends adjacent to a vertex is its outdegree (called branching factor in trees). Directed graph_sentence_15

Let G = (V, A) and v ∈ V. The indegree of v is denoted deg(v) and its outdegree is denoted deg(v). Directed graph_sentence_16

A vertex with deg(v) = 0 is called a source, as it is the origin of each of its outcoming arrows. Directed graph_sentence_17

Similarly, a vertex with deg(v) = 0 is called a sink, since it is the end of each of its incoming arrows. Directed graph_sentence_18

The degree sum formula states that, for a directed graph, Directed graph_sentence_19

If for every vertex v ∈ V, deg(v) = deg(v), the graph is called a balanced directed graph. Directed graph_sentence_20

Degree sequence Directed graph_section_6

The degree sequence of a directed graph is the list of its indegree and outdegree pairs; for the above example we have degree sequence ((2, 0), (2, 2), (0, 2), (1, 1)). Directed graph_sentence_21

The degree sequence is a directed graph invariant so isomorphic directed graphs have the same degree sequence. Directed graph_sentence_22

However, the degree sequence does not, in general, uniquely identify a directed graph; in some cases, non-isomorphic digraphs have the same degree sequence. Directed graph_sentence_23

The directed graph realization problem is the problem of finding a directed graph with the degree sequence a given sequence of positive integer pairs. Directed graph_sentence_24

(Trailing pairs of zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the directed graph.) Directed graph_sentence_25

A sequence which is the degree sequence of some directed graph, i.e. for which the directed graph realization problem has a solution, is called a directed graphic or directed graphical sequence. Directed graph_sentence_26

This problem can either be solved by the Kleitman–Wang algorithm or by the Fulkerson–Chen–Anstee theorem. Directed graph_sentence_27

Directed graph connectivity Directed graph_section_7

Main article: Connectivity (graph theory) Directed graph_sentence_28

A directed graph is weakly connected (or just connected) if the undirected underlying graph obtained by replacing all directed edges of the graph with undirected edges is a connected graph. Directed graph_sentence_29

A directed graph is strongly connected or strong if it contains a directed path from x to y and a directed path from y to x for every pair of vertices {x, y}. Directed graph_sentence_30

The strong components are the maximal strongly connected subgraphs. Directed graph_sentence_31

See also Directed graph_section_8

Directed graph_unordered_list_3


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Directed graph.