Моральный график
В теории графов используется моральный граф для нахождения эквивалентной неориентированной формы ориентированного ациклического графа . Это ключевой шаг алгоритма дерева соединений , используемый при распространении убеждений в графических моделях .
Морализованный аналог ориентированного ациклического графа формируется путем добавления ребер между всеми парами несмежных узлов, имеющих общего дочернего элемента, а затем делает все ребра в графе неориентированными. Эквивалентно, моральный граф ориентированного ациклического графа G — это неориентированный граф, в котором каждый узел исходного G теперь связан со своим марковским одеялом . Название происходит от того факта, что в моральном графе два узла, имеющие общего ребенка, должны пожениться, имея общее ребро. [1]
Морализация также может быть применена к смешанным графам , называемым в этом контексте «цепными графами». В цепном графе связная компонента неориентированного подграфа называется цепью. Морализация добавляет ненаправленное ребро между любыми двумя вершинами, обе из которых имеют исходящие ребра в одну и ту же цепь, а затем забывает ориентацию направленных ребер графа.
Слабо рекурсивно симплициальный
[ редактировать ]Граф является слабо рекурсивно симплициальным, если он имеет симплициальную вершину , а подграф после удаления симплициальной вершины и некоторых ребер (возможно, ни одного) между его соседями является слабо рекурсивно симплициальным. Граф моральен тогда и только тогда, когда он слабо рекурсивно симплициален.
граф Хордальный (он же рекурсивный симплициал) — это частный случай слабо рекурсивно симплициала, когда в процессе исключения не удаляется ни одно ребро. Следовательно, хордальный граф также моральен. Но моральный граф не обязательно хордальный. [2]
Распознавание моральных графиков
[ редактировать ]В отличие от хордальных графов, которые можно распознать за полиномиальное время, Верма и Перл (1993) доказали, что решение о том, является ли граф моральным, является NP-полным.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Коуэлл, Роберт Г.; Дэвид, А. Филип ; Лауритцен, Штеффен Л .; Шпигельхальтер, Дэвид Дж. (1999). «3.2.1 Морализация» . Вероятностные сети и экспертные системы: точные методы расчета для байесовских сетей . Спрингер-Верлаг Нью-Йорк. стр. 31–33. дои : 10.1007/0-387-22630-3_3 . ISBN 0-387-98767-3 .
- ^ Коуэлл и др. (1999) , с. 50.
- Верма, Т.С.; Перл, Дж. (1993), «Определение моральности графов является NP-полным», Неопределенность в искусственном интеллекте : 391–399, arXiv : 1303.1501 , doi : 10.1016/B978-1-4832-1451-1.50052-4 , ISBN 9781483214511 , S2CID 14690613 .