Моральный граф (Bkjgl,udw ijgs)

Перейти к навигации Перейти к поиску

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

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

Морализация

[править | править код]

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

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

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

[править | править код]

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

Примечания

[править | править код]

Литература

[править | править код]
  • 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.