Введение
В теории графов моральный граф используется для нахождения эквивалентной ненаправленной формы направленного ациклического графа. Это ключевой шаг алгоритма дерева стыков, используемый в распространении убеждений на графических моделях. Морализованный аналог направленного ациклического графа формируется путем добавления краев между всеми парами не смежных узлов, которые имеют общего ребенка, а затем делая все края в графе не направленными. Аналогичным образом, моральный график направленного ациклического графа G является не направленным графиком, в котором каждый узел исходного G теперь связан с его одеялом Маркова. Название происходит от того, что в моральном графике два узла, имеющие общего ребенка, должны быть женаты, имея общий край. Морализация может также применяться к смешанным графам, называемым в этом контексте "цепочными графами". В цепном графике соединенный компонент ненаправленного подграфа называется цепью. Морализация добавляет ненаправленный край между любыми двумя вершинами, которые оба имеют исходящие края к одной цепи, а затем забывает ориентацию направленных краев графа.
Слабо рекурсивное упрощение
Граф слабо рекурсивно упрощенный, если у него есть упрощенная вершина, а подграф после удаления упрощенной вершины и некоторых краев (возможно, ни одного) между его соседями слабо рекурсивно упрощенный. Граф морален, если и только если он слабо рекурсивно упрощен. Хордальный график (также известный как рекурсивный симпликат) - это особый случай слабо рекурсивного симпликата, когда во время процесса устранения не удаляется ни один край. Поэтому, хордальный график также моральный. Но моральный график не обязательно является хордальным.
Распознавание моральных графиков
В отличие от хордальных графов, которые могут быть распознаны в полиномиальном времени, доказано, что решение о том, является ли граф моральным, является NP полным.