Browse

A study on chordality of the moral graph of a directed acyclic graph
사이클을 포함하지 않는 유향그래프가 삼각화된 모랄그래프를 가질 조건에 대한 연구

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors
이승철
Advisor
김서령
Major
사범대학 수학교육과
Issue Date
2016-02
Publisher
서울대학교 대학원
Keywords
bayesian networkmoral graphchordal graphtriangulationcompetition베이지안 네트워크모랄그래프삼각화된 그래프삼각화경쟁그래프(ij) 유향그래프
Description
학위논문 (석사)-- 서울대학교 대학원 : 수학교육과, 2016. 2. 김서령.
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.
Language
English
URI
https://hdl.handle.net/10371/127614
Files in This Item:
Appears in Collections:
College of Education (사범대학)Dept. of Mathematics Education (수학교육과)Theses (Master's Degree_수학교육과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse