En el campo matemático de la teoría de grafos , una reducción transitiva de un grafo dirigido D es otro grafo dirigido con los mismos vértices y la menor cantidad posible de aristas, de modo que para todos los pares de vértices v , w existe un camino (dirigido) de v a w en D si y solo si dicho camino existe en la reducción. Las reducciones transitivas fueron introducidas por Aho, Garey y Ullman (1972), quienes proporcionaron límites estrictos a la complejidad computacional de construirlas.
Más técnicamente, la reducción es un gráfico dirigido que tiene la misma relación de alcanzabilidad que D. De manera equivalente, D y su reducción transitiva deberían tener el mismo cierre transitivo entre sí, y la reducción transitiva de D debería tener la menor cantidad posible de aristas entre todos los gráficos con esa propiedad.
La reducción transitiva de un grafo acíclico dirigido finito (un grafo dirigido sin ciclos dirigidos ) es única y es un subgrafo del grafo dado. Sin embargo, la unicidad falla para grafos con ciclos (dirigidos), y para grafos infinitos ni siquiera está garantizada la existencia.
El concepto estrechamente relacionado de un grafo equivalente mínimo es un subgrafo de D que tiene la misma relación de alcanzabilidad y la menor cantidad posible de aristas. [1] La diferencia es que una reducción transitiva no tiene que ser un subgrafo de D . Para grafos acíclicos dirigidos finitos , el grafo equivalente mínimo es el mismo que la reducción transitiva. Sin embargo, para grafos que pueden contener ciclos, los grafos equivalentes mínimos son NP-difíciles de construir, mientras que las reducciones transitivas se pueden construir en tiempo polinomial .
La reducción transitiva se puede definir para una relación binaria abstracta en un conjunto , interpretando los pares de la relación como arcos en un gráfico dirigido.
La reducción transitiva de un grafo dirigido finito G es un grafo con el menor número posible de aristas que tiene la misma relación de alcanzabilidad que el grafo original. Es decir, si hay un camino desde un vértice x hasta un vértice y en el grafo G , también debe haber un camino desde x hasta y en la reducción transitiva de G , y viceversa. Específicamente, si hay algún camino desde x hasta y, y otro desde y hasta z, entonces no puede haber ningún camino desde x hasta z que no incluya y. La transitividad para x, y y z significa que si x < y e y < z, entonces x < z. Si para cualquier camino desde y hasta z hay un camino x hasta y, entonces hay un camino x hasta z; sin embargo, no es cierto que para cualquier camino x hasta y y x hasta z haya un camino y hasta z, y por lo tanto cualquier arista entre los vértices x y z se excluye bajo una reducción transitiva, ya que representan recorridos que no son transitivos. La siguiente imagen muestra dibujos de gráficos correspondientes a una relación binaria no transitiva (a la izquierda) y su reducción transitiva (a la derecha).
La reducción transitiva de un grafo acíclico dirigido finito G es única y está formada por las aristas de G que forman el único camino entre sus extremos. En particular, siempre es un subgrafo generador del grafo dado. Por esta razón, la reducción transitiva coincide con el grafo equivalente mínimo en este caso.
En la teoría matemática de las relaciones binarias , cualquier relación R sobre un conjunto X puede ser considerada como un grafo dirigido que tiene como conjunto vértice al conjunto X y que tiene un arco xy para cada par ordenado de elementos que están relacionados en R. En particular, este método permite reinterpretar los conjuntos parcialmente ordenados como grafos acíclicos dirigidos, en los que hay un arco xy en el grafo siempre que exista una relación de orden x < y entre el par dado de elementos del orden parcial. Cuando la operación de reducción transitiva se aplica a un grafo acíclico dirigido que se ha construido de esta manera, genera la relación de recubrimiento del orden parcial, que frecuentemente se expresa visualmente mediante un diagrama de Hasse .
La reducción transitiva se ha utilizado en redes que pueden representarse como gráficos acíclicos dirigidos (por ejemplo, gráficos de citas o redes de citas ) para revelar diferencias estructurales entre redes. [2]
En un grafo finito que tiene ciclos, la reducción transitiva puede no ser única: puede haber más de un grafo en el mismo conjunto de vértices que tenga un número mínimo de aristas y tenga la misma relación de alcanzabilidad que el grafo dado. Además, puede darse el caso de que ninguno de estos grafos mínimos sea un subgrafo del grafo dado. Sin embargo, es sencillo caracterizar los grafos mínimos con la misma relación de alcanzabilidad que el grafo dado G . [3] Si G es un grafo dirigido arbitrario, y H es un grafo con el número mínimo posible de aristas que tienen la misma relación de alcanzabilidad que G , entonces H consta de
El número total de aristas en este tipo de reducción transitiva es entonces igual al número de aristas en la reducción transitiva de la condensación, más el número de vértices en componentes fuertemente conexos no triviales (componentes con más de un vértice).
Los bordes de la reducción transitiva que corresponden a los bordes de condensación siempre pueden elegirse como subgrafos del grafo G dado . Sin embargo, el ciclo dentro de cada componente fuertemente conectado solo puede elegirse como subgrafo de G si ese componente tiene un ciclo hamiltoniano , algo que no siempre es cierto y es difícil de comprobar. Debido a esta dificultad, es NP-difícil encontrar el subgrafo más pequeño de un grafo G dado con la misma alcanzabilidad (su grafo equivalente mínimo). [3]
Aho et al. proporcionan el siguiente ejemplo para demostrar que en grafos infinitos , incluso cuando el grafo es acíclico, puede no existir una reducción transitiva. Formen un grafo con un vértice para cada número real , con una arista siempre que como números reales. Entonces este grafo es infinito, acíclico y transitivamente cerrado. Sin embargo, en cualquier subgrafo que tenga el mismo cierre transitivo, cada arista restante puede eliminarse sin cambiar el cierre transitivo, porque todavía debe quedar un camino desde a a través de cualquier vértice entre ellos. Por lo tanto, entre los subgrafos con el mismo cierre transitivo, ninguno de estos subgrafos es mínimo: no hay reducción transitiva. [3]
Como muestran Aho et al., [3] cuando la complejidad temporal de los algoritmos de grafos se mide solo como una función del número n de vértices en el grafo, y no como una función del número de aristas, el cierre transitivo y la reducción transitiva de grafos acíclicos dirigidos tienen la misma complejidad. Ya se había demostrado que el cierre transitivo y la multiplicación de matrices booleanas de tamaño n × n tenían la misma complejidad entre sí, [4] por lo que este resultado coloca la reducción transitiva en la misma clase. Los mejores algoritmos exactos para la multiplicación de matrices , a partir de 2023, toman tiempo O( n 2.371552 ), [5] y esto da el límite de tiempo más rápido conocido en el peor de los casos para la reducción transitiva en grafos densos, aplicándolo a matrices sobre los números enteros y mirando las entradas distintas de cero en el resultado.
Para demostrar que la reducción transitiva es tan fácil como el cierre transitivo, Aho et al. se basan en la equivalencia ya conocida con la multiplicación de matrices booleanas. Dejan que A sea la matriz de adyacencia del grafo acíclico dirigido dado, y B sea la matriz de adyacencia de su cierre transitivo (calculado utilizando cualquier algoritmo de cierre transitivo estándar). Entonces, una arista uv pertenece a la reducción transitiva si y solo si hay una entrada distinta de cero en la fila u y la columna v de la matriz A , y hay una entrada cero en la misma posición del producto matricial AB . En esta construcción, los elementos distintos de cero de la matriz AB representan pares de vértices conectados por caminos de longitud dos o más. [3]
Para demostrar que la reducción transitiva es tan difícil como el cierre transitivo, Aho et al. construyen a partir de un grafo acíclico dirigido dado G otro grafo H , en el que cada vértice de G se reemplaza por un camino de tres vértices, y cada arista de G corresponde a una arista en H que conecta los vértices medios correspondientes de estos caminos. Además, en el grafo H , Aho et al. añaden una arista desde el inicio de cada camino hasta el final de cada camino. En la reducción transitiva de H , hay una arista desde el inicio del camino para u hasta el final del camino para v , si y solo si la arista uv no pertenece al cierre transitivo de G . Por lo tanto, si la reducción transitiva de H se puede calcular de manera eficiente, el cierre transitivo de G se puede leer directamente de ella. [3]
Cuando se miden tanto en términos del número n de vértices como del número m de aristas en un grafo acíclico dirigido, las reducciones transitivas también se pueden encontrar en tiempo O( nm ), un límite que puede ser más rápido que los métodos de multiplicación de matrices para grafos dispersos . Para ello, aplique un algoritmo de ruta más larga en el tiempo lineal en el grafo acíclico dirigido dado, para cada posible elección de vértice inicial. De las rutas más largas calculadas, mantenga solo aquellas de longitud uno (una sola arista); en otras palabras, mantenga aquellas aristas ( u , v ) para las que no existe otra ruta de u a v . Este límite de tiempo O( nm ) coincide con la complejidad de construir cierres transitivos mediante el uso de búsqueda en profundidad o búsqueda en amplitud para encontrar los vértices alcanzables desde cada elección de vértice inicial, por lo que nuevamente con estas suposiciones, los cierres transitivos y las reducciones transitivas se pueden encontrar en la misma cantidad de tiempo.
Para un gráfico con n vértices, m aristas y r aristas en la reducción transitiva, es posible encontrar la reducción transitiva utilizando un algoritmo sensible a la salida en una cantidad de tiempo que depende de r en lugar de m . El algoritmo es: [6]
El ordenamiento de los bordes en el bucle interno se puede obtener utilizando dos pases de ordenamiento por conteo u otro algoritmo de ordenamiento estable para ordenar los bordes, primero por la numeración topológica de su vértice final y segundo por su vértice inicial. Si los conjuntos se representan como matrices de bits , cada operación de unión de conjuntos se puede realizar en tiempo O ( n ), o más rápido utilizando operaciones bit a bit . El número de estas operaciones de conjunto es proporcional al número de bordes de salida, lo que lleva al límite de tiempo general de O ( nr ). Los conjuntos alcanzables obtenidos durante el algoritmo describen el cierre transitivo de la entrada. [6]
Si el gráfico se da junto con una partición de sus vértices en k cadenas (subconjuntos alcanzables por pares), este tiempo se puede reducir aún más a O ( kr ), representando cada conjunto alcanzable de manera concisa como una unión de sufijos de cadenas. [7]
