В теории графов , А моральный график используется , чтобы найти эквивалентную неориентированную форму направленного ациклического графа . Это ключевой шаг алгоритма дерева соединений , используемого при распространении убеждений на графических моделях .
Морализованный аналог ориентированного ациклического графа формируется путем добавления ребер между всеми парами несмежных узлов, имеющих общий дочерний элемент, а затем превращения всех ребер в графе в ненаправленные. Эквивалентно, моральный граф ориентированного ациклического графа G - это неориентированный граф, в котором каждый узел исходного G теперь соединен со своим марковским одеялом . Название происходит от того факта, что в моральном графе два узла, у которых есть общий ребенок, должны быть женаты , разделяя ребро. [1]
Морализация также может применяться к смешанным графам , называемым в данном контексте «цепными графами». В цепном графе связная компонента неориентированного подграфа называется цепочкой. Морализация добавляет неориентированное ребро между любыми двумя вершинами, каждая из которых имеет выходящие ребра в одну и ту же цепочку, а затем забывает ориентацию ориентированных ребер графа.
Слабо рекурсивно симплициальный [ править ]
Граф является слабо рекурсивно симплициальным, если у него есть симплициальная вершина, а подграф после удаления симплициальной вершины и некоторых ребер (возможно, ни одного) между его соседями является слабо рекурсивно симплициальным. Граф является моральным тогда и только тогда, когда он слабо рекурсивно симплициальный.
Хорде граф (он же, рекурсивная симплициальная) является частным случаем слабо рекурсивно симплициальна , когда ни одно ребро не удаляется во время процесса ликвидации. Следовательно, хордовый граф - это тоже мораль. Но моральный граф не обязательно хордовый. [2]
Распознавание моральных графиков [ править ]
В отличие от хордовых графов, которые можно распознать за полиномиальное время, Верма и Перл (1993) доказали, что решение о том, является ли граф моральным, является NP-полным.
См. Также [ править ]
Ссылки [ править ]
- ^ Коуэлл, Роберт G .; Давид, А. Филип ; Лауритцен, Штеффен Л .; Шпигельхальтер, Дэвид Дж. (1999). «3.2.1 Морализация». Вероятностные сети и экспертные системы: точные вычислительные методы для байесовских сетей . Springer-Verlag New York. С. 31–33. DOI : 10.1007 / 0-387-22630-3_3 . ISBN 0-387-98767-3.CS1 maint: ref = harv ( ссылка )
- ^ Коуэлл и др. (1999) , стр. 50.
- Verma, TS; Перл, Дж. (1993), «Определение морали графов является NP-полным», Неопределенность в искусственном интеллекте : 391–399, arXiv : 1303.1501.
Внешние ссылки [ править ]
