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