В теории графов моральный граф используется для поиска эквивалентной неориентированной формы направленного ациклического графа . Это ключевой шаг алгоритма дерева соединений , используемого при распространении убеждений на графических моделях .
Морализированный аналог направленного ациклического графа формируется путем добавления ребер между всеми парами несмежных узлов, имеющих общего потомка, а затем делая все ребра в графе неориентированными. Эквивалентно, моральный граф направленного ациклического графа G является неориентированным графом, в котором каждый узел исходного G теперь соединен со своим марковским одеялом . Название происходит от того факта, что в моральном графе два узла, имеющие общего потомка, должны быть женаты путем совместного использования ребра. [1]
Морализацию можно также применять к смешанным графам , называемым в этом контексте «цепными графами». В цепном графе связный компонент неориентированного подграфа называется цепью. Морализация добавляет неориентированное ребро между любыми двумя вершинами, обе из которых имеют исходящие ребра в одну и ту же цепь, а затем забывает ориентацию направленных ребер графа.
Граф слабо рекурсивно симплициален, если он имеет симплициальную вершину , а подграф после удаления симплициальной вершины и некоторых ребер (возможно, ни одного) между его соседями является слабо рекурсивно симплициальным. Граф является моральным тогда и только тогда, когда он слабо рекурсивно симплициален.
Хордальный граф (он же рекурсивный симплициальный) — это частный случай слабо рекурсивно симплициального, когда ни одно ребро не удаляется в процессе исключения. Поэтому хордальный граф также является моральным. Но моральный граф не обязательно является хордальным. [2]
В отличие от хордовых графов, которые можно распознать за полиномиальное время, Верма и Перл (1993) доказали, что решение вопроса о том, является ли граф моральным, является NP-полной задачей.