Моральний граф
У теорії графів моральний граф використовують для пошуку еквівалентного неорієнтованого графа для спрямовного ациклічного графа. Це ключовий крок алгоритму для дерева зчленувань, використовуваного в алгоритмі поширення довіри на графових імовірнісних моделях.
Моралізація
ред.Моралізована копія спрямованого ациклічного графа утворюється додаванням ребер між усіма парами вузлів, які мають спільних нащадків, а потім перетворення всіх ребер графа на неорієнтовані. Еквівалентно, моральний граф орієнтованого ациклічного графа G є неорієнтованим графом, в якому кожен вузол початкового графа G з'єднується з його марковським покриттям. Назва походить від факту, що в моральному графі два вузли, які мають спільних нащадків, повинні обручитися створенням спільного ребра[1].
Зауважимо, що моральний граф не обов'язково хордальний[2].
Моралізація змішаного графа
ред.Моралізацію можна здійснити і для змішаних графів, званих у цьому контексті «ланцюговими графами». У ланцюговому графі зв'язану компоненту неорієнтованого підграфа називають ланцюгом. Моралізація додає неорієнтоване ребро між будь-якими двома вершинами, які мають вихідні дуги в той самий ланцюг, а потім забувається орієнтація ребер графа.
Див. також
ред.Примітки
ред.Література
ред.- Robert G. Cowell, A. Philip Dawid, Steffen L. Lauritzen, David J. Spiegelhalter. 3.2.1 Moralization // [1] — Springer-Verlag New York, 1999. — P. 31–33. — ISBN 0-387-98767-3. — DOI: Архівовано з джерела 17 травня 2022