En teoría de grafos , un grafo moral se usa 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 gráfico acíclico dirigido se forma agregando bordes entre todos los pares de nodos no adyacentes que tienen un hijo común, y luego haciendo que todos los bordes del gráfico no estén dirigidos. De manera equivalente, un gráfico moral de un gráfico acíclico dirigido G es un gráfico no dirigido en el que cada nodo del G original ahora está conectado a su manto de Markov . El nombre proviene del hecho de que, en un gráfico moral, se requiere que dos nodos que tienen un hijo común estén casados compartiendo una ventaja. [1]
La moralización también se puede aplicar a gráficos mixtos , llamados en este contexto "gráficos de cadena". En un gráfico de cadena, un componente conectado del subgráfico no dirigido se llama cadena. La moralización agrega un borde no dirigido entre dos vértices cualesquiera que tengan bordes salientes a la misma cadena, y luego olvida la orientación de los bordes dirigidos del gráfico.
Débilmente recursivamente simplicial
Un gráfico es débilmente recursivamente simplicial si tiene un vértice simplicial y el subgráfico después de eliminar un vértice simplicial y algunos bordes (posiblemente ninguno) entre sus vecinos es débilmente recursivamente simplicial. Un gráfico 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 recursivamente débil cuando no se elimina ningún borde durante el proceso de eliminación. Por lo tanto, un grafo de cuerdas también es moral. Pero un grafo moral no es necesariamente cordal. [2]
Reconociendo gráficos morales
A diferencia de los grafos cordales que pueden reconocerse en tiempo polinomial, Verma y Pearl (1993) demostraron que decidir si un grafo es moral o no es NP-completo.
Ver también
Referencias
- ^ Cowell, Robert G .; Dawid, A. Philip ; Lauritzen, Steffen L .; Spiegelhalter, David J. (1999). "3.2.1 Moralización" . Redes probabilísticas y sistemas expertos: métodos computacionales exactos para redes bayesianas . Springer-Verlag Nueva York. págs. 31–33. doi : 10.1007 / 0-387-22630-3_3 . ISBN 0-387-98767-3.
- ^ Cowell y col. (1999) , pág. 50.