Transpose graph

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.

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 transposed directed graph is the transpose of the adjacency matrix of the original directed graph. The name "reverse" is obvious. 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.

References

  1. ^ Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley .
  2. ^ Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L.. Introduction to Algorithms. MIT Press and McGraw-Hill. , ex. 22.1–3, p. 530.
  3. ^ Essam, John W.; Fisher, Michael E. (1970), "Some basic definitions in graph theory", Review of Modern Physics 42 (2): 271–288, doi:10.1103/RevModPhys.42.271 , entry 2.24, p. 275.


Stub icon This combinatorics-related article is a stub. You can help Wikipedia by expanding it.