En el estudio matemático y algorítmico de la teoría de grafos , la inversa , [1] transpuesta [2] o inversa [3] de un grafo dirigido G es otro grafo dirigido en el mismo conjunto de vértices con todas las aristas invertidas en comparación con la orientación de las aristas correspondientes en G. Es decir, si G contiene una arista ( u , v ), entonces la inversa/transpuesta/inversa de G contiene una arista ( v , u ) y viceversa.
El nombre de recíproco surge porque la inversión de las flechas corresponde a tomar el recíproco de una implicación en lógica. El nombre de transposición se debe a que la matriz de adyacencia del grafo dirigido transpuesto es la transpuesta de la matriz de adyacencia del grafo dirigido original.
No existe un acuerdo general sobre la terminología preferida.
El inverso se denota simbólicamente como G' , G T , G R u otras notaciones, dependiendo de la terminología utilizada y de qué libro o artículo sea la fuente de la notación.
Aunque matemáticamente hay poca diferencia entre un grafo y su transpuesta, la diferencia puede ser mayor en informática , dependiendo de cómo se represente un grafo determinado . Por ejemplo, para el grafo web , es fácil determinar los enlaces salientes de un vértice, pero difícil determinar los enlaces entrantes, mientras que en la inversión de este grafo ocurre lo contrario. Por lo tanto, en los algoritmos de grafos , a veces puede ser útil construir una representación explícita de la inversión de un grafo, para poner el grafo en una forma que sea más adecuada para las operaciones que se realizan en él. Un ejemplo de esto es el algoritmo de Kosaraju para componentes fuertemente conectados , que aplica la búsqueda en profundidad dos veces, una al grafo dado y una segunda a su inversión.
Un gráfico antisimétrico es un gráfico que es isomorfo a su propio gráfico transpuesto, a través de un tipo especial de isomorfismo que empareja todos los vértices.
La relación inversa de una relación binaria es la relación que invierte el orden de cada par de objetos relacionados. Si la relación se interpreta como un grafo dirigido, esto es lo mismo que la transposición del grafo. En particular, el orden dual de un orden parcial puede interpretarse de esta manera como la transposición de un grafo acíclico dirigido transitivamente cerrado .