Para un grafo dirigido G , los términos converso [ 1] , transpuesto [ 2] o inverso [ 3 ] se usan para referirse a otro grafo dirigido con el mismo conjunto de vértices y los mismos arcos, pero la orientación de los arcos de este gráfica es opuesta a la orientación de los arcos de la gráfica G . Es decir, si el gráfico G contiene un arco (u,v) , entonces el gráfico inverso/transpuesto/opuesto del gráfico G contiene un arco (v,u) , y viceversa.
El nombre inversa surge porque la inversión de las flechas del arco corresponde a la inversión de una inferencia lógica en lógica. El término transpuesto proviene del álgebra porque la matriz de adyacencia de un gráfico dirigido transpuesto es la matriz transpuesta de la matriz de adyacencia del gráfico original.
No existe una opinión establecida sobre cuál de los términos es preferible.
Un grafo inverso se puede denotar como G' , G T , G R o de otra forma, dependiendo de la terminología adoptada en el artículo o libro.
Aunque matemáticamente la diferencia entre un gráfico y su gráfico transpuesto es pequeña, en informática la diferencia puede ser muy grande, dependiendo de la forma en que se represente el gráfico. Por ejemplo, para un gráfico web, es fácil determinar las conexiones salientes de los vértices, pero es difícil determinar las conexiones entrantes, mientras que para un gráfico inverso es todo lo contrario. Por lo tanto, para algoritmos en gráficos, a veces sería útil construir un gráfico inverso para llevar el gráfico a una forma que sea más adecuada para las operaciones que se aplican al gráfico. Un ejemplo de esto es el algoritmo de Kosaraju para componentes fuertemente acoplados , que aplica la búsqueda primero en profundidad dos veces , una para un gráfico dado y una segunda vez para su inversa.
Un gráfico sesgado simétrico es un gráfico isomorfo a su propio gráfico transpuesto a través de una forma especial de isomorfismo que empareja todos los vértices.
La relación inversa una relación binaria es una relación que invierte el orden de cada par de objetos relacionados. Si la relación se interpreta como un gráfico dirigido, entonces la relación inversa es el mismo objeto que el gráfico transpuesto. En particular, el orden dual de un orden parcial puede interpretarse como una transposición de un gráfico acíclico dirigido transitivamente cerrado .