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

Cited 0 time in Web of Science Cited 0 time in Scopus
Issue Date
서울대학교 대학원
학위논문(석사)--서울대학교 대학원 :자연과학대학 수리과학부,2020. 2. 국웅.
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
Files in This Item:
Appears in Collections:
College of Natural Sciences (자연과학대학)Dept. of Mathematical Sciences (수리과학부)Theses (Master's Degree_수리과학부)
  • mendeley

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