📑 Table of Contents▼
A graph and its transpose

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

edit

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

edit

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. In graph algorithms, therefore, it may sometimes be useful to construct an explicit representation of the reversal of a graph, in order to put the graph into a form which is more suitable for the operations being performed on it. 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.

edit

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 converse relation of a binary relation is the relation that reverses the ordering of each pair of related objects. If the relation is interpreted as a directed graph, this is the same thing as the transpose of the graph. In particular, the dual order of a partial order can be interpreted in this way as the transposition of a transitively-closed directed acyclic graph.

See also

edit

References

edit
  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", Reviews of Modern Physics, 42 (2): 275, Bibcode:1970RvMP...42..271E, doi:10.1103/RevModPhys.42.271, entry 2.24

📚 Artikel Terkait di Wikipedia

Kosaraju's algorithm

transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.

Glossary of graph theory

graph that is its own transitive closure; it exists only for comparability graphs. transpose The transpose graph of a given directed graph is a graph

Graph operations

graph from an initial one by a complex change, such as: transpose graph; complement graph; line graph; graph minor; graph rewriting; power of graph;

Directed graph

Node ordering for directed acyclic graphs Transpose graph – Directed graph with reversed edges Vertical constraint graph Zero-weight cycle problem Bang-Jensen

Laplacian matrix

adjacency matrix A {\displaystyle A} of the original directed graph and its matrix transpose A T {\displaystyle A^{T}} , where the zero and one entries of

Skew-symmetric graph

In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by

Converse relation

(order theory) – Term in the mathematical area of order theory Transpose graph – Directed graph with reversed edges Ernst Schröder, (1895), Algebra der Logik

Strongly connected component

explores them if not. The second depth-first search is on the transpose graph of the original graph, and each recursive exploration finds a single new strongly