Моральный граф

В теории графов моральный граф используется для поиска эквивалентного неориентированного графа для направленного ациклического графа. Это ключевой шаг алгоритма для дерева сочленений, используемого в алгоритме распространения доверия на графовых вероятностных моделях.

Направленный ациклический граф

Соответствующий моральный граф с новыми рёбрами, показанными красным

Морализация

Морализованная копия направленного ациклического графа образуется добавлением рёбер между всеми парами узлов, которые имеют общих детей, а затем преобразования всех рёбер в графе в неориентированные. Эквивалентно, моральный граф ориентированного ациклического графа G является неориентированным графом, в котором каждый узел исходного графа G соединяется с его марковским ограждением. Название происходит от факта, что в моральном графе два узла, имеющих общих детей, должны обручиться путём создания общего ребра.

Заметим, что моральный граф не обязательно хордален.

Морализация смешанного графа

Морализация может быть осуществлена для смешанных графов, называемых в этом контексте «цепочечными графами». В цепочечном графе связанная компонента неориентированного подграфа называется цепочкой. Морализация добавляет неориентированное ребро между любыми двумя вершинами, которые имеют исходящие дуги в ту же самую цепочку, а затем забывается ориентация рёбер графа.

См. также

• D-separation
• Древесная декомпозиция

Литература

• Robert G. Cowell, A. Philip Dawid, Steffen L. Lauritzen, David J. Spiegelhalter. 3.2.1 Moralization // Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks. — Springer-Verlag New York, 1999. — P. 31–33. — ISBN 0-387-98767-3. — doi:10.1007/0-387-22630-3_3.

Ссылки

• M. Studeny: On mathematical description of probabilistic conditional independence structures