Usuario:SrMateos/Taller
Reducción Transitiva [editar]
En Matemáticas, la reducción transitiva de un grafo dirigido G es otro grafo dirigido con el mismo número vértices y el mínimo número de aristas posible, tal que para todo par de vértices v, w existe un camino (dirigido) desde v hasta w en G si y solo si ese camino existe en la reducción. La reducción transitiva es un concepto que fue introducido por Aho, Garey y Ullman (1972), quien proporcionó gran cantidad de información acerca de los límites de la complejidad computacional requerida para hallarlas.
Más en concreto, la reducción consiste en un grafo dirigido que tiene las mismas relaciones de accesibilidad que el grafo G. De forma equivalente, G y su reducción transitiva han de tener la misma clausura transitiva, y la reducción transitiva de G, ha de tener el mínimo número de aristas del conjunto de grafos con dicha propiedad.
La reducción transitiva de un grafo acíclico dirigido finito es única, y es un subgrafo del grafo dado. Sin embargo, la unicidad de la reducción transitiva no se mantiene para los grafos cíclicos dirigidos, y por otra parte, para grafos infinitos, ni si quiera se puede garantizar la existencia de la reducción. La reducción transitiva de un grafo acíclico dirigido finito es única, y es un subgrafo del grafo dado. Sin embargo, la unicidad de la reducción transitiva no se mantiene para los grafos cíclicos dirigidos, y por otra parte, para grafos infinitos, ni si quiera se puede garantizar la existencia de la reducción.
Un concepto parecido al de la reducción transitiva, es el de grafo mínimo equivalente, el cual es un subgrafo de G que tiene la misma relación de accesibilidad que este, y el mínimo número de aristas posible[1]. La diferencia radica en que la reducción transitiva de un grafo no tiene por qué ser un subgrafo del original G. Para grafos acíclicos dirigidos, la reducción resulta ser la misma, sin embargo, para grafos que contengan ciclos, esto no se mantiene. Por otra parte, el grafo mínimo equivalente de un grafo dirigido cíclico tienen una complejidad NP-hard a la hora de ser hallado, mientras que la reducción transitiva del grafo puede ser hallada en tiempo polinomial.
Complejidad[editar]
Como Aho et al.[2] nos muestran, cuando la complejidad temporal de los algoritmos de un grafo se estima únicamente en función del número n de vertices del grafo, y no en función del número de aristas, la clausura transitiva y la reducción transitiva del grafo dirigido acíclico tienen la misma complejidad. Ya se ha demostrado que la clausura transitiva y la multiplicación de matrices booleanas de tamaño n × n tienen la misma complejidad[3], así que esto nos lleva a poner la reducción transitiva al mismo nivel. Los algoritmos más eficientes actualmente conocidos para la multiplicación de una matriz, son de 2015 y tienen una complejidad de O(n2.3729), que nos da el el mejor tiempo conocido para el peor caso en cuestión de complejidad temporal, para la reducción transitiva de grafos densos.
Computación de la reducción transitiva haciendo uso de la clausura transitiva.[editar]
Con el objetivo de probar que la reducción transitiva es igual de tiene la misma complejidad computacional que la reducción transitiva, Aho et al. hacen uso de la anteriormente conocida equivalencia con la multiplicación de matrices booleanas. Comienzan por establecer A como la matriz de adyacencia del grafo dirigido, y B como la matriz de adyacencia de la clausura transitiva (que puede ser hallada mediante el uso de cualquier algoritmo de computación de una clausura transitiva). Después se define una arista uv perteneciente a la reducción transitiva si y solo si hay un valor distinto de cero en la fila y u y la columna v de la matriz A, y si hay un cero en la misma posición de la matriz resultante de multiplicar A y B. En esta estructura, los elementos distintos de cero de la matriz AB representan pares de vértices conectados por caminos de longitud mayor o igual que 2.
Computación de la clausura transitiva haciendo uso de la reducción transitiva[editar]
Con el objetivo de probar que la complejidad de la reducción transitiva es la misma que la de la clausura transitiva, Aho et al partiendo de digrafo acíclico G dado, construyen otro grafo H, tal que todo vértice de G es reemplazado por un camino de 3 vértices, y toda arista de G tiene su correspondencia en H con las distintas aristas que conectan los vértices de este camino. En adición, en el grafo H, Aho et al. añaden una arista que va desde el inicio del camino hasta el final de este. En la reducción transitiva de G, hay una arista desde el inicio del camino, que es el vértice u, hasta el final de este, que es el vértice v, sí y solo si la arista uv no pertenece a la clausura transitiva de G. Por tanto, si la reducción transitiva de H puede ser computada de forma eficiente, la clausura transitiva de G puede ser encontrada de la reducción.
Computación de la reducción transitiva para grafos de poca densidad[editar]
Conocidos el número de vértices n y el número de aristas m de un grafo dirigido acíclico, la reducción transitiva puede ser hallada en un tiempo O(nm), el cual puede ser más rápido que algunos
métodos de multiplicación de matrices booleanas, sin embargo, estos métodos solo son aplicables de forma eficiente para grafos de baja densidad, es decir, cuando hay un número
de aristas m muy pequeño en comparación con el número de vértices n. Para ello, aplicamos un '''algoritmo de búsqueda del camino más corto''' en '''tiempo lineal''' al grafo dirigido acíclico,
para todo vértice de inicio posible. Para los caminos resultantes más largos, nos quedamos con aquellos de longitud uno (de una sola arista); en otras palabras, nos quedamos con aquellas
aristas (u,v) para las cuales no existe otro camino. Esta complejidad O(nm) se corresponde con la complejidad resultante de construir clausuras transitivas haciendo uso de
búsquedas en profundidad o búsquedas en anchura para encontrar los vértices que son accesibles desde cada uno de los vértices de inicio. De esta forma, podemos concluir que las clausuras transitivas y las reducciones transitivas pueden ser encontradas en el mismo tiempo.
Referencias[editar]
- Esta obra contiene una traducción total derivada de «Transitive reduction» de Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.
- ↑ Moyles, Dennis M.; Thompson, Gerald L. (1969-07-XX). «An Algorithm for Finding a Minimum Equivalent Graph of a Digraph». Journal of the ACM 16 (3): 455-460. ISSN 0004-5411. doi:10.1145/321526.321534. Consultado el 20 de abril de 2021.
- ↑ Aho, A. V.; Garey, M. R.; Ullman, J. D. (1972-06-XX). «The Transitive Reduction of a Directed Graph». SIAM Journal on Computing 1 (2): 131-137. ISSN 0097-5397. doi:10.1137/0201008. Consultado el 20 de abril de 2021.
- ↑ «V A Tolomasov et al, kristalogr, 15 (6), 1970, 1233–1238 (in Russian).». Vacuum 21 (10): 499. 1971-10-XX. ISSN 0042-207X. doi:10.1016/0042-207x(71)92300-1. Consultado el 20 de abril de 2021.