En teoría de grafos , se utiliza un grafo moral para encontrar la forma no dirigida equivalente de un grafo acíclico dirigido . Es un paso clave del algoritmo del árbol de unión , utilizado en la propagación de creencias en modelos gráficos .
La contraparte moralizada de un grafo acíclico dirigido se forma añadiendo aristas entre todos los pares de nodos no adyacentes que tienen un hijo común y luego haciendo que todas las aristas del grafo no estén dirigidas. De manera equivalente, un grafo moral de un grafo acíclico dirigido G es un grafo no dirigido en el que cada nodo del G original ahora está conectado a su manta de Markov . El nombre se deriva del hecho de que, en un grafo moral, se requiere que dos nodos que tienen un hijo común estén unidos compartiendo una arista. [1]
La moralización también puede aplicarse a los grafos mixtos , llamados en este contexto "grafos en cadena". En un grafo en cadena, un componente conectado del subgrafo no dirigido se denomina cadena. La moralización agrega una arista no dirigida entre dos vértices cualesquiera que tengan aristas salientes hacia la misma cadena y luego olvida la orientación de las aristas dirigidas del grafo.
Un grafo es débilmente recursivamente simplicial si tiene un vértice simplicial y el subgrafo, después de eliminar un vértice simplicial y algunas aristas (posiblemente ninguna) entre sus vecinos, es débilmente recursivamente simplicial. Un grafo es moral si y solo si es débilmente recursivamente simplicial.
Un grafo cordal (también conocido como simplicial recursivo) es un caso especial de simplicial débilmente recursivo cuando no se elimina ninguna arista durante el proceso de eliminación. Por lo tanto, un grafo cordal también es moral. Pero un grafo moral no es necesariamente cordal. [2]
A diferencia de los gráficos cordales que pueden reconocerse en tiempo polinomial, Verma y Pearl (1993) demostraron que decidir si un gráfico es moral o no es NP-completo.