В теории графов моральный граф используется для поиска эквивалентного неориентированного графа для направленного ациклического графа. Это ключевой шаг алгоритма для дерева сочленений, используемого в алгоритме распространения доверия на графовых вероятностных моделях.
Морализация Морализованная копия направленного ациклического графа образуется добавлением рёбер между всеми парами узлов, которые имеют общих детей, а затем преобразования всех рёбер в графе в неориентированные. Эквивалентно, моральный граф ориентированного ациклического графа является неориентированным графом, в котором каждый узел исходного графа соединяется с его марковским ограждением. Название происходит от факта, что в моральном графе два узла, имеющих общих детей, должны обручиться путём создания общего ребра.
Заметим, что моральный граф не обязательно хордален.
Морализация смешанного графа Морализация может быть осуществлена для смешанных графов, называемых в этом контексте «цепочечными графами». В цепочечном графе связанная компонента неориентированного подграфа называется цепочкой. Морализация добавляет неориентированное ребро между любыми двумя вершинами, которые имеют исходящие дуги в ту же самую цепочку, а затем забывается ориентация рёбер графа.
См. также D-separation Древовидная декомпозиция
Примечания
Литература
Ссылки M. Studeny: On mathematical description of probabilistic conditional independence structures
Категория:Байесовские сети Категория:Графические модели Категория:Операции над графами