Transponer gráfico
En el estudio matemático y algorítmico de la teoría de grafos , el inverso , [1] transponer [2] o revertir [3] de un grafo dirigido G es otro grafo dirigido en el mismo conjunto de vértices con todos los bordes invertidos en comparación con la orientación. de los bordes correspondientes en G . Es decir, si G contiene un borde, entonces el inverso / transposición / reverso de G contiene un borde y viceversa.
El nombre inverso surge porque la inversión de flechas corresponde a tomar el inverso de una implicación en lógica. El nombre transposición se debe a que la matriz de adyacencia del gráfico dirigido por transposición es la transpuesta de la matriz de adyacencia del gráfico dirigido original.
Lo contrario se denota simbólicamente como G ' , G T , G R u otras notaciones, según la terminología que se use y el libro o artículo que sea la fuente de la notación.
Aunque hay poca diferencia matemática entre un gráfico y su transposición, la diferencia puede ser mayor en informática , dependiendo de cómo se represente un gráfico determinado . Por ejemplo, para el gráfico web , es fácil determinar los enlaces salientes de un vértice, pero es difícil determinar los enlaces entrantes, mientras que en la inversión de este gráfico ocurre lo contrario. En los algoritmos de gráficos , por lo tanto, a veces puede ser útil construir una representación explícita de la inversión de un gráfico, con el fin de poner el gráfico 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 primera búsqueda en profundidad dos veces, una vez al gráfico dado y una segunda vez a su inversión.
Un gráfico de simetría sesgada es un gráfico que es isomorfo a su propio gráfico de transposición, 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 gráfico dirigido, esto es lo mismo que la transposición del gráfico. En particular, el orden dual de un orden parcial se puede interpretar de esta manera como la transposición de un gráfico acíclico dirigido transitivamente cerrado .
