Directed graph: Difference between revisions
Pierre5018 (talk | contribs) →See also: RG and SFG (Math) |
→See also: ce, add Zero-weight cycle problem |
||
(148 intermediate revisions by 81 users not shown) | |||
Line 1: | Line 1: | ||
{{Short description|Graph with oriented edges}} |
|||
[[File:Directed.svg|125px|thumb|A directed graph.]] |
|||
[[File:Directed graph no background.svg|upright|thumb|A simple directed graph]] |
|||
In [[mathematics]], and more specifically in [[graph theory]], a '''directed graph''' (or '''digraph''') is a [[graph (mathematics)|graph]], or set of nodes connected by edges, where the edges have a direction associated with them. In formal terms, a digraph is a pair <math>G=(V,A)</math> (sometimes <math>G=(V,E)</math>) of:<ref>{{harvtxt|Bang-Jensen|Gutin|2000}}. {{harvtxt|Diestel|2005}}, Section 1.10. {{harvtxt|Bondy|Murty|1976}}, Section 10.</ref> |
|||
* a [[Set (mathematics)|set]] ''V'', whose [[element (mathematics)|elements]] are called ''vertices'' or ''nodes'', |
|||
* a set ''A'' of [[ordered pair]]s of vertices, called ''arcs'', ''directed edges'', or ''arrows'' (and sometimes simply ''edges'' with the corresponding set named ''E'' instead of ''A''). |
|||
In [[mathematics]], and more specifically in [[graph theory]], a '''directed graph''' (or '''digraph''') is a [[Graph (discrete mathematics)|graph]] that is made up of a set of [[Vertex (graph theory)|vertices]] connected by directed [[Edge (graph theory)|edges]], often called '''arcs'''. |
|||
It differs from an ordinary or [[undirected graph]], in that the latter is defined in terms of [[unordered pair]]s of vertices, which are usually called edges. |
|||
==Definition== |
|||
A digraph is called "simple" if it has no loops, and no multiple arcs (arcs with same starting and ending nodes). A ''[[multigraph|directed multigraph]]'', in which the arcs constitute a [[multiset]], rather than a set, of ordered pairs of vertices may have loops (that is, "self-loops" with same starting and ending node) and multiple arcs. Some, but not all, texts allow a digraph, without the qualification simple, to have self loops, multiple arcs, or both. |
|||
In formal terms, a directed graph is an ordered pair {{nowrap|1=''G'' = (''V'', ''A'')}} where<ref>{{harvtxt|Bang-Jensen|Gutin|2000}}. {{harvtxt|Bang-Jensen|Gutin|2018}}, Chapter 1.{{harvtxt|Diestel|2005}}, Section 1.10. {{harvtxt|Bondy|Murty|1976}}, Section 10.</ref> |
|||
* ''V'' is a [[Set (mathematics)|set]] whose [[Element (mathematics)|elements]] are called ''[[Vertex (graph theory)|vertices]]'', ''nodes'', or ''points''; |
|||
* ''A'' is a set of [[ordered pair]]s of vertices, called ''arcs'', ''directed edges'' (sometimes simply ''edges'' with the corresponding set named ''E'' instead of ''A''), ''arrows'', or ''directed lines''. |
|||
It differs from an ordinary or [[undirected graph]], in that the latter is defined in terms of [[unordered pair]]s of vertices, which are usually called ''edges'', ''links'' or ''lines''. |
|||
==Basic terminology== |
|||
An arc <math>e = (x, y)</math> is considered to be directed ''from'' <math>x</math> ''to'' <math>y</math>; <math>y</math> is called the ''head'' and <math>x</math> is called the ''tail'' of the arc; <math>y</math> is said to be a ''direct successor'' of <math>x</math>, and <math>x</math> is said to be a ''direct predecessor'' of <math>y</math>. If a [[path (graph theory)|path]] made up of one or more successive arcs leads from <math>x</math> to <math>y</math>, then <math>y</math> is said to be a ''successor'' of <math>x</math>, and <math>x</math> is said to be a ''predecessor'' of <math>y</math>. The arc <math>(y, x)</math> is called the arc <math>(x, y)</math> ''inverted''. |
|||
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 arcs (namely, they allow the arc set to be a [[multiset]]). Sometimes these entities are called '''[[directed multigraph]]s''' (or '''multidigraphs''').<br/> |
|||
An [[Orientation (graph theory)|orientation]] of a [[simple graph|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.<ref>{{harvtxt|Diestel|2005}}, Section 1.10.</ref> |
|||
On the other hand, the aforementioned definition allows a directed graph to have [[Loop (graph theory)|loops]] (that is, arcs that directly connect nodes with themselves), but some authors consider a narrower definition that does not allow directed graphs to have loops.<ref name="Chartrand">{{cite book |last=Chartrand |first=Gary |date=1977 |title=Introductory Graph Theory |url=https://books.google.com/books?id=rYuToT7vHbMC&q=Introductory%20Graph%20Theory&pg=PP1 |publisher=Courier Corporation |isbn=9780486247755 |access-date=2020-10-02 |archive-date=2023-02-04 |archive-url=https://web.archive.org/web/20230204155556/https://books.google.com/books?id=rYuToT7vHbMC&q=Introductory%20Graph%20Theory&pg=PP1 |url-status=live }}</ref> |
|||
Directed graphs without loops may be called '''simple directed graphs''', while directed graphs with loops may be called ''loop-digraphs'' (see section [[#Types of directed graphs|Types of directed graph]]). |
|||
==Types of directed graphs== |
|||
A ''weighted digraph'' is a digraph with weights assigned to its arcs, similar to a [[weighted graph]]. |
|||
{{see also|Graph (discrete mathematics)#Types of graphs}} |
|||
In the context of graph theory a digraph with weighted edges is called a ''network''. |
|||
===Subclasses=== |
|||
The [[adjacency matrix]] of a digraph (with loops and multiple arcs) is the integer-valued [[Matrix (mathematics)|matrix]] with rows and columns corresponding to the nodes, where a nondiagonal entry <math>a_{ij}</math> is the number of arcs from node ''i'' to node ''j'', and the diagonal entry <math>a_{ii}</math> is the number of loops at node ''i''. The adjacency matrix of a digraph is unique up to identical permutation of rows and columns. |
|||
[[File:Directed acyclic graph 2.svg|right|upright=0.65|thumb|A simple directed acyclic graph]] |
|||
[[File:4-tournament.svg|thumb|right|upright=0.4|A tournament on 4 vertices]] |
|||
* '''Symmetric directed graphs''' are directed graphs where all edges appear twice, one in each direction (that is, for every arrow that belongs to the digraph, the corresponding inverse arrow also belongs to it). (Such an edge is sometimes called "bidirected" and such graphs are sometimes called "bidirected", but this conflicts with the meaning for [[bidirected graph]]s.) |
|||
* '''Simple directed graphs''' are directed graphs that have no [[Loop (graph theory)|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''.<ref name="Chartrand"/> |
|||
** '''Complete directed graphs''' are simple directed graphs where each pair of vertices is joined by a symmetric pair of directed arcs (it is equivalent to an undirected [[complete graph]] with the edges replaced by pairs of inverse arcs). It follows that a complete digraph is symmetric. |
|||
** '''Semicomplete multipartite digraphs''' are simple digraphs in which the vertex set is partitioned into sets such that for every pair of vertices ''x'' and ''y'' in different sets, there is an arc between ''x'' and ''y''. There can be one arc between ''x'' and ''y'' or two arcs in opposite directions.<ref>{{harvtxt|Bang-Jensen|Gutin|2018}}, Chapter 7 by Yeo.</ref> |
|||
** '''Semicomplete digraphs''' are simple digraphs where there is an arc between each pair of vertices. Every semicomplete digraph is a semicomplete multipartite digraph in a trivial way, with each vertex constituting a set of the partition.<ref name="Bang-Jensen 2018">{{harvtxt|Bang-Jensen|Gutin|2018}}, Chapter 2 by Bang-Jensen and Havet.</ref> |
|||
** '''Quasi-transitive digraphs''' are simple digraphs where for every triple ''x'', ''y'', ''z'' of distinct vertices with arcs from ''x'' to ''y'' and from ''y'' to ''z'', there is an arc between ''x'' and ''z''. There can be just one arc between ''x'' and ''z'' or two arcs in opposite directions. A semicomplete digraph is a quasi-transitive digraph. There are extensions of quasi-transitive digraphs called ''k''-quasi-transitive digraphs.<ref>{{harvtxt|Bang-Jensen|Gutin|2018}}, Chapter 8 by Galeana-Sanchez and Hernandez-Cruz.</ref> |
|||
** '''[[Oriented graph]]s''' are directed graphs having no opposite pairs of directed edges (i.e. at most one of {{nowrap|(''x'', ''y'')}} and {{nowrap|(''y'', ''x'')}} may be arrows of the graph). It follows that a directed graph is an oriented graph if and only if it has no [[directed cycle|2-cycle]].<ref>{{harvtxt|Diestel|2005}}, Section 1.10.</ref> (This is not the only meaning of "oriented graph"; see [[Orientation (graph theory)]].) |
|||
*** '''[[Tournament (mathematics)|Tournaments]]''' are oriented graphs obtained by choosing a direction for each edge in undirected [[complete graph]]s. A tournament is a semicomplete digraph.<ref name="Bang-Jensen 2018"/> |
|||
*** A directed graph is '''acyclic''' if it has no [[directed cycle]]s. The usual name for such a digraph is '''[[directed acyclic graph]]''' (DAG).<ref>{{harvtxt|Bang-Jensen|Gutin|2018}}, Chapter 3 by Gutin.</ref> |
|||
**** ''[[Multitree]]s'' are DAGs in which there are no two distinct directed paths from the same starting vertex to the same ending vertex. |
|||
**** ''[[Oriented tree]]s'' or ''polytrees'' are DAGs formed by orienting the edges of trees (connected, acyclic undirected graphs). |
|||
***** ''[[Rooted tree]]s'' are oriented trees in which all edges of the underlying undirected tree are directed either away from or towards the root (they are called, respectively, '''arborescences''' or '''out-trees''', and '''in-trees'''. |
|||
===Digraphs with supplementary properties=== |
|||
Another matrix representation for a digraph is its [[incidence matrix]]. |
|||
* '''Weighted directed graphs''' (also known as '''directed networks''') are (simple) directed graphs with ''weights'' assigned to their arrows, similarly to [[weighted graph]]s (which are also known as undirected networks or [[weighted network]]s).<ref name="Chartrand"/> |
|||
** '''[[Flow network]]s''' are weighted directed graphs where two nodes are distinguished, a ''source'' and a ''sink''. |
|||
* '''[[Rooted graph|Rooted directed graphs]]''' (also known as '''flow graphs''') are digraphs in which a vertex has been distinguished as the root. |
|||
** ''[[Control-flow graph]]s'' are rooted digraphs used in computer science as a representation of the paths that might be traversed through a program during its execution. |
|||
* '''[[Signal-flow graph]]s''' are directed graphs in which nodes represent system variables and branches (edges, arcs, or arrows) represent functional connections between pairs of nodes. |
|||
* '''[[Flow graph (mathematics)|Flow graphs]]''' are digraphs associated with a set of linear algebraic or differential equations. |
|||
* '''[[State diagram]]s''' are [[directed multigraph]]s that represent [[finite state machine]]s. |
|||
* '''[[Commutative diagram]]s''' 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. |
|||
* In the theory of [[Lie group]]s, a '''[[Quiver (mathematics)|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]] FinVct<sub>''K''</sub><sup>''F''(''Q'')</sup> where ''F''(''Q'') is the [[free category]] on ''Q'' consisting of paths in ''Q'' and FinVct<sub>''K''</sub> is the category of finite-dimensional [[vector space]]s over a [[Field (mathematics)|field]] ''K''. Representations of a quiver label its vertices with vector spaces and its edges (and hence paths) compatibly with [[Linear map|linear transformations]] between them, and transform via [[natural transformation]]s. |
|||
==Basic terminology== |
|||
See [[Glossary of graph theory#Direction|direction]] for more definitions. |
|||
[[File:Incidence matrix - directed graph.svg|thumb|Oriented graph with corresponding incidence matrix]] |
|||
An arc {{nowrap|(''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 (graph theory)|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''. The arc {{nowrap|(''y'', ''x'')}} is called the ''reversed arc'' of {{nowrap|(''x'', ''y'')}}. |
|||
The [[adjacency matrix]] of a multidigraph with loops is the integer-valued [[Matrix (mathematics)|matrix]] with rows and columns corresponding to the vertices, where a nondiagonal entry ''a''<sub>''ij''</sub> is the number of arcs from vertex ''i'' to vertex ''j'', and the diagonal entry ''a''<sub>''ii''</sub> is the number of loops at vertex ''i''. The adjacency matrix of a directed graph is a [[logical matrix]], and is |
|||
unique up to permutation of rows and columns. |
|||
Another matrix representation for a directed graph is its [[incidence matrix]]. |
|||
See [[Glossary of graph theory#direction|direction]] for more definitions. |
|||
==Indegree and outdegree== |
==Indegree and outdegree== |
||
[[File:DirectedDegrees.svg|thumb|A |
[[File:DirectedDegrees.svg|thumb|A directed graph with vertices labeled (indegree, outdegree)]] |
||
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). |
|||
Let {{nowrap|1=''G'' = (''V'', ''E'')}} and {{nowrap|''v'' ∈ ''V''}}. The indegree of ''v'' is denoted deg<sup>−</sup>(''v'') and its outdegree is denoted deg<sup>+</sup>(''v''). |
|||
For a node, the number of head endpoints adjacent to a node is called the ''indegree'' of the node and the number of tail endpoints adjacent to a node is its ''outdegree'' (called "[[branching factor]]" in trees). |
|||
A vertex with {{nowrap|1=deg<sup>−</sup>(''v'') = 0}} is called a ''source'', as it is the origin of each of its outcoming arcs. Similarly, a vertex with {{nowrap|1=deg<sup>+</sup>(''v'') = 0}} is called a ''sink'', since it is the end of each of its incoming arcs. |
|||
The ''degree sum formula'' states that, for a directed graph, |
The ''degree sum formula'' states that, for a directed graph, |
||
:<math>\sum_{v \in V} \deg^ |
: <math>\sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |E|.</math> |
||
If for every |
If for every vertex {{nowrap|''v'' ∈ ''V''}}, {{nowrap|1=deg<sup>+</sup>(''v'') = deg<sup>−</sup>(''v'')}}, the graph is called a ''balanced directed graph''.<ref>{{citation|page=460|title=Discrete Mathematics and Graph Theory|first1=Bhavanari|last1=Satyanarayana|first2=Kuncham Syam| last2=Prasad| publisher=PHI Learning Pvt. Ltd.|isbn=978-81-203-3842-5}}; {{citation|page=[https://archive.org/details/combinatorialmat0000brua/page/51 51]| title=Combinatorial Matrix Classes| volume=108|series=Encyclopedia of Mathematics and Its Applications|first=Richard A. |last=Brualdi| publisher=Cambridge University Press|year=2006|isbn=978-0-521-86565-4| url=https://archive.org/details/combinatorialmat0000brua/page/51}}.</ref> |
||
==Degree sequence== |
==Degree sequence== |
||
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)). The degree sequence is a directed graph invariant so isomorphic directed graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a graph; in some cases, non-isomorphic |
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)). The degree sequence is a directed graph invariant so isomorphic directed graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a directed graph; in some cases, non-isomorphic digraphs have the same degree sequence. |
||
The [[ |
The [[Digraph realization problem|directed graph realization problem]] is the problem of finding a directed graph with the degree sequence a given sequence of positive [[integer]] pairs. (Trailing pairs of zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the directed graph.) 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. This problem can either be solved by the [[Kleitman–Wang algorithm]] or by the [[Fulkerson–Chen–Anstee theorem]]. |
||
== |
==Directed graph connectivity== |
||
{{main|Connectivity (graph theory)}} |
{{main|Connectivity (graph theory)}} |
||
A |
A directed graph is ''weakly connected'' (or just ''connected''<ref>{{harvtxt|Bang-Jensen|Gutin|2000}} p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).</ref>) if the undirected ''underlying graph'' obtained by replacing all directed edges of the graph with undirected edges is a [[Connectivity (graph theory)|connected graph]]. |
||
A directed graph is ''[[strongly connected]]'' or ''strong'' if it contains a directed path from ''x'' to ''y'' (and from ''y'' to ''x'') for every pair of vertices {{nowrap|(''x'', ''y'')}}. The ''strong components'' are the maximal strongly connected subgraphs. |
|||
==Classes of digraphs== |
|||
A connected [[rooted graph]] (or ''flow graph'') is one where there exists a directed path to every vertex from a distinguished ''root vertex''. |
|||
A directed graph ''G'' is called '''symmetric''' if, for every arc that belongs to ''G'', the corresponding reversed arc also belongs to ''G''. A symmetric, loopless directed graph is equivalent to an undirected graph with the edges replaced by pairs of inverse arcs; thus the number of edges is equal to the number of arcs halved. |
|||
[[File:Directed acyclic graph 2.svg|right|100px|thumb|A simple acyclic directed graph]] |
|||
An '''acyclic''' directed graph, acyclic digraph, or [[directed acyclic graph]] is a directed graph with no [[directed cycle]]s. Special cases of acyclic directed graphs include [[multitree]]s (graphs in which no two directed paths from a single starting node meet back at the same ending node), [[oriented tree]]s or polytrees (digraphs formed by orienting the edges of undirected acyclic graphs), and [[rooted tree]]s (oriented trees in which all edges of the underlying undirected tree are directed away from the roots). |
|||
[[File:4-tournament.svg|thumb|right|100px|A tournament on 4 vertices]] |
|||
A '''[[tournament (mathematics)|tournament]]''' is an oriented graph obtained by choosing a direction for each edge in an undirected [[complete graph]]. |
|||
In the theory of [[Lie group]]s, a '''[[quiver (mathematics)|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]] '''FinVct'''<sub>''K''</sub><sup>F(''Q'')</sup> where ''F''(''Q'') is the [[free category]] on ''Q'' consisting of paths in ''Q'' and '''FinVct'''<sub>''K''</sub> is the category of finite-dimensional [[vector space]]s over a [[Field (mathematics)|field]] ''K''. Representations of a quiver label its vertices with vector spaces and its edges (and hence paths) compatibly with [[Linear map|linear transformations]] between them, and transform via [[natural transformation]]s. |
|||
==See also== |
==See also== |
||
{{cmn| |
|||
*[[Coates graph]] |
|||
* [[Binary relation]] |
|||
* [[Coates graph]] |
|||
* [[DGML|Directed Graph Markup Language]] |
|||
* [[DRAKON|DRAKON flowchart]] |
|||
* [[Flow chart]] |
* [[Flow chart]] |
||
* [[ |
* [[Globular set]] |
||
* [[ |
* [[Glossary of graph theory]] |
||
* [[ |
* [[Graph Style Sheets]] |
||
* [[ |
* [[Graph theory]] |
||
* [[Graph (abstract data type)]] |
|||
* [[Network theory]] |
|||
* [[Orientation (graph theory)|Orientation]] |
|||
* [[Preorder]] |
* [[Preorder]] |
||
* [[Topological sorting]] |
|||
* [[Quiver (mathematics)|Quiver]] |
|||
* [[Signal-flow graph]] |
|||
* [[Transpose graph]] |
* [[Transpose graph]] |
||
* [[Vertical constraint graph]] |
* [[Vertical constraint graph]] |
||
* [[Zero-weight cycle problem]] |
|||
}} |
|||
==Notes== |
==Notes== |
||
{{ |
{{Reflist}} |
||
==References== |
==References== |
||
*{{Citation |
* {{Citation |
||
| last1=Bang-Jensen | first1=Jørgen |
| last1=Bang-Jensen | first1=Jørgen |
||
| last2=Gutin | first2=Gregory |
| last2=Gutin | first2=Gregory |
||
Line 80: | Line 116: | ||
| isbn=1-85233-268-9 |
| isbn=1-85233-268-9 |
||
| url=http://www.cs.rhul.ac.uk/books/dbook/ |
| url=http://www.cs.rhul.ac.uk/books/dbook/ |
||
}} |
}}(the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009 {{ISBN|1-84800-997-6}}). |
||
* {{ |
* {{Citation |
||
| last1= |
| last1=Bang-Jensen | first1=Jørgen |
||
| last2= |
| last2=Gutin | first2=Gregory |
||
| title= |
| title= Classes of Directed Graphs |
||
| publisher=[[Springer International Publishing AG|Springer]] |
|||
| year=1976 |
|||
| year=2018 |
|||
| publisher=North-Holland |
|||
| isbn= |
| isbn=978-3319718408 |
||
}}. |
|||
| url=http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html |
|||
* {{citation |last1 = Bondy |
|||
|first1 = John Adrian |
|||
|author-link1 = John Adrian Bondy |
|||
|last2 = Murty |
|||
|first2 = U. S. R. |
|||
|author-link2 = U. S. R. Murty |
|||
|title = Graph Theory with Applications |
|||
|year = 1976 |
|||
|publisher = North-Holland |
|||
|isbn = 0-444-19451-7 |
|||
|url = https://archive.org/details/graphtheorywitha0000bond |
|||
|url-access = registration |
|||
}}. |
}}. |
||
*{{Citation |
* {{Citation |
||
| last=Diestel | first=Reinhard |
| last=Diestel | first=Reinhard |
||
| title=Graph Theory |
| title=Graph Theory |
||
Line 99: | Line 147: | ||
| url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ |
| url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ |
||
}} (the electronic 3rd edition is freely available on author's site). |
}} (the electronic 3rd edition is freely available on author's site). |
||
*{{citation|last1=Harary|first1=Frank|last2=Norman|first2=Robert Z.|last3=Cartwright|first3=Dorwin|title=Structural Models: An Introduction to the Theory of Directed Graphs|place=New York|publisher=Wiley|year=1965}}. |
* {{citation|last1=Harary|first1=Frank|author-link1=Frank Harary|last2=Norman|first2=Robert Z.| last3=Cartwright|first3=Dorwin| title=Structural Models: An Introduction to the Theory of Directed Graphs| place=New York|publisher=Wiley| year=1965}}. |
||
* |
* [https://oeis.org/A000273 Number of directed graphs (or directed graphs) with n nodes] from [[On-Line Encyclopedia of Integer Sequences]] |
||
==External links== |
|||
{{Commons category|Directed graphs}} |
|||
{{Authority control}} |
|||
{{DEFAULTSORT:Directed Graph}} |
{{DEFAULTSORT:Directed Graph}} |
||
[[Category:Directed graphs]] |
[[Category:Directed graphs]] |
||
[[Category:Graph theory]] |
|||
[[Category:Graph data structures]] |
Revision as of 16:53, 23 June 2024
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 directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pair G = (V, A) where[1]
- V is a set whose elements are called vertices, nodes, or points;
- A is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.
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, links or lines.
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 arcs (namely, they allow the arc set to be a multiset). Sometimes these entities are called directed multigraphs (or multidigraphs).
On the other hand, the aforementioned definition allows a directed graph to have loops (that is, arcs that directly connect nodes with themselves), but some authors consider a narrower definition that does not allow directed graphs to have loops.[2]
Directed graphs without loops may be called simple directed graphs, while directed graphs with loops may be called loop-digraphs (see section Types of directed graph).
Types of directed graphs
Subclasses
- Symmetric directed graphs are directed graphs where all edges appear twice, one in each direction (that is, for every arrow that belongs to the digraph, the corresponding inverse arrow also belongs to it). (Such an edge is sometimes called "bidirected" and such graphs are sometimes called "bidirected", but this conflicts with the meaning for bidirected graphs.)
- 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.[2]
- Complete directed graphs are simple directed graphs where each pair of vertices is joined by a symmetric pair of directed arcs (it is equivalent to an undirected complete graph with the edges replaced by pairs of inverse arcs). It follows that a complete digraph is symmetric.
- Semicomplete multipartite digraphs are simple digraphs in which the vertex set is partitioned into sets such that for every pair of vertices x and y in different sets, there is an arc between x and y. There can be one arc between x and y or two arcs in opposite directions.[3]
- Semicomplete digraphs are simple digraphs where there is an arc between each pair of vertices. Every semicomplete digraph is a semicomplete multipartite digraph in a trivial way, with each vertex constituting a set of the partition.[4]
- Quasi-transitive digraphs are simple digraphs where for every triple x, y, z of distinct vertices with arcs from x to y and from y to z, there is an arc between x and z. There can be just one arc between x and z or two arcs in opposite directions. A semicomplete digraph is a quasi-transitive digraph. There are extensions of quasi-transitive digraphs called k-quasi-transitive digraphs.[5]
- Oriented graphs are directed graphs having no opposite pairs of directed 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 has no 2-cycle.[6] (This is not the only meaning of "oriented graph"; see Orientation (graph theory).)
- Tournaments are oriented graphs obtained by choosing a direction for each edge in undirected complete graphs. A tournament is a semicomplete digraph.[4]
- A directed graph is acyclic if it has no directed cycles. The usual name for such a digraph is directed acyclic graph (DAG).[7]
- Multitrees are DAGs in which there are no two distinct directed paths from the same starting vertex to the same ending vertex.
- Oriented trees or polytrees are DAGs formed by orienting the edges of trees (connected, acyclic undirected graphs).
- Rooted trees are oriented trees in which all edges of the underlying undirected tree are directed either away from or towards the root (they are called, respectively, arborescences or out-trees, and in-trees.
Digraphs with supplementary properties
- 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).[2]
- Flow networks are weighted directed graphs where two nodes are distinguished, a source and a sink.
- Rooted directed graphs (also known as flow graphs) are digraphs in which a vertex has been distinguished as the root.
- 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.
- 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.
- Flow graphs are digraphs associated with a set of linear algebraic or differential equations.
- State diagrams are directed multigraphs that represent finite state machines.
- 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.
- 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 FinVctKF(Q) 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.
Basic terminology
An arc (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 reachable from x, and x is said to be a predecessor of y. The arc (y, x) is called the reversed arc of (x, y).
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 arcs from vertex i to vertex j, and the diagonal entry aii is the number of loops at vertex i. The adjacency matrix of a directed graph is a logical matrix, and is unique up to permutation of rows and columns.
Another matrix representation for a directed graph is its incidence matrix.
See direction for more definitions.
Indegree and outdegree
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).
Let G = (V, E) and v ∈ V. The indegree of v is denoted deg−(v) and its outdegree is denoted deg+(v).
A vertex with deg−(v) = 0 is called a source, as it is the origin of each of its outcoming arcs. Similarly, a vertex with deg+(v) = 0 is called a sink, since it is the end of each of its incoming arcs.
The degree sum formula states that, for a directed graph,
If for every vertex v ∈ V, deg+(v) = deg−(v), the graph is called a balanced directed graph.[8]
Degree sequence
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)). The degree sequence is a directed graph invariant so isomorphic directed graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a directed graph; in some cases, non-isomorphic digraphs have the same degree sequence.
The directed graph realization problem is the problem of finding a directed graph with the degree sequence a given sequence of positive integer pairs. (Trailing pairs of zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the directed graph.) 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. This problem can either be solved by the Kleitman–Wang algorithm or by the Fulkerson–Chen–Anstee theorem.
Directed graph connectivity
A directed graph is weakly connected (or just connected[9]) if the undirected underlying graph obtained by replacing all directed edges of the graph with undirected edges is a connected graph.
A directed graph is strongly connected or strong if it contains a directed path from x to y (and from y to x) for every pair of vertices (x, y). The strong components are the maximal strongly connected subgraphs.
A connected rooted graph (or flow graph) is one where there exists a directed path to every vertex from a distinguished root vertex.
See also
- Binary relation
- Coates graph
- Directed Graph Markup Language
- DRAKON flowchart
- Flow chart
- Globular set
- Glossary of graph theory
- Graph Style Sheets
- Graph theory
- Graph (abstract data type)
- Network theory
- Orientation
- Preorder
- Topological sorting
- Transpose graph
- Vertical constraint graph
- Zero-weight cycle problem
Notes
- ^ Bang-Jensen & Gutin (2000). Bang-Jensen & Gutin (2018), Chapter 1.Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.
- ^ a b c Chartrand, Gary (1977). Introductory Graph Theory. Courier Corporation. ISBN 9780486247755. Archived from the original on 2023-02-04. Retrieved 2020-10-02.
- ^ Bang-Jensen & Gutin (2018), Chapter 7 by Yeo.
- ^ a b Bang-Jensen & Gutin (2018), Chapter 2 by Bang-Jensen and Havet.
- ^ Bang-Jensen & Gutin (2018), Chapter 8 by Galeana-Sanchez and Hernandez-Cruz.
- ^ Diestel (2005), Section 1.10.
- ^ Bang-Jensen & Gutin (2018), Chapter 3 by Gutin.
- ^ Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd., p. 460, ISBN 978-81-203-3842-5; Brualdi, Richard A. (2006), Combinatorial Matrix Classes, Encyclopedia of Mathematics and Its Applications, vol. 108, Cambridge University Press, p. 51, ISBN 978-0-521-86565-4.
- ^ Bang-Jensen & Gutin (2000) p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).
References
- Bang-Jensen, Jørgen; Gutin, Gregory (2000), Digraphs: Theory, Algorithms and Applications, Springer, ISBN 1-85233-268-9(the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009 ISBN 1-84800-997-6).
- Bang-Jensen, Jørgen; Gutin, Gregory (2018), Classes of Directed Graphs, Springer, ISBN 978-3319718408.
- Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7.
- Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6 (the electronic 3rd edition is freely available on author's site).
- Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley.
- Number of directed graphs (or directed graphs) with n nodes from On-Line Encyclopedia of Integer Sequences