도덕 그래프
Moral graph그래프 이론에서, 도덕적 그래프는 지시된 악순환 그래프의 동등한 비방향 형태를 찾기 위해 사용된다.이것은 접속 트리 알고리즘의 핵심 단계로, 그래픽 모델에 대한 믿음 전파에 사용된다.
지시된 악순환 그래프의 도덕화된 상대방은 공통 자식을 갖는 비인접 노드 쌍 사이에 가장자리를 추가한 다음 그래프에서 모든 가장자리를 비방향으로 만들어 형성된다.마찬가지로, 지시된 Acyclic 그래프 G의 도덕 그래프는 원래 G의 각 노드가 이제 마르코프 담요에 연결된 비방향 그래프다.그 이름은 도덕 그래프에서 공통의 아이를 가진 두 개의 노드가 하나의 우위를 공유함으로써 결혼하도록 요구된다는 사실에서 유래되었다.[1]
이러한 맥락에서 "체인 그래프"라고 불리는 혼합 그래프에도 도덕화가 적용될 수 있다.체인 그래프에서, 비방향 서브그래프의 연결된 구성요소를 체인이라고 한다.도덕화는 둘 다 동일한 체인에 발신 에지를 가지고 있는 두 꼭지점 사이에 비방향 에지를 추가한 다음, 그래프의 방향 에지의 방향을 잊어버린다.
약하게 재귀적으로 단순화
그래프는 단순 정점을 제거한 후 하위 그래프가 있는 경우 약하게 재귀적으로 단순하고 인접한 부분 사이의 일부 가장자리(아마도 없음)는 약하게 재귀적으로 단순하다.그래프는 약하게 반복적으로 단순화될 경우에만 도덕적이다.
코드 그래프(예: 재귀적 단순화)는 제거 과정에서 가장자리가 제거되지 않을 때 약하게 재귀적으로 단순화된 특수한 경우다.따라서 화음 그래프도 도덕적이다.그러나 도덕적 그래프가 반드시 화음인 것은 아니다.[2]
도덕 그래프 인식
다항식 시간에 인식할 수 있는 화음 그래프와 달리, Verma & Pearl(1993)은 그래프가 도덕적인지 여부를 결정하는 것은 NP-완전하다는 것을 증명했다.
참고 항목
참조
- ^ Cowell, Robert G.; Dawid, A. Philip; Lauritzen, Steffen L.; Spiegelhalter, David J. (1999). "3.2.1 Moralization". Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks. Springer-Verlag New York. pp. 31–33. doi:10.1007/0-387-22630-3_3. ISBN 0-387-98767-3.
- ^ 코웰 외 연구진(1999), 페이지 50.
- Verma, T. S.; Pearl, J. (1993), "Deciding morality of graphs is NP-complete", Uncertainty in Artificial Intelligence: 391–399, arXiv:1303.1501, doi:10.1016/B978-1-4832-1451-1.50052-4, ISBN 9781483214511, S2CID 14690613.
