Publications
Detailed Information
Linear Ordering Problem of Tournament Digraph and its Computation : 토너먼트 그래프의 선형 순서 문제와 그 계산
Cited 0 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Advisor
- 국웅
- Issue Date
- 2020
- Publisher
- 서울대학교 대학원
- Description
- 학위논문(석사)--서울대학교 대학원 :자연과학대학 수리과학부,2020. 2. 국웅.
- Abstract
- A 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
{(v_i,v_j) : i
is 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'.
토너먼트란 유향그래프 중 서로 다른 두 개의 모든 꼭짓점이 한 방향으로 인접한 그래프이다. 이것은 스포츠 리그 결과나 선호도와 같은 여러 경쟁의 결과로 이용된다. 경쟁의 순위로써 토너먼트에는 Slater 순서, Copeland 순서, Sorted sequence of kings 등 여러 선형순서가 있다. 그리고 선형순서의 첫 번째 꼭짓점은 경쟁의 우승자 꼭짓점으로 불린다. 우리는 이 중 Slater order에 집중하고자 한다.
Slater 순서란 토너먼트 꼭짓점들의 선형순서 (v_1,v_2,...,v_n)중 집합 {(v_i,v_j):i
- Language
- eng
- Files in This Item:
- Appears in Collections:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.