{{CS1 config|mode=cs1}} In graph theory, a '''moral graph''' is used to find the equivalent undirected form of a directed acyclic graph. It is a key step of the junction tree algorithm, used in belief propagation on graphical models.
{{multiple image|align=right |image1=MoralGraph-DAG1.svg|caption1=A directed acyclic graph |image2=Moralized graph1.svg|caption2=The corresponding moral graph, with newly added arcs shown in red}} The moralized counterpart of a directed acyclic graph is formed by adding edges between all pairs of non-adjacent nodes that have a common child, and then making all edges in the graph undirected. Equivalently, a moral graph of a directed acyclic graph {{mvar|G}} is an undirected graph in which each node of the original {{mvar|G}} is now connected to its Markov blanket. The name stems from the fact that, in a moral graph, two nodes that have a common child are required to be ''married'' by sharing an edge.<ref name="cdls">{{cite book |last1= Cowell |first1= Robert G. |last2= Dawid |first2= A. Philip|author2-link=Philip Dawid |last3= Lauritzen |first3= Steffen L.|author3-link=Steffen Lauritzen |last4= Spiegelhalter |first4= David J.|author4-link=David Spiegelhalter |title= Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks |publisher= Springer-Verlag New York |year= 1999 |isbn= 0-387-98767-3 |chapter= 3.2.1 Moralization|pages= 31–33|chapter-url=https://books.google.com/books?id=G_4E_w_wJzcC&pg=PA31|doi=10.1007/0-387-22630-3_3 }}</ref>
Moralization may also be applied to mixed graphs, called in this context "chain graphs". In a chain graph, a connected component of the undirected subgraph is called a chain. Moralization adds an undirected edge between any two vertices that both have outgoing edges to the same chain, and then forgets the orientation of the directed edges of the graph.
==Weakly recursively simplicial== A graph is '''weakly recursively simplicial''' if it has a simplicial vertex and the subgraph after removing a simplicial vertex and some edges (possibly none) between its neighbours is weakly recursively simplicial. A graph is moral if and only if it is weakly recursively simplicial.
A chordal graph (a.k.a., recursive simplicial) is a special case of weakly recursively simplicial when no edge is removed during the elimination process. Therefore, a chordal graph is also moral. But a moral graph is not necessarily chordal.<ref>{{harvtxt|Cowell|Dawid|Lauritzen|Spiegelhalter|1999}}, p. 50.</ref>
== Recognising moral graphs== Unlike chordal graphs that can be recognised in polynomial time, {{harvtxt|Verma|Pearl|1993}} proved that deciding whether or not a graph is moral is NP-complete.<ref>{{cite journal | last1 = Verma | first1 = T. S. | last2 = Pearl | first2 = J. | author2-link = Judea Pearl | journal = Uncertainty in Artificial Intelligence | pages = 391–399 | title = Deciding morality of graphs is NP-complete | year = 1993| doi = 10.1016/B978-1-4832-1451-1.50052-4 | arxiv = 1303.1501| isbn = 9781483214511 | s2cid = 14690613 }}</ref>
== See also == * D-separation * Tree decomposition
== References == {{reflist}}
==External links== * [http://staff.utia.cas.cz/studeny/e3.html M. Studeny: On mathematical description of probabilistic conditional independence structures]
Category:Bayesian networks Category:Graphical models Category:Graph operations