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 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.

Although there is little difference mathematically between a graph and its transpose, the difference may be larger in computer science, depending on how a given graph is represented.

For instance, for the web graph, it is easy to determine the outgoing links of a vertex, but hard to determine the incoming links, while in the reversal of this graph the opposite is true.

An example of this is Kosaraju's algorithm for strongly connected components, which applies depth-first search twice, once to the given graph and a second time to its reversal.