Grafo transpuesto

En el estudio matemático y algorítmico de la teoría de grafos , el recíproco , ^{[ 1 ]} transpuesto ^{[ 2 ]} o inverso ^{[ 3 ]} de un grafo dirigido G es otro grafo dirigido sobre 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 el recíproco/transpuesto/inverso de G contiene una arista ( v , u ) y viceversa.

El nombre «converso» surge porque la inversión de las flechas corresponde a tomar el recíproco de una implicación en lógica. El nombre «transpuesto» 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 consenso general sobre la terminología preferida.

Lo contrario se denota simbólicamente como G' , GT , GR u otras notaciones, dependiendo de la terminología que se utilice y del libro o artículo que sea la fuente de la ^{notación .}

Aunque matemáticamente hay poca diferencia entre un grafo y su transpuesta, en informática la diferencia puede ser mayor , dependiendo de cómo se represente un grafo dado . 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 transformarlo en una forma más adecuada para las operaciones que se realizan sobre él. Un ejemplo de esto es el algoritmo de Kosaraju para componentes fuertemente conexas , que aplica la búsqueda en profundidad dos veces: una vez al grafo dado y una segunda vez a su inversión.

Un grafo antisimétrico es un grafo isomorfo a su propio grafo transpuesto, mediante un tipo especial de isomorfismo que empareja todos los vértices.

La relación inversa de una relación binaria es aquella que invierte el orden de cada par de objetos relacionados. Si la relación se interpreta como un grafo dirigido, esto equivale a la transpuesta del grafo. En particular, el orden dual de un orden parcial puede interpretarse de esta manera como la transposición de un grafo dirigido acíclico transitivamente cerrado .

• Relación inversa : Inversión del orden de los elementos de una relación binaria.