Reverse Graph on:
[Wikipedia]
[Google]
[Amazon]
In the mathematical and algorithmic study of
In the mathematical and algorithmic study of graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the converse, transpose or reverse, entry 2.24 of a directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
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 . That is, if contains an edge then the converse/transpose/reverse of contains an edge and vice versa.
Notation
The name arises because the reversal of arrows corresponds to taking theconverse
Converse may refer to:
Mathematics and logic
* Converse (logic), the result of reversing the two parts of a definite or implicational statement
** Converse implication, the converse of a material implication
** Converse nonimplication, a logical c ...
of an implication in logic. The name is because the adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
of the transpose directed graph is the transpose
In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations).
The tr ...
of the adjacency matrix of the original directed graph.
There is no general agreement on preferred terminology.
The converse is denoted symbolically as , , , 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 incomputer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, depending on how a given graph is represented. For instance, for the web graph The webgraph describes the directed links between pages of the World Wide Web. A graph, in general, consists of several vertices, some pairs connected by edges. In a directed graph, edges are directed lines or arcs. The webgraph is a directed 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 algorithm
The following is a list of well-known algorithms along with one-line descriptions for each.
Automated planning
Combinatorial algorithms
General combinatorial algorithms
* Brent's algorithm: finds a cycle in function value iterations using on ...
s, 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
In computer science, Kosaraju-Sharir's algorithm (also known as Kosaraju's algorithm) is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to S. Rao Kosaraju and Micha Sha ...
for strongly connected components, which applies depth-first search twice, once to the given graph and a second time to its reversal.
Related concepts
Askew-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 reversing all of its edges, under an isomorphism that is an involution without any fixed p ...
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
In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent&n ...
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
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...
can be interpreted in this way as the transposition of a transitively-closed directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...
.
See also
*References
{{reflist Graph operations Directed graphs