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

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

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

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

Моралізація

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

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

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

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

Див. також

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

Примітки

1. Cowell, Dawid, Lauritzen, Spiegelhalter, 1999, с. 31–33.
2. Cowell, Dawid, Lauritzen, Spiegelhalter, 1999, с. 50.

Література

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

Посилання

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