WikiSort.ru - Не сортированное

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

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

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

Морализация

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

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

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

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

См. также

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

Примечания

Литература

Ссылки

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.