Reducción de una relación a un orden parcial

Question

¿Existe algún método general para reducir una relación reflexiva a un orden parcial en un conjunto finito?

En particular, dada una relación R definido en un conjunto finito, que es reflexivo xRx y para todo x $\ne$ y, xRy o yRx pero no ambos; ¿existe una forma mínima/óptima de llegar a un orden parcial eliminando (x,y) pares de la relación R ?

Answer 1

Es obvio que podemos identificar una relación reflexiva $R\subset V\times V$ con un dígrafo $G=(V,E)$ donde $E=R \setminus \{(x,x)\}_{x\in V}$ (más explícitamente, existe una arista $x \rightarrow y$ siempre que $xRy$ et $x\neq y$ ).

Ahora, eliminar mínimamente los ciclos para terminar con un gráfico $G^\prime$ . La relación correspondiente $R^\prime$ todavía no es un orden parcial, ya que podría no satisfacer la transitividad.

Visite $G^{\prime\prime}$ añadiendo todas las aristas para satisfacer la transitividad (es decir, si hay aristas $x_1 \rightarrow x_2$ et $x_2 \rightarrow x_3$ añade el borde $x_1 \rightarrow x_3$ ). La relación correspondiente $R^{\prime\prime}$ es lo que está buscando.

(Recomiendo hacer algunos dibujos para entender lo que he dicho, suponiendo que no haya cometido ningún error).