Моральний граф

У теорії графів моральний граф використовують для пошуку еквівалентного неорієнтованого графа для спрямовного ациклічного графа. Це ключовий крок алгоритму для дерева зчленувань, використовуваного в алгоритмі поширення довіри на графових імовірнісних моделях.

Спрямований ациклічний граф

Відповідний моральний граф із новими ребрами, показаними червоним

Моралізація

Моралізована копія спрямованого ациклічного графа утворюється додаванням ребер між усіма парами вузлів, які мають спільних нащадків, а потім перетворення всіх ребер графа на неорієнтовані. Еквівалентно, моральний граф орієнтованого ациклічного графа G є неорієнтованим графом, в якому кожен вузол початкового графа G з'єднується з його марковським покриттям. Назва походить від факту, що в моральному графі два вузли, які мають спільних нащадків, повинні обручитися створенням спільного ребра.

Зауважимо, що моральний граф не обов'язково хордальний.

Моралізація змішаного графа

Моралізацію можна здійснити і для змішаних графів, званих у цьому контексті «ланцюговими графами». У ланцюговому графі зв'язану компоненту неорієнтованого підграфа називають ланцюгом. Моралізація додає неорієнтоване ребро між будь-якими двома вершинами, які мають вихідні дуги в той самий ланцюг, а потім забувається орієнтація ребер графа.

Див. також

• О-розділеність
• Деревна декомпозиція

Література

• 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:10.1007/0-387-22630-3_3. Архівовано з джерела 17 травня 2022

Посилання

• M. Studeny: On mathematical description of probabilistic conditional independence structures [Архівовано 20 березня 2022 у Wayback Machine.]