Transpose graph
In the mathematical and algorithmic study of graph theory, the converse,[1] transpose[2] or reverse[3] of a directed graph G is another directed graph on the same set of vertices with all of the edges reversed compared to the orientation of the corresponding edges in G. That is, if G contains an edge (u, v) then the converse/transpose/reverse of G contains an edge (v, u) and vice versa.
Notation
The name converse arises because the reversal of arrows corresponds to taking the converse of an implication in logic. The name transpose is because the adjacency matrix of the transpose directed graph is the transpose of the adjacency matrix of the original directed graph.
There is no general agreement on preferred terminology.
The converse is denoted symbolically as G', GT, GR, or other notations, depending on which terminology is used and which book or article is the source for the notation.
Applications
Although there is little difference mathematically between a graph and its transpose, the difference may be larger in
Related concepts
A skew-symmetric graph is a graph that is isomorphic to its own transpose graph, via a special kind of isomorphism that pairs up all of the vertices.
The
See also
- Converse relation – Reversal of the order of elements of a binary relation
References
- ^ Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. MIT Press and McGraw-Hill., ex. 22.1–3, p. 530.
- , entry 2.24