Gráfico de transposição - Transpose graph
No estudo matemático e algorítmica da teoria gráfico , o inverso , transposta ou reverso de um grafo orientado G é outro gráfico dirigido no mesmo conjunto de vértices com todas as arestas invertida em comparação com a orientação dos bordos correspondentes em L . Ou seja, se G contém uma aresta, então o inverso / transposto / reverso de G contém uma aresta e vice-versa.
Notação
O nome converse surge porque a inversão das setas corresponde a tomar o inverso de uma implicação na lógica. O nome transposta é porque a matriz de adjacência do grafo direcionado transposta é a transposta da matriz de adjacência do grafo direcionado original.
Não há acordo geral sobre a terminologia preferida.
O inverso é denotado simbolicamente como G ' , G T , G R ou outras notações, dependendo de qual terminologia é usada e de qual livro ou artigo é a fonte da notação.
Formulários
Embora haja pouca diferença matematicamente entre um gráfico e sua transposta, a diferença pode ser maior na ciência da computação , dependendo de como um dado gráfico é representado . Por exemplo, para o gráfico da web , é fácil determinar os links de saída de um vértice, mas difícil determinar os links de entrada, enquanto na reversão deste gráfico o oposto é verdadeiro. Em algoritmos de gráfico , portanto, às vezes pode ser útil construir uma representação explícita da reversão de um gráfico, a fim de colocá-lo em uma forma que seja mais adequada para as operações realizadas nele. Um exemplo disso é o algoritmo de Kosaraju para componentes fortemente conectados , que aplica a primeira pesquisa de profundidade duas vezes, uma vez para o gráfico dado e uma segunda vez para sua reversão.
Conceitos relacionados
Um gráfico com simetria oblíqua é um gráfico isomórfico ao seu próprio gráfico transposto, por meio de um tipo especial de isomorfismo que emparelha todos os vértices.
A relação inversa de uma relação binária é a relação que inverte a ordem de cada par de objetos relacionados. Se a relação for interpretada como um gráfico direcionado, isso é a mesma coisa que a transposição do gráfico. Em particular, a ordem dual de uma ordem parcial pode ser interpretada desta forma como a transposição de um gráfico acíclico dirigido transitivamente fechado .