Directed graph: Difference between revisions
i have removed the references Tags: Visual edit Mobile edit Mobile web edit |
Boomer Vial (talk | contribs) m Reverted edits by 197.237.118.16 (talk) to last version by BD2412 |
||
Line 2: | Line 2: | ||
[[File:Incidence matrix - directed graph.svg|thumb|Directed graph with corresponding incidence matrix.]] |
[[File:Incidence matrix - directed graph.svg|thumb|Directed graph with corresponding incidence matrix.]] |
||
In [[mathematics]], and more specifically in [[graph theory]], a '''directed graph''' (or '''digraph''') is a [[Graph (discrete mathematics)|graph]], or set of vertices connected by edges, where the edges have a direction associated with them. In formal terms, a directed graph is an ordered pair {{nobreak|1=''G'' = (''V'', ''A'')}} (sometimes {{nobreak|1=''G'' = (''V'', ''E'')}}) where |
In [[mathematics]], and more specifically in [[graph theory]], a '''directed graph''' (or '''digraph''') is a [[Graph (discrete mathematics)|graph]], or set of vertices connected by edges, where the edges have a direction associated with them. In formal terms, a directed graph is an ordered pair {{nobreak|1=''G'' = (''V'', ''A'')}} (sometimes {{nobreak|1=''G'' = (''V'', ''E'')}}) where<ref>{{harvtxt|Bang-Jensen|Gutin|2000}}. {{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 ''vertices'', ''nodes'', or ''points''; |
* ''V'' is a [[Set (mathematics)|set]] whose [[Element (mathematics)|elements]] are called ''vertices'', ''nodes'', or ''points''; |
||
* ''A'' is a set of [[ordered pair]]s of vertices, called ''arrows'', ''directed edges'' (sometimes simply ''edges'' with the corresponding set named ''E'' instead of ''A''), ''directed arcs'', or ''directed lines''. |
* ''A'' is a set of [[ordered pair]]s of vertices, called ''arrows'', ''directed edges'' (sometimes simply ''edges'' with the corresponding set named ''E'' instead of ''A''), ''directed arcs'', or ''directed lines''. |
||
Line 13: | Line 13: | ||
An arrow {{nobreak|(''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''. 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 arrow {{nobreak|(''y'', ''x'')}} is called the ''inverted arrow'' of {{nobreak|(''x'', ''y'')}}. |
An arrow {{nobreak|(''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''. 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 arrow {{nobreak|(''y'', ''x'')}} is called the ''inverted arrow'' of {{nobreak|(''x'', ''y'')}}. |
||
An [[Orientation (graph theory)|orientation]] of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. Any directed graph constructed this way is called an ''oriented graph''. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of {{nobreak|(''x'', ''y'')}} and {{nobreak|(''y'', ''x'')}} may be arrows of the graph). |
An [[Orientation (graph theory)|orientation]] of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. Any directed graph constructed this way is called an ''oriented graph''. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of {{nobreak|(''x'', ''y'')}} and {{nobreak|(''y'', ''x'')}} may be arrows of the graph).<ref>{{harvtxt|Diestel|2005}}, Section 1.10.</ref> |
||
A ''weighted directed graph'' is a directed graph with weights assigned to its arrows, similarly to a [[weighted graph]]. |
A ''weighted directed graph'' is a directed graph with weights assigned to its arrows, similarly to a [[weighted graph]]. |
||
Line 38: | Line 38: | ||
: <math>\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = |A|.</math> |
: <math>\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = |A|.</math> |
||
If for every vertex {{nobreak|''v''∈''V''}}, {{nobreak|1=deg<sup>+</sup>(''v'') = deg<sup>−</sup>(''v'')}}, the graph is called a ''balanced directed graph''. |
If for every vertex {{nobreak|''v''∈''V''}}, {{nobreak|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=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}}.</ref> |
||
==Degree sequence== |
==Degree sequence== |
||
Line 47: | Line 47: | ||
==Directed graph connectivity== |
==Directed graph connectivity== |
||
{{main|Connectivity (graph theory)}} |
{{main|Connectivity (graph theory)}} |
||
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 [[Connectivity (graph theory)|connected graph]]. 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 {{nobreak|{''x'', ''y''}}}. The ''strong components'' are the maximal strongly connected subgraphs. |
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 a directed path from ''y'' to ''x'' for every pair of vertices {{nobreak|{''x'', ''y''}}}. The ''strong components'' are the maximal strongly connected subgraphs. |
||
==Classes of directed graphs== |
==Classes of directed graphs== |
||
Line 59: | Line 59: | ||
A ''[[Tournament (mathematics)|tournament]]'' is an oriented graph obtained by choosing a direction for each edge in an undirected [[complete graph]]. |
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== |
|||
{{Commons category|Directed graphs}} |
|||
* [[Coates graph]] |
|||
* [[Flow chart]] |
|||
* [[Rooted graph]] |
|||
* [[Flow graph (mathematics)]] |
|||
* [[Mason graph]] |
|||
* [[Oriented graph]] |
|||
* [[Preorder]] |
|||
* [[Quiver (mathematics)|Quiver]] |
|||
* [[Signal-flow graph]] |
|||
* [[Transpose graph]] |
|||
* [[Vertical constraint graph]] |
|||
==Notes== |
|||
{{reflist}} |
|||
==References== |
|||
* {{Citation |
|||
| last1=Bang-Jensen | first1=Jørgen |
|||
| last2=Gutin | first2=Gregory |
|||
| title=directed graphs: Theory, Algorithms and Applications |
|||
| publisher=[[Springer Science+Business Media|Springer]] |
|||
| year=2000 |
|||
| isbn=1-85233-268-9 |
|||
| url=http://www.cs.rhul.ac.uk/books/dbook/ |
|||
}}<br>(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=Bondy | first1=John Adrian | authorlink1=John Adrian Bondy |
|||
| last2=Murty | first2=U. S. R. | authorlink2=U. S. R. Murty |
|||
| title=Graph Theory with Applications |
|||
| year=1976 |
|||
| publisher=North-Holland |
|||
| isbn=0-444-19451-7 |
|||
| url=http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html |
|||
}}. |
|||
* {{Citation |
|||
| last=Diestel | first=Reinhard |
|||
| title=Graph Theory |
|||
| publisher=[[Springer Science+Business Media|Springer]] |
|||
| year=2005 |
|||
| edition=3rd |
|||
| isbn=3-540-26182-6 |
|||
| url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ |
|||
}} (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 | title=Number of directed graphs (or directed graphs) with n nodes. | url=http://oeis.org/A000273}} |
|||
{{DEFAULTSORT:Directed Graph}} |
{{DEFAULTSORT:Directed Graph}} |
Revision as of 12:07, 29 February 2016
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph, or set of vertices connected by edges, where the edges have a direction associated with them. In formal terms, a directed graph is an ordered pair G = (V, A) (sometimes G = (V, E)) where[1]
- V is a set whose elements are called vertices, nodes, or points;
- 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.
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.
A directed graph is called a simple digraph if it has no multiple arrows (two or more edges that connect the same two vertices in the same direction) and no loops (edges that connect vertices to themselves). A directed graph is called a directed multigraph or multidigraph if it may have multiple arrows (and sometimes loops). In the latter case the arrow set forms a multiset, rather than a set, of ordered pairs of vertices.
Basic terminology
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. 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 arrow (y, x) is called the inverted arrow of (x, y).
An orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. Any directed graph constructed this way is called an oriented graph. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of (x, y) and (y, x) may be arrows of the graph).[2]
A weighted directed graph is a directed graph with weights assigned to its arrows, similarly to a weighted graph. In the context of graph theory, a weighted directed graph is often called a network.
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. The adjacency matrix of a directed graph is unique up to identical 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 incident arrows.
Similarly, a vertex with deg+(v) = 0 is called a sink.
If a vertex is neither a source nor a sink, it is called an internal.
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.[3]
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[4]) 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 a directed path from y to x for every pair of vertices {x, y}. The strong components are the maximal strongly connected subgraphs.
Classes of directed graphs
A symmetric digraph is a directed graph in which for every arrow that belongs to it, the corresponding inversed arrow also belongs to it. A symmetric, loopless directed graph is equivalent to an undirected graph with the edges replaced by pairs of inverse arrows; thus the number of edges is equal to the number of arrows halved.
A directed acyclic graph is a directed graph with no directed cycles. Special cases of directed acyclic graphs include multitrees (graphs in which no two directed paths from a single starting vertex meet back at the same ending vertex), oriented trees or polytrees (directed graphs formed by orienting the edges of undirected acyclic graphs), and rooted trees (oriented trees in which all edges of the underlying undirected tree are directed away from the roots).
A tournament is an oriented graph obtained by choosing a direction for each edge in an undirected complete graph.
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.
See also
- Coates graph
- Flow chart
- Rooted graph
- Flow graph (mathematics)
- Mason graph
- Oriented graph
- Preorder
- Quiver
- Signal-flow graph
- Transpose graph
- Vertical constraint graph
Notes
- ^ Bang-Jensen & Gutin (2000). Diestel (2005), Section 1.10. Bondy & Murty (1976), Section 10.
- ^ Diestel (2005), Section 1.10.
- ^ 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), directed graphs: 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). - 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.