¿Existe un nombre para un operador que elimine el mayor número posible de aristas de un grafo manteniendo su cierre transitivo?

Question

Dado un grafo dirigido acíclico $G=(V,E)$ podemos calcular un gráfico $G'=(V,E')$ tal que:

1. $E'\subseteq E$ .
2. Si $u$ es accesible desde $v$ en $G$ entonces también es alcanzable en $G'$ .
3. Eliminar cualquier borde de $E'$ violaría (2) y afectaría a la alcanzabilidad.

¿Existe un nombre para la operación que da $G$ devuelve tales $G'$ ?

---

Por ejemplo, si $G=(\{1,2,3\},\{(1,2),(1,3),(2,3)\})$ obtenemos $G'=(\{1,2,3\},\{(1,2),(2,3)\})$ ?

Answer 1

El reducción transitiva . Para los grafos acíclicos dirigidos, la reducción transitiva es única, y es lo mismo que el "grafo mínimo equivalente" (que se ajusta más a su definición), y es lo mismo que el diagrama de Hasse de la relación de alcanzabilidad.

EDIT: Estoy asumiendo que $G$ es finito aquí - no hay reducción transitiva para el gráfico en $\mathbb N\cup\{\infty\}$ con arcos $i\to j$ si $i\leq j.$