Creo que lo que estás buscando es "transitivo reducción", que da a los más pequeños relación cuyo cierre transitivo es el mismo que el cierre transitivo de la relación.
Y esto me hace pensar, ¿por qué molestarse con el transitiva reducción cuando se puede tomar el cierre transitivo para empezar...es decir, ¿por qué preocuparse por el 'ruido' y sólo tiene que añadir en todos los desaparecidos transitiva arcos.
Si el ruido es tal que usted tiene -ciclos-... bueno, eso es todo un tro problema (¿cómo se sabe que el borde es el 'malo'?)
A partir de los comentarios, voy a agregar a mi respuesta. Creo que la pregunta realmente es algo como esto:
"Dado un gráfico acíclico dirigido, además de algunas caras nuevas (lo cual puede inducir ciclos), la devolución de algún tipo de poset (transitivo dirigida gráfico acíclico)".
Una vez que los ciclos se rompe, entonces uno puede tomar un cierre transitivo (algebraicamente, como te gusta por $A^* = I + A + A^2 + ... + A^n = (I - A)^{-1}$ (OK, me tiró reflexivo no demasiado).
Ahora la dificultad es la de deshacerse de los ciclos. No hay manera de saber cuáles son espurios, así que tienes que arbitrariamente tirar de los bordes para deshacerse de los ciclos. Un enfoque ingenuo sería DFS repetidamente (esto no es particularmente algebraicas), quitar el borde en el que un ciclo es reconocido, hasta que no hay más ciclos se encuentran. Esto no es muy elegante ya que se puede quitar más bordes que fuera necesario (para inducir acyclicity).
La siguiente idea es tratar de deshacerse de la -menor - bordes posible, que la parte superior de mi cabeza suena muy NP-completos, que no me molesta (puede alguien confirmar o no?).
Cuando eso sucede, se puede sacar el teórico sombrero y acaba de ser práctico...¿cuántos falsos bordes se puede esperar? Si son muy pocos, yo diría que ir con el DFS enfoque, no habrá muchas entrelazamiento de los ciclos.
Usted puede estar preocupado de que tal cosa va a resultar en una taxonomía que no es ... a la derecha. Decir, un perro es un animal es un beagle (que quería que el algoritmo para desechar el falso 'de un animal es un beagle' y no 'un beagle es un perro'). Pero si el algoritmo es ser anónimo, no puede (no es posible) saber cual es el mejor borde para quitar (en un ciclo, no borde se distingue). Es decir, el mal ejemplo que he dado es inevitable en una configuración general.
PS: desde que nos mudamos a tratar con los ciclos en lugar de transitividad (desde cualquier gráfico acíclico tiene un acíclicos cierre transitivo), ahora me doy cuenta de que hay un 'estadística', por 'circunferencia', la longitud de la más grande de ciclo (con un gráfico acíclico tener una infinita circunferencia). Y ...no sé de una fracción analógica a la circunferencia. Ver Scheinerman, la fracción de la Teoría de grafos para las ideas.
PPS: estoy seguro de que hay heurística que podría ayudar a elegir mal los bordes (bordes que desea quitar), por ejemplo, para hacer que la jerarquía más ... piramidal... intenta minimizar el número de 'top' de los nodos (nodos con no en los bordes) o intentar maximizar el número de descendientes de estos nodos superiores. Esto puede ser caro (para cada borde en un ciclo, calcular descendientes para todo el mundo, y luego comparar estos resultados y elegir la mejor).
