Contracción transitiva
En matemáticas , la reducción transitiva de una relación binaria R sobre un conjunto X es la relación mínima sobre X tal que la clausura transitiva coincide con la clausura transitiva de R. Si la clausura transitiva de R es antisimétrica y finita , entonces es única. Sin embargo, ni la existencia ni la unicidad están garantizadas en el caso general.
Ejemplo
En teoría de grafos, cualquier relación binaria R sobre X puede entenderse como un grafo dirigido ( V , A ), donde V = X son los vértices y A = R son los arcos del grafo. La reducción transitiva de un gráfico a veces se denomina representación mínima . Las siguientes figuras representan una relación no transitiva (izquierda) y su contracción transitiva (derecha).
La contracción transitiva de un gráfico acíclico dirigido finito es única.
Algoritmos de reducción transitiva
La reducción transitiva de una relación sin ciclos se puede encontrar usando su cierre transitivo :
Aquí significa relación de composición .
Aho, Garey y Ullman (1972), quienes acuñaron el término "contracción transitiva" en el sentido descrito aquí, también establecieron una conexión entre el cierre transitivo y la contracción:
- para definir una contracción transitiva, extendieron el hallazgo de una clausura transitiva por ciclos de procesamiento;
- mostraron cómo obtener una clausura transitiva a partir de una contracción transitiva;
- demostraron que encontrar una reducción transitiva y un cierre tienen la misma complejidad computacional .
La utilidad tred en Graphviz [1] realiza la reducción de gráficos transitivos mediante la búsqueda en profundidad .
Estructura de datos extensible
Uno de los problemas mejor estudiados en la teoría de grafos computacionales es el almacenamiento de un historial consistente de cierres transitivos de grafos cuando se insertan o eliminan vértices y arcos. En 1987, JA La Poutré y Jan van Leeuwen describieron, en su obra frecuentemente citada Mantenimiento de cierres transitivos y reducciones transitivas de gráficos , un algoritmo de almacenamiento de historial tanto para el cierre como para la reducción del gráfico. [2]
El algoritmo utiliza
O(|E nuevo ||V|)tiempo para la inserción secuencial de arcos y
O(|E antiguo ||V|+|E antiguo | 2 )para el borrado secuencial, donde E antiguo es el conjunto de arcos antes de la inserción o borrado y E nuevo después. Para gráficos en los que no hay ciclos, la eliminación requiere solo
O(|E antiguo ||V|)tiempo.
Véase también
Enlaces
- ^ Investigación de laboratorios de AT&T - Herramientas de software . Consultado el 15 de enero de 2013. Archivado desde el original el 28 de enero de 2013.
- ↑ CiteSeerX - Mantenimiento de cierres transitivos y reducciones transitivas de gráficos . Consultado el 15 de enero de 2013. Archivado desde el original el 28 de enero de 2013.
Notas
- A. Aho, M. Garey, J. Ullman. La reducción transitiva de un grafo dirigido // SIAM Journal on Computing : diario. - 1972. - junio ( vol. 1 , no. 2 ). - P. 131-137 . -doi : 10.1137/ 0201008 .
Enlaces
- Mathworld: reducción transitiva
- E.Reingold, Yu.Nivergelt, N.Deo ALGORITMOS COMBINATORIALES. TEORÍA Y PRÁCTICA M.: Mir, 1980, 476 págs.