Linear Ordering Problem of Tournament Digraph and its Computation
토너먼트 그래프의 선형 순서 문제와 그 계산

DC Field Value Language
dc.description학위논문(석사)--서울대학교 대학원 :자연과학대학 수리과학부,2020. 2. 국웅.-
dc.description.abstractA tournament is an oriented graph where every pair of distinct vertices are adjacent. It is used as a result of various competitions, such as sports league results and preference. And as ranking, there are several linear orderings at the tournament such as `Slater order', `Copeland order', `Sorted sequence of kings'. And competition winner is the first vertex of linear order. We will focus on `Slater order'.

`Slater order' is a linear order (v_1, v_2,...,v_n) of its vertex set such that
dc.description.abstract{(v_i,v_j) : i-
dc.description.abstractis as large as possible. In this paper, We will introduce several propositions for `Slater order' and 'Slater winner' and compare with other linear orders. And also introduce branch and bound method for computing `Slater order' of the given tournament by using boundary values of `Slater index'. Finally, we will introduce some open problems and conjecture about `Slater order'.-
dc.description.abstract토너먼트란 유향그래프 중 서로 다른 두 개의 모든 꼭짓점이 한 방향으로 인접한 그래프이다. 이것은 스포츠 리그 결과나 선호도와 같은 여러 경쟁의 결과로 이용된다. 경쟁의 순위로써 토너먼트에는 Slater 순서, Copeland 순서, Sorted sequence of kings 등 여러 선형순서가 있다. 그리고 선형순서의 첫 번째 꼭짓점은 경쟁의 우승자 꼭짓점으로 불린다. 우리는 이 중 Slater order에 집중하고자 한다.

Slater 순서란 토너먼트 꼭짓점들의 선형순서 (v_1,v_2,...,v_n)중 집합 {(v_i,v_j):i
dc.description.tableofcontents1 Introduction 1

2 Preliminary 3
2.1 Basic denitions 3
2.2 Tournament digraph and special examples 5

3 Linear ordering problem of tournament 8
3.1 Slater problem and its equivalent problem 9
3.2 Copeland order 12
3.3 Sorted sequence of kings 16

4 Properties of Slater problem 18
4.1 Slater order 18
4.1.1 Making another Slater order 20
4.1.2 Reversing arc in Slater order 22
4.1.3 Properties used in algorithm 23
4.1.4 Relationship with other linear orders 26
4.2 Slater winner 27
4.2.1 King network 27
4.2.2 Candidates of Slater winner 29
4.2.3 Relationship with other winners 32
4.3 Slater index 33

5 Algorithms 37
5.1 Computing SSK 37
5.2 Computing Slater order 39

6 Special examples and open problems 45
6.1 (Almost) Regular tournament 45
6.2 Brualdi-Li tournament 47

Abstract (in Korean) 54
Acknowledgement (in Korean) 55
dc.publisher서울대학교 대학원-
dc.titleLinear Ordering Problem of Tournament Digraph and its Computation-
dc.title.alternative토너먼트 그래프의 선형 순서 문제와 그 계산-
dc.contributor.department자연과학대학 수리과학부-
Appears in Collections:
College of Natural Sciences (자연과학대학)Dept. of Mathematical Sciences (수리과학부)Theses (Master's Degree_수리과학부)
Files in This Item:
  • mendeley

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