У теорії графів моральний граф використовують для пошуку еквівалентного неорієнтованого графа для спрямовного ациклічного графа. Це ключовий крок алгоритму для дерева зчленувань, використовуваного в алгоритмі поширення довіри на графових імовірнісних моделях.
Моралізація Моралізована копія спрямованого ациклічного графа утворюється додаванням ребер між усіма парами вузлів, які мають спільних нащадків, а потім перетворення всіх ребер графа на неорієнтовані. Еквівалентно, моральний граф орієнтованого ациклічного графа є неорієнтованим графом, в якому кожен вузол початкового графа з'єднується з його марковським покриттям. Назва походить від факту, що в моральному графі два вузли, які мають спільних нащадків, повинні обручитися створенням спільного ребра.
Зауважимо, що моральний граф не обов'язково хордальний.
Моралізація змішаного графа Моралізацію можна здійснити і для змішаних графів, званих у цьому контексті «ланцюговими графами». У ланцюговому графі зв'язану компоненту неорієнтованого підграфа називають ланцюгом. Моралізація додає неорієнтоване ребро між будь-якими двома вершинами, які мають вихідні дуги в той самий ланцюг, а потім забувається орієнтація ребер графа.
Див. також О-розділеність Деревна декомпозиція
Примітки
Література
Посилання M. Studeny: On mathematical description of probabilistic conditional independence structures