Publications
Detailed Information
A study on competition numbers of planar graphs
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.advisor | 김서령 | - |
| dc.contributor.author | 어수강 | - |
| dc.date.accessioned | 2017-07-19T02:32:51Z | - |
| dc.date.available | 2017-07-19T02:32:51Z | - |
| dc.date.issued | 2016-02 | - |
| dc.identifier.other | 000000132401 | - |
| dc.identifier.uri | https://hdl.handle.net/10371/127611 | - |
| dc.description | 학위논문 (석사)-- 서울대학교 대학원 : 수학교육과, 2016. 2. 김서령. | - |
| dc.description.abstract | 임의의 그래프의 경쟁수를 계산하는 것은 NP-Hard 문제이다. 그래프 G의 경쟁수에 대한 상계 M을 구하는 것은 그래프 G에 M개의 고립점을 더한 것을 경쟁그래프로 가지는 비순환 유향그래프 D를 직접 구성함으로써 보일 수 있다. 반면, 하계를 구하는 것은 매우 많은 경우를 고려해야 하기 때문에 어려운 일이다.
이 논문에서는 그래프 $G$의 최상위 포식자 지수 p(G)를 도입하여 Opsut(1982)이 제시한 경쟁수에 대한 하계보다 일반화된 새로운 하계를 제시하고, 이것이 `효율적인 경쟁 덮개'를 가지는 그래프의 경쟁수와 일치함을 보였다. 또한 다이아몬드를 갖지 않는 연결된 평면 그래프의 경쟁수를 최상위 포식자 지수를 이용하여 표현하고 이중 특정 평면그래프의 경쟁수를 계산하였다. | - |
| dc.description.tableofcontents | Chapter 1 Introduction 1
Chapter 2 Effective competition covers of graphs 6 Chapter 3 Relationship between the competition number and the primary predator index of a graph 13 Chapter 4 Competition numbers of planar graphs 20 Chapter 5 Concluding remarks 38 Bibliography 39 국문초록 42 | - |
| dc.format | application/pdf | - |
| dc.format.extent | 474365 bytes | - |
| dc.format.medium | application/pdf | - |
| dc.language.iso | ko | - |
| dc.publisher | 서울대학교 대학원 | - |
| dc.subject | competition graph | - |
| dc.subject | competition number | - |
| dc.subject | edge clique cover number | - |
| dc.subject | effective competition cover | - |
| dc.subject | primary predator index | - |
| dc.subject | planar graph | - |
| dc.subject.ddc | 510 | - |
| dc.title | A study on competition numbers of planar graphs | - |
| dc.type | Thesis | - |
| dc.description.degree | Master | - |
| dc.citation.pages | 41 | - |
| dc.contributor.affiliation | 사범대학 수학교육과 | - |
| dc.date.awarded | 2016-02 | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.