A study on chordality of the moral graph of a directed acyclic graph

Abstract

사이클을 포함하지 않는 유향그래프가 삼각화된 모랄그래프를 가질 조건에 대한 연구는 베이지안 네트워크의 징후전달과 관련된 문제에서 비롯되었다. 이 논문에서는 삼각화된 모랄그래프를 가지는 (2,2) 유향그래프의 특징을 분석하여 두 개의 주된 결과를 얻었다. 그 중 하나는 (2,2) 유향그래프에서 유향변의 방향을 제거해 만든 그래프가 길이 7 이상인 홀을 가지는 경우, 그것의 모랄그래프는 삼각화된 그래프가 아니라는 것이다. 그리고 나머지 하나는 (2,2) 유향그래프에서 유향변의 방향을 제거해 만든 그래프가 삼각화된 그래프라면 그것의 모랄그래프 역시 삼각화된 그래프라는 것이다. 또한 이분 (2,2) 유향그래프가 삼각화된 모랄그래프를 가질 충분조건을 구하였다.

Determining whether or not a directed acyclic graph has a chordal graph as its moral graph is motivated by the problem related to the propagation of evidence in a Bayesian network. In this thesis, we will give a characterization of the (2,2) digraphs whose moral graphs are chordal. We give two main results. One states that if the underlying graph of a (2,2) digraph D contains a hole of length n for n\geq 7, then a moral graph of D is not a chordal graph. The other states that if an underlying graph of a (2,2) digraph D is chordal, then the moral graph of D is also chordal. In addition, we study chordality of moral graphs of (2,2) digraphs whose underlying graphs are bipartite graphs.