Publications

Detailed Information

Phylogeny graphs of (3,2) digraphs : (3,2) 방향그래프의 계통그래프

DC Field Value Language
dc.contributor.advisor김서령-
dc.contributor.author임청-
dc.date.accessioned2021-11-30T06:59:07Z-
dc.date.available2021-11-30T06:59:07Z-
dc.date.issued2021-02-
dc.identifier.other000000164363-
dc.identifier.urihttps://hdl.handle.net/10371/176744-
dc.identifier.urihttps://dcollection.snu.ac.kr/common/orgView/000000164363ko_KR
dc.description학위논문 (석사) -- 서울대학교 대학원 : 사범대학 수학교육과, 2021. 2. 김서령.-
dc.description.abstract비순환 방향 그래프의 계통그래프가 삼각화가 가능한 지에 대한 문제는 베에지안 네트워크에서의 번식문제에서 비롯했다. 이와 관련하여 이승철 외(2017)와 어수강 외(2018)는 (2,j) 방향 그래프의 계통그래프의 삼각화에 대한 문제에 대하여 연구하였다. 이 논문에서는, 기존 연구를 확장하여 (3,2) 방향그래프의 계통그래프의 삼각화에 대한 문제를 연구하였다. 먼저 어떤 (3,2) 방향그래프의 계통그래프도 7개의 꼭짓점을 가진 완전그래프를 부분그래프로 가지지 않음을 보였다. 다음으로 만약 (3,2) 방향 그래프의 기본그래프가 길이가 10이상인 홀을 가질 때, (3,2) 방향 그래프의 계통그래프는 삼각화될 수 없음을 보였다. 게다가 삼각화가능한 (3,2) 방향그래프의 계통그래프가 될 수 없도록 하는 홀의 방향그래프들을 완전하게 정리하였다.-
dc.description.abstractChordality of the phylogeny graph of a (2,j) digraph was studied by Lee et al.(2017) and Eoh et al.(2018). The problem whether the phylogeny graph of an acyclic digraph is a chordal or not is motivated by the propagation problem in a Bayesian network. In this thesis, we study chordality of the phylogeny graph of a (3,2) digraph to extend the existing research. We show that the phylogeny graph of any (3,2) digraph does not have the complete graph on 7 vertices as a subgraph. Then we prove that if the underlying graph of a (3,2) digraph contains a hole of length n which is greater than 10, then the phylogeny graph of a (3,2) digraph is not chordal. In addition, we obtain the complete list of orientations of holes that are forbidden subdigraphs for the class of (3,2) digraphs whose phylogeny graphs are chordal. We hope that our results will provide insights for the further research on (i,2) digraphs.-
dc.description.tableofcontentsAbstract i

1 Introduction 1
1.1 Basic terminology 1
1.2 Competition graph and its variants 3
1.3 Triangulation of the moral graph 6
1.4 Chordality of phylogeny graph 7
1.5 Preview of thesis

2 The maximum degree of the phylogeny graph of an (i,j) digraph 9

3 Forbidden subgraphs for phylogeny graphs of (3,2) digraphs 11

4 A necessary condition for the phylogeny graph of a (3,2) digraph whose phylogeny graphs are chordal 16

5 Forbidden subdigraphs for the class of (3,2) digraphs whose phylogeny graphs are chordal 26

6 Concluding remarks 37

Abstract (in Korean) 41
-
dc.format.extentiii, 40-
dc.language.isoeng-
dc.publisher서울대학교 대학원-
dc.subjectCompetition graph-
dc.subjectPhylogeny graph-
dc.subject(3,2) digraph-
dc.subjectChordal graph-
dc.subject경쟁그래프-
dc.subject계통그래프-
dc.subject(3,2)방향그래프-
dc.subject삼각화된 그래프-
dc.subject.ddc510.7-
dc.titlePhylogeny graphs of (3,2) digraphs-
dc.title.alternative(3,2) 방향그래프의 계통그래프-
dc.typeThesis-
dc.typeDissertation-
dc.contributor.AlternativeAuthorIm Cheong-
dc.contributor.department사범대학 수학교육과-
dc.description.degreeMaster-
dc.date.awarded2021-02-
dc.identifier.uciI804:11032-000000164363-
dc.identifier.holdings000000000044▲000000000050▲000000164363▲-
Appears in Collections:
Files in This Item:

Altmetrics

Item View & Download Count

  • mendeley

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

Share