\documentclass[dvips,10pt,b5paper]{book}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[dvips]{graphicx}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{multirow}
\usepackage{enumerate}
\usepackage{AlgofInfColor30January2011}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Automata
\usepackage{emlines,emlines2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Compilers
\usepackage[emtex,dvips,all]{xy}
\usepackage{hhline}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Reliable
\usepackage{enumerate}
\usepackage{amsmath,amssymb}
\addtocounter{part}{0}
\addtocounter{chapter}{29}
\setcounter{page}{1500}
\setcounter{tocdepth}{2}
\topmargin -10mm
\oddsidemargin 0.0in
\evensidemargin 0.0in
\makeindex
\sloppy
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\Zset{\mathbb{Z}}
\begin{document}
\tableofcontents
\chapter{ Score Sets and Kings\label{chapterScoreSets}}
\noindent The idea of comparison-based ranking has been discussed earlier in the chapter
\textit{Comparison based ranking},\index{comparison based ranking}
where score sequence was introduced as a way of ranking vertices in a tournament.
Oriented graphs are generalizations of tournaments. In fact, just like one can think of a tournament
as expressing the results of a round-robin competition without ties (with vertices representing players
and arrows pointing to the defeated players), one can think of an oriented graph as a round-robin
competition with ties allowed (ties are represented by not drawing the corresponding arcs).
\begin{figure}[!ht]
\centering
\includegraphics[width=10cm,height=3cm]{roundrobin}
\caption{A round-robin competition involving 4 players.\label{figroundrobin}}
\end{figure}
Figure \ref{figroundrobin} shows the results of a round-robin competition involving 4 players $a, \ b, \ c$
and $d,$ with (a) ties not allowed and (b) ties allowed. In the first instance there is always a winner
and a loser whenever two players square off, while in the latter case player $a$ ties with player $d$
and player $b$ ties with player $c.$
In 2009 Antal Iványi\nevindex{Iványi, Antal Miklós} studied directed graphs, in which every pair
of different vertices is connected with at least $a$ and at most $b$ arcs. He named them
$(a,b,n)$-tournaments or simply $(a,b)$-tournament.\index{directed graph}
\index{abtournament@$(a,b)$-tournament}\index{abntournament@$(a,b,n)$-tournament}
If $a = b = k,$ then the $(a,b)$-tournaments are called $k$-tournaments.\index{ktournament@$k$-tournament}
In this chapter we deal first of all with $1$-tournaments and $(0,1)$-tournaments.
$(0,1)$-tournaments are in some sense equivalent with $(2,2)$-tournaments. We use the simple notations
1-tournament $T^1_n,$\index{onetournament@1-tournament} 2-tournament $T^2_n,$\index{twotournament@2-tournament}
\ldots, $k$-tournament $T^k_n,$ \ldots .\index{ktournament@$k$-tournament}
It is worth mentioning that $T^1_n$ is a classical tournament, while oriented graphs are
$(0,1)$-tournaments. If we allow loops then every directed graph is some $(a,b,n)$-tournament
(see the Chapter \ref{chapterRanking} (\textit{Comparison Based Ranking}) of this book).
We discuss two concepts related with $(a,b)$-tournaments,
namely score sets and kings. A \textit{score set}\index{score set} is just the set of different scores
(out-degrees) of vertices, while a \textit{king}\index{king} is a dominant vertex.
We shall study both concepts for 1-tournaments first and then extend these to the more general setting
of oriented graphs.
Although we present algorithms for finding score sets and kings in $1$-tournaments and $(0,1)$-tournaments,
much of the focus is on constructing tournaments with special
properties such as having a prescribed score set or a fixed number of kings. Since players in a tournament
are represented by vertices, we shall use the words player and vertex interchangeably throughout
this chapter without affecting the meaning.
We adopt the standard notation $T(V,A)$ to denote
a tournament with vertex set $V$ and arc set $A.$ We denote the number of vertices by $n,$ and the
out-degree matrix\index{out-degree matrix} by $\mathcal{M},$ and the
in-degree matrix\index{in-degree matrix} by $N.$ Furthermore, we use the term $n$-tournament
and the notation $T^k_n$ to represent a tournament with $n$ vertices and exactly $k$ arcs between the elements
of any pair of different vertices. In a similar way $R_n^k$ and $N_n$ denote a regular, resp. a null graph.
When there is no ambiguity we omit one or even both indices shall refer
to the corresponding tournaments as $T,$ $R.$ and $N.$
In Section \ref{sec30Sets1t} the score sets of 1-tournaments are discussed, while Section
\ref{sec30Sets2t} deals with the sore sets of oriented graphs.
In Section \ref{sec30Unicity} the conditions of the unique reconstruction of the score sets are considered
at first for $k$-tournaments, then in more details for 1-tournaments and 2-tournaments.
In Section \ref{sec30Kings1t} and Section \ref{sec30Kings2t} results connected with
different kings of tournaments are presented.
Some long and accessible proofs are omitted. In these cases the Reader can find the coordinates of the proof
in \textit{Chapter notes} and \textit{Bibliography}.
%%%%%%%%%%%%%%%%%
\section{Score sets in 1-tournaments\label{sec30Sets1t}}\index{score sets in 1-tournaments|(}
In a round-robin competition with no ties allowed, what are the sets of nonnegative integers
that can arise as scores of players? Note that here we are not interested in the scores
of individual players (the score sequence), rather we are looking for the sets of nonnegative integers
with each integer being the score of at least one player in the tournament.
This question motivates the study of \textit{score sets} of tournaments.
The set of different scores of vertices of a tournament is called the \ki{score set}\inddef{score set}
of the tournament. In other words, the score set is actually the score sequence of a tournament
with repetitions removed. For example the tournament given in Figure \ref{fig30scoresetexample} has
score sequence $[0,2,2,2],$ whereas the score set of this tournament is $\{0,2\}.$
Figure \ref{fig30out} shows the out-degree matrix
of the tournament represented on Figure \ref{fig30scoresetexample}.
\begin{figure}[!t]
\centering
\includegraphics[width=6cm,height=3.2cm]{scoresetexample}
\caption{A tournament with score set $\{0,2\}.$}
\label{fig30scoresetexample}
\end{figure}
\begin{figure}[!t]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|} \hline
vertex/vertex & $a$ & $b$ & $c$ & $d$ & Score \\ \hline
$a$ & --- & $0$ & $0$ & $0$ & $0$ \\ \hline
$b$ & $1$ & --- & $1$ & $0$ & $2$ \\ \hline
$c$ & $1$ & $0$ & --- & $1$ & $2$ \\ \hline
$d$ & $1$ & $1$ & $0$ & --- & $2$ \\ \hline
\end{tabular} \\
\caption{Out-degree matrix of the tournament represented in Figure \ref{fig30scoresetexample}.\label{fig30out}}
\end{center}
\vspace{-2mm}
\end{figure}
\subsection{Determining the score set\label{subsec30scoresetof1t}}
Determining the score set of a tournament $T(V,A)$ is quite easy. The following algorithm
\textsc{Set1} takes the data of a tournament $T(V,A)$ as input
and returns the score set $\mathcal{S}$ of $T.$
The procedures of this chapter are written according to the third edition of the textbook
\textit{Introduction to Algorithms} published by T. H. Cormen,\nevindex{Cormen, Thomas H.}
C. E. Leiserson,\nevindex{Leiserson, Charles E.} R. L. Rivest\nevindex{Rivest, Ronald L.} and
C. Stein\nevindex{Stein, Clifford} in 2009.
\begin{alg}{Set1$(n,V,A)$\inddef{\textsc{Set1}}\label{set}}
1 \' $\mathcal{S} = \emptyset$ \\
2 \' \key{for} \= all vertex $u \in V$ \\
3 \' \> $s = 0$ \\
4 \' \> \key{for} \= all vertex $v \in V$ \\
5 \' \> \> \key{if} \= $(u,v) \in A$ \` \key{//} is $(u,v)$ an arc of $T$? \\
6 \' \> \> \> $s = s + 1$ \\
7 \' \> \key{if} \= $s \notin \mathcal{S}$ \` \key{//} is the found score new? \\
8 \' \> \> $\mathcal{S} = \mathcal{S} \cup \{s\}$ \\
9 \' \key{return} $\mathcal{S}$
\end{alg}
Since the scores of the vertices depend on $n(n - 1)$ out-degrees,
any algorithm determining the score set requires $\Omega(n^2)$ time. Due to the embedded loops in lines 02--08
the running time of \textsc{Set1} is $\Omega(n^2)$ even in the best case. The precise order of the running
time depends among others on the implementation of the \key{if} instruction in line 07. E.g., if line 07 is
implemented by the comparison of the actual score with the elements of $S,$ then the running time is
$\Theta(n^3)$ for a score sequence containing different elements and is $\Theta(n^2)$ for a regular tournament.
Out-degree matrix $\mathcal{M}_{n \times n} = [m_{ij}]_{n \times n}$ is a useful tool in the implementation
of graph algorithms. The input of the following algorithm \textsc{Quick-Set1} is $n$ and $\mathcal{M},$
and the output is the score sequence \textbf{s} as a nonincreasingly ordered sequence and the score set
$\mathcal{S}$ as an increasingly ordered sequence. \textsc{Quick-Set1} calls the well-known sorting procedure
\textsc{Insertion-Sort}.\index{\textsc{Insertion-Sort}}
\begin{algN}{Quick-Set1$(n,\mathcal{M})$\inddef{\textsc{Quick-Set1}}}
1 \' $\mathcal{S} = \emptyset$ \\
2 \' \key{for} \= $i = 1$ \key{to} $n$ \\
3 \' \> $s_i = 0$ \\
4 \' \> \key{for} \= $j = 1$ \key{to} $n$ \\
5 \' \> \> $s_i = s_i + m_{ij}$ \` \textbf{//} score sequence is computed \\
6 \' $S_1 = s_1$ \\
7 \' \textsc{Insertion-Sort}$(\mathbf{s})$ \key{if} \= $s \notin \mathcal{S}$ \` \key{//} sorting of the score vector\\
8 \' \key{for} \= $i = 2$ \key{to} $n$ \\
9 \' \> \key{if} \= $s_i \neq s_{i-1}$ \\
10 \' \> \> $S_k = s_i$ \\
11 \' \> \> $k = k +1$ \\
12 \' \key{return} $\mathbf{s}, \ \mathcal{S}$
\end{algN}
Since the embedded loops in lines 02--05 need $\Theta(n^2)$ time, and the remaining part of the code
requires less, the running time of \textsc{Quick-Set1} is $\Theta(n^2)$ in all cases.
\subsection{Tournaments with prescribed score set\label{subsec302Constrt1}}
Constructing a tournament with a prescribed score set is more difficult than determining the score set.
Quite surprisingly, if sufficiently many players participate in a tournament then any finite set
of nonnegative integers can arise as a score set. This was conjectured by
K. B. Reid\nevindex{Reid, K. Brooks} in 1978 and turned out to be a relatively challenging problem.
Reid proved the result when $| \ \mathcal{S} \ | = 1, 2$ or $3$, or if $\mathcal{S}$ contains consecutive terms
of an arithmetic or geometric progression. That is, Reid showed that any set of one, two or three
nonnegative integers is a score set of some tournament and additionally, any set of the form
$\{s, s + d, s + 2d, \ldots, s + pd\}$ for $s > 0, d>1$ or $\{s, sd, sd^{2},\ldots, sd^{p}\}$
for $s \geq 0, d > 0,$ is a score set of some tournament. Hager\nevindex{Hager, Michael} settled the cases
$| \mathcal{S} | = 4$ and $| \mathcal{S} | = 5$ in 1986 and finally in 1987, T. Yao\nevindex{Yao, Tianxing}
gave an existence proof of the general Reid's conjecture based on arithmetic analysis.
\begin{tetel} \emph{(Yao, 1988)} Every finite nonempty set $\mathcal{S}$ of nonnegative integers is
the score set of some tournament.
\end{tetel}
Let us try to formulate Reid's conjecture purely as a statement about numbers.
Let $\mathcal{S} = \{ s_{1}, \ldots, s_{p} \}$ be an increasing sequence of nonnegative integers.
The conjecture means that there exist positive integers $x_{1}, \ldots, x_{p}$ such that
\begin{equation*}
\mathcal{S} = (s_1^{x_1}, \ldots, s_2^{x_2} \ldots, s_p^{x_p})
\end{equation*}
is the score sequence of some 1-tournament with $\sum_{i=1}^p{x_i} = n$ vertices.
By Landau's\nevindex{Landau, H. G.} theorem, $\mathbf{a} = (a_1,\ldots,a_n)$, with $a_1 \leq \cdots \leq a_n,$
is the score sequence of some $1$-tournament $T_n$ if and only if $\sum_{i=1}^k a_i \geq \textbinom{k}{2},$
for $k=1, \ldots, n-1$ and $\sum_{i=1}^n a_i = \textbinom{n}{2}.$ Thus it can be readily seen
that Reid's conjecture is equivalent to the following statement.
For every nonempty set of nonnegative integers $S = \{s_1, \ldots, s_p \},$
where $s_1 < \cdots < s_p,$ there exist positive integers $x_1, \ldots, x_p,$ such that
\begin{eqnarray}
\sum_{i=1}^k s_i x_i \geq \binom{\sum_{i=1}^k x_i}{2}, \ \ \textnormal{ for } k=1,\ldots,p-1\koz,\\
\sum_{i=1}^p s_i x_i = \binom{\sum_{i=1}^px_i}{2} \koz. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\end{eqnarray}
It is this equivalent formulation of Reid's conjecture that led to Yao's\nevindex{Yao, Tianxing} proof.
The proof is not combinatorial in nature, but uses first of all some results of number theory.
Commenting on Yao's proof Qiao Li\nevindex{Li, Qiao} wrote in 2006
in the \textit{Annals of New York Academy of Sciences:}
\begin{quotation}
\textit{Yao's proof is the first proof of the conjecture, but I do not think it is the last one.
I hope a shorter and simpler new proof will be coming in the near future}.
\end{quotation}
However, the prophecized constructive proof has not been discovered yet. This is in sharp
contrast with Landau's theorem on score sequences, for which several proofs have emerged
over the years. Recently, S. Pirzada\nevindex{Pirzada, Shariefuddin} and T. A. Naikoo\nevindex{Naikoo, Tariq A.}
gave a constructive combinatorial proof of a new special case of Reid's theorem. Their proof
gives an algorithm for constructing a tournament with the prescribed score set,
provided the score increments are increasing.
\begin{tetel}\label{pirzada}
\emph{(Pirzada and Naikoo, 2008)} If $a_{1}, a_{2}, \ldots, a_{p}$ are nonnegative integers
with $a_1 < a_2 < \cdots < a_p,$ then there exists a 1-tournament $T$ with score set
\begin{equation}
S = \left \{s_1 =a_1, s_2 = \sum_{i=1}^2 a_i, \ldots, s_p = \sum_{i=1}^p a_i \right \}\koz.
\label{pirzadaset}
\end{equation}
\end{tetel}
\begin{figure}[t!]
\centering
\includegraphics[width=8cm,height=5cm]{dominance}
\caption{Construction of tournament $T$ with odd number of distinct scores.}
\label{figdominance}
\end{figure}
\begin{figure}[t!]
\centering
\includegraphics[width=8cm,height=5cm]{dominance2}
\caption{Construction of tournament $T$ with even number of distinct scores.}
\label{figdominance2}
\end{figure}
Since any set of nonnegative integers can be written in the form of \ref{pirzadaset}, the above theorem
is applicable to all sets of nonnegative integers $S = \{s_{1},s_{2},\ldots,s_{p}\}$
with increasing increments (i.e., $s_{1} print \textsc{Odd$(p,I_p)$} \\
3 \' \key{else} \> print \textsc{Even$(p,I_p)$}
\end{alg}
This algorithm calls one of the two following recursive procedures \textsc{ODD} and \textsc{Even}
according to the parity of $p.$ The input of both algorithm is some prefix $X_t$ of the sequence
of the increments $a_1, a_2, \ldots, a_t,$ and the output is a tournament having the score set corresponding
to the given increments.
\begin{algN}{Odd$(t,X_t)$\inddef{\textsc{Odd}}}
1 \' \key{if} \ \ \ \= $t == 1$ \\
2 \' \> \key{return} $R_{2a_1 + 1}$
\algnewpageN
3 \' \key{else} \> $T_t^{(3)} = R_{(2(a_t - a_{t-1} + a_{t-2} - a_{t-3} + \cdots+ a_3 - a_2 + a_1) + 1)}$ \\
4 \' \> $T_t^{(2)} = R_{2(a_{t-1} - a_{t-2} + a_{t-3} - a_{t-2} +
\cdots + a_4 - a_3 + a_2 - a_1 - 1) + 1}$ \\
5 \' \> $t = t - 2$ \\
6 \' \> $T_t^{(1)}$ = \textsc{Odd}$(t, X_t)$ \\
7 \' \> $T_t = T_t^{(3)} \oplus T_t^{(2)} \oplus T_t^{(1)}$ \\
8 \' \> $T_t = T + $ \= arcs such that \\
9 \' \> \> $T_t^{(2)}$ dominates $T_t^{(1)}$ \\
10 \' \> \> $T_t^{(3)}$ dominates $T_t^{(1)}$ \\
11 \' \> \> $T_t^{(3)}$ dominates $T_t^{(2)}$ \\
12 \' \key{return} $T_t$
\end{algN}
We can remark that the tournament constructed by the first execution of line 03 of \textsc{Odd} contains
the vertices whose score is $a_p,$ while the tournament constructed in line 04 contains the vertices whose score
is $a_{p - 1}$ in the tournament appearing as output. The vertices having smaller scores appear during
the later execution of lines 03 and 04 with exception of the vertices having score $a_1$ since those vertices
will be added to the output in line 02.
\begin{alg}{Even$(t,X_t)$\inddef{\textsc{Even}}}
1 \' \> $T_t^{(2)} = R_{2(a_{t} -a_{t-1} + a_{t-2} - a_{t-3} +
\cdots + a_4 - a_3 + a_2 - a_1 - 1) + 1}$ \\
2 \' \> $t = t - 1$ \\
3 \' \> $T_t^{(1)}$ = \textsc{Odd}$(t, X_t)$ \\
4 \' \> $T_t = T_t^{(2)} \oplus T_t^{(1)}$ \\
5 \' \> $T_t = T + $ \= arcs such that $T_t^{(2)}$ dominates $T_t^{(1)}$ \\
6 \' \key{return} $T_t$
\end{alg}
Since the algorithm is complicated, let's consider an example.
\begin{pelda} Let $p = 5$ and $I_5 = \{0,1,2,3,4\}.$ Since $p$ is odd, \textsc{Score-Reconstruction1}
calls \textsc{Odd} in line 02 with parameters $5$ and $I_5.$
The first step of \textsc{Odd} is the construction of $T_5^{(3)} = T_{2(4 - 3 + 2 - 1 + 0) + 1} = T_5$ in line 03.
Denoting the vertices of this regular 5-tournament by $v_1, \ v_2, \ v_3, \ v_4, \ v_5$ and using the result of
Exercise \ref{regular} we get the out-degree matrix shown in Figure \ref{table302}.
\begin{figure}[!t]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
vertex/vertex & $v_1$ & $v_2$ & $v_3$ & $v_4 $ & $v_5$ & Score \\ \hline
$v_1$ & --- & $1$ & $1$ & $0$ & $0$ & 2 \\ \hline
$v_2$ & $0$ & --- & $1$ & $1$ & $0$ & 2 \\ \hline
$v_3$ & $0$ & $0$ & --- & $1$ & $1$ & 2 \\ \hline
$v_4$ & $1$ & $0$ & $0$ & --- & $1$ & 2 \\ \hline
$v_5$ & $1$ & $1$ & $0$ & --- & $0$ & 2\\ \hline
\end{tabular} \\
\caption{Out-degree matrix of the tournament $T_5^{(3)}$.\label{table302}}
\end{center}
\vspace{-2mm}
\end{figure}
The second step of \textsc{Odd}\pelindex{\textsc{Odd}} is the construction of
$T_5^{(2)} = T_{2(3 - 2 + 1 - 0 - 1) + 1} = T_3.$ Let
$v_6, \ v_7$ and $v_8$ be the vertices of this tournament.
The third step of \textsc{Odd} is the recursive call with parameters $p = 3$ and $X_3 = \{2, \ 1, \ 0 \}.$
The fourth action of \textsc{Odd} is the construction of $T_3^{(3)} = T_{2(2 - 1 + 0) + 1} = T_3.$
Let $v_9, \ v_{10}$ and $v_{11}$ be the vertices of this tournament.
The fifth step is the construction of $T_3^{(2)} = T_{2(2 - 1 + 0 - 1)+ 1} = T_1.$ Let $v_{12}$ be the only
vertex of this graph. The sixth action is the call of \textsc{Odd} with parameters $t = 1$ and $X_1 = \{ 0 \}.$
Now the number of increments equals to 1, therefore the algorithm constructs $T_1^{(1)} = T_1$ in line 02.
The seventh step is the construction of $T$ in line 07, then the eighth step is adding new arcs (according to
lines 08--11) to the actual $T$ constructed in line 07 and consisting from 3 regular tournaments having
altogether 5 vertices $(v_{13}, \ v_{12}, \ v_{11}, \ v_{10}, \ v_9)$. The result is shown in Figure \ref{table303}.
\begin{figure}[!t]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
vertex/vertex & $v_9$ & $v_{10}$ & $v_{11}$ & $v_{12} $ & $v_{13}$ & Score \\ \hline
$v_9$ & --- & $1$ & $0$ & $1$ & $1$ & 3 \\ \hline
$v_{10}$ & $0$ & --- & $1$ & $1$ & $1$ & 3 \\ \hline
$v_{11}$ & $1$ & $0$ & --- & $1$ & $1$ & 3 \\ \hline
$v_{12}$ & $0$ & $0$ & $0$ & --- & $1$ & 1 \\ \hline
$v_{13}$ & $0$ & $0$ & $0$ & $0$ & --- & 0\\ \hline
\end{tabular} \\
\caption{Out-degree matrix of the tournament $T_5^{(3)}$.\label{table303}}
\end{center}
\vspace{-2mm}
\end{figure}
Ninth step of \textsc{Odd} is joining the tournaments $T_5$ and $T_3$ to $T$ and the final step
is adding of the domination arcs. The out-degree matrix of the output $T_5$ of \textsc{Odd}
is shown in Figure \ref{table304}.
\begin{figure}[!t]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
v/v &$v_1$&$v_2$&$v_3$&$v_4$&$v_5$&$v_6$&$v_7$&$v_8$&$v_9$&$v_{10}$&$v_{11}$&$v_{12}$&$v_{13}$& Score \\ \hline
$v_1$ & --- & $0$ & $0 $& $0$ & $0$ & $0$ & $0$ & $0$ & $0 $& $0$ & $0$ & $0$ & $0$ & 0 \\ \hline
$v_2$ & $1$ & --- & $0$ & $0$ & $0$ & $0$ & $0$ & $0$ & $0 $& $0$ & $0$ & $0$ & $0$ & 1 \\ \hline
$v_3$ & $1$ & $1$ & --- & $1$ & $0$ & $0$ & $0$ & $0$ & $0 $& $0$ & $0$ & $0$ & $0$ & 3 \\ \hline
$v_4$ & $1$ & $1$ & $0$ & --- & $1$ & $0$ & $0$ & $0$ & $0 $& $0$ & $0$ & $0$ & $0$ & 3 \\ \hline
$v_5$ & $1$ & $1$ & $1$ & $0$ & --- & $0$ & $0$ & $0$ & $0 $& $0$ & $0$ & $0$ & $0$ & 3 \\ \hline
$v_6$ & $1$ & $1$ & $1$ & $1$ & $1$ & --- & $1$ & $0$ & $0 $& $0$ & $0$ & $0$ & $0$ & 6 \\ \hline
$v_7$ & $1$ & $1$ & $1$ & $1$ & $1$ & $0$ & --- & $1$ & $0 $& $0$ & $0$ & $0$ & $0$ & 6 \\ \hline
$v_8$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $0$ & --- & $0 $& $0$ & $0$ & $0$ & $0$ & 6 \\ \hline
$v_9$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & --- & $1$ & $0$ & $1$ & $1$ & 10 \\ \hline
$v_{10}$& $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $0$ & --- & $1$ & $1$ & $0$ & 10 \\ \hline
$v_{11}$& $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $0$ & $0$ & --- & $1$ & $1$ & 10 \\ \hline
$v_{12}$& $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $0$ & $0$ & --- & $1$ & 10 \\ \hline
$v_{13}$& $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $0$ & $0$ & --- & 10\\ \hline
\end{tabular} \\
\caption{Out-degree matrix of the tournament $T_5$.\label{table304}}
\end{center}
\vspace{-2mm}
\end{figure}
\end{pelda}
\subsubsection{Correctness of the algorithm} Let $I = \{a_1, a_2, \ldots, a_p\}$ be a set of $p$
nonnegative integers with $a_1 < a_2 < \cdots < a_p.$
\textsc{Score-Reconstruction1} performs two types of recursions: first if $p$
is odd and the second if $p$ is even. Assume $p$ to be odd. For $p = 1,$ the set $I$
contains one nonnegative integer $a_1$ and the algorithm returns the regular tournament $T_{2a_{1}+1}$ as output.
Note that each vertex of $T_{2a_{1}+1}$ has score $\textbinom{2a_{1}+1-1}{2} = a_1,$ so that score set
of $T_{2a_{1}+1}$ is $S = \{s_1 = a_1\}.$ This shows that the algorithm is correct for $p = 1$.
If $p = 3,$ then the set of increments $I$ consists of three nonnegative integers
$\{a_1, a_2, a_3\}$ with $a_1 < a_2 < a_3.$ Now $a_3 > a_2,$ therefore $a_3 - a_2 > 0,$
so that $a_3 - a_2 + a_1 > 0$ as $a_1 \geq 0.$ Let $T^{(3)}$ be a regular tournament having
$2(a_{3} - a_{2} + a_{1}) + 1$ vertices. Then each vertex of $T^{(3)}$ has score
$\textbinom{2(a_3 - a_2 + a_1) + 1 - 1}{2} = a_3 - a_2 + a_1.$
Again, since $a_2 > a_1,$ therefore $a_2 - a_1 > 0,$ so that $a_2 - a_1 - 1 \geq 0.$ Let $T^{(2)}$
be a regular tournament having $2(a_2 - a_1 - 1) + 1$ vertices. Then each vertex of
$T^{(2)}$ has score $\textbinom{2(a_2 - a_1 - 1) + 1 - 1}{2} = a_2 - a_1 - 1.$
Also since $a_{1} \geq 0,$ let $T^{(1)}$ be a regular tournament having $2a_1 + 1$ vertices.
Then each vertex of $T_1$ has score $\textbinom{2a_1 + 1 - 1}{2} = a_1.$
If $p = 3,$ \textsc{Score-Reconstruction1}\index{Score-Reconstruction1} outputs a tournament $T$ whose
vertex set is the disjoint union of vertex sets of $T^{(1)},$ $T^{(2)}$ and $T^{(3)}$ and whose arc set contains
all the arcs of $T^{(1)},$ $T^{(2)}$ and $T^{(3)}$ such that every vertex of $T^{(2)}$
dominates each vertex of $T^{(1)},$ and every vertex of $T^{(3)}$ dominates each vertex of $T^{(1)}$
and $T^{(2)}.$ Thus $T$ has $2a_1 + 1 + 2(a_2 - a_1 - 1) + 1 + 2(a_3 - a_2 + a_1) + 1 = 2(a_1 + a_3) + 1$
vertices with score set
\begin{eqnarray*}
S = \{a_1, a_2 - a_1 - 1 + 2a_1 + 1, a_3 - a_2 + a_1 + 2(a_2 - a_1 - 1) + 1 + 2a_1 + 1\}\\
= \left \{a_1, \sum_{i=1}^2 a_i, \sum_{i=1}^3 a_i \right \} \koz. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\end{eqnarray*}
This shows that the algorithm is correct for $p = 3$ too. When the set $I$ of increments consists
of an odd number of nonnegative integers, the algorithm recursively builds the required tournament
by using the procedure \textsc{Odd}. To see this, assume that the algorithm works for all odd numbers
upto $p.$ That is, if $a_1, a_2,\ldots, a_p$ are $p$ nonnegative integers with $a_1 < a_2 < \cdots < a_p,$
then the algorithm outputs a tournament having $2(a_1 + a_3 +\ldots + a_p) + 1$ vertices with score set
$\{ a_1,\sum_{i=1}^2 a_i, \ldots, \sum_{i=1}^p a_i\}.$ Let us call this tournament $T^{(1)}.$
We now show how the algorithm constructs a tournament with $p + 2$ vertices with score set
$\{a_1, \sum_{i=1}^2 a_i, \ldots, \sum_{i=1}^{p+2} a_i\},$ where $a_1, a_2,\ldots, a_{p+2}$ are
$p+2$ nonnegative integers with $a_1 < a_2 < \cdots < a_{p+2}.$
Since $a_2 > a_1, a_4 > a_3,\ldots, a_{p-1} > a_{p-2}, a_{p+1} > a_p.$ therefore $a_2 - a_1 > 0,$ $a_4- a_3 > 0,$
$\ldots, a_{p-1} - a_{p-2} > 0,$ $a_{p+1}-a_p > 0,$ so that $a_{p+1} -a_p + a_{p-1} - a_{p-2} + \ldots +
a_4- a_3 + a_2 - a_1 > 0,$ that is, $a_{p+1}-a_p + a_p - 1 - a_{p-2} + \ldots + a_4 - a_3 + a_2 - a_1 - 1 \geq 0.$
The procedure \textsc{Odd}\index{\textsc{Odd}} constructs $T^{(2)}$ as a regular tournament having
$2(a_{p+1} - a_p + a_{p-1} - a_{p-2} + \cdots + a_4 - a_3 + a_2 - a_1 - 1) + 1$ vertices. Each vertex of $T^{(2)}$
has score
\begin{eqnarray*}
\frac{2(a_{p+1} - a_p + a_{p-1} - a_{p-2} + \ldots + a_4 - a_3 + a_2 - a_1 - 1) + 1 - 1}{2}\\
= a_{p+1} - a_p + a_{p-1} - a_{p-2} + \cdots + a_4 - a_3 + a_2 - a_1 - 1 \koz . \ \ \ \ \ \ \ \ \ \ \ \ \ \
\end{eqnarray*}
Again, $a_3 > a_2, \ldots, a_p > a_{p-1}, a_{p+2} > a_{p+1},$ therefore $a_{3}-a_2 > 0, \ldots,
a_{p} - a_{p-1} > 0, a_{p+2} - a_{p+1} > 0,$ so that $a_{p+2} - a_{p+1} + a_p - a_{p-1} + \cdots +
a_3 - a_2 + a_1 > 0$ as $a_1 \geq 0.$
The procedure \textsc{Odd}\index{\textsc{Odd}} constructs $T^{(3)}$ as a regular tournament having
$2(a_{p+2} - a_{p+1} + a_p - a_{p-1} + \cdots+ a_3 - a_2 + a_1) + 1$ vertices. Each vertex of $T^{(3)}$ has score
\begin{eqnarray*}
\frac{2(a_{p+2} - a_{p+1} + a_p - a_{p-1} + \cdots + a_{3} - a_2 + a_1) + 1 - 1}{2} \\
= a_{p+2} - a_{p+1} + a_p - a_{p-1} + \cdots + a_3 - a_2 + a_1 \koz . \ \ \ \ \ \ \ \ \ \ \ \ \ \
\end{eqnarray*}
Now \textsc{Score-Reconstruction1} sets $T=T^{(1)}\oplus T^{(2)}\oplus T^{(3)}$
and adds additional arcs in such a way that every vertex of $T^{(2)}$ dominates each vertex of $T^{(1)},$
and every vertex of $T^{(3)}$ dominates each vertex of $T^{(1)}$ and $T^{(2)}$. Therefore $T$ is
a tournament having
\begin{eqnarray*}
2(a_1 + a_3 + \cdots + a_p) + 1 + 2(a_{p+1}a_p + a_{p1}a_{p2} + \cdots + a_4a_3 + a_2a_1) + 1 \ \ \\
+2(a_{p+2}a_{p+1}+ a_pa_{p-1} + \cdots +a_3a_2 + a_1) + 1 \\
= 2(a_1 + a_3 + \cdots + a_{p+2}) + 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\end{eqnarray*}
\noindent vertices with score set
\begin{equation*}
S = \left \{a_1, \sum_{i=1}^2 a_i,\ldots, \sum_{i=1}^p a_i, \sum_{i=1}^{p+1} a_i, \sum_{i=1}^{p+2}a_i \right \} \koz.
\end{equation*}
Hence by induction, the algorithm is correct for all odd $p.$
To prove the correctness for even case, note that if $p$ is odd, then $p + 1$ is even. Let
$a_1, a_2, \ldots, a_{p+1}$ be $p+1$ nonnegative integers with $a_1 < a_2 < \cdots < a_{p+1}.$.
Therefore $a_1 < a_2 < \cdots < a_p,$ where $p$ is odd. The procedure \textsc{Even} uses
the procedure \textsc{Odd} to generate a tournament $T^{(1)}$ having $2(a_1 + a_3 + \cdots + a_p ) + 1$
vertices with score set $S = \{a_1, \sum_{i=1}^2 a_i,\ldots, \ \sum_{i=1}^p a_i\}.$
Also, since $a_2 > a_1,$ $a_4 > a_3, \ldots, a_{p-1} > a_{p-2}, a_{p+1} > a_p,$
the procedure \textsc{Even} generates a regular tournament $T^{(2)}$ having $2(a_{p+1} - a_p + a_{p-1} -
a_{p-2} + \cdots +a_4 -a_3 +a_2 - a_1 - 1) + 1$ vertices such that the score for each vertex is
$a_{p+1} - a_p + a_{p-1} - a_{p-2} + \cdots + a_4 - a_3 + a_2 - a_1 - 1.$
Finally the algorithm generates the tournament $T^{(1)}\oplus T^{(2)}$ and adds additional arcs so
that every vertex of $T^{(2)}$ dominates each vertex of $T^{(1)}.$
The resulting tournament $T$ consists of
\begin{eqnarray*}
2(a_1 + a_3 + \cdots + a_{p-2} + a_p ) + 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
+ 2(a_{p+1} - a_p + a_{p-1} - a_{p-2}+ \cdots + a_4 - a_3 + a_2 - a_1 - 1) + 1 \\
= 2(a_2 + a_4 + \cdots + a_{p+1}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\end{eqnarray*}
vertices and has score set
\begin{eqnarray*}
S = \{a_1,\sum_{i=1}^2 a_i,\ldots ,\sum_{i=1}^p a_i, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\
a_{p+1} - a_p + a_{p-1} - a_{p-2} + \cdots + a_4 - a_3 + a_2 - a_1 - 1 \\
+ 2(a_1 + a_3 + \cdots + a_{p-2} + a_p) + 1 \} \\
= \{a_1,\sum_{i=1}^2 a_i,\ldots, \ \sum_{i=1}^{p+1} a_i\}\koz.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\end{eqnarray*}
This shows that the algorithm is correct for even $p$ as well.
\subsubsection{Computational complexity}
The running time of \textsc{Score-Reconstruction1}\index{Score-Reconstruction1} depends
on the size of the score set $\vert S \vert$ as well as the largest increment $a_p = s_p - s_{p-1}.$
The details are left as a problem for the Reader (see Exercise \ref{regular}).
\begin{gyak}
\ujgyak\label{regular}
The out-degree matrix $\mathcal{M}$ of a tournament is defined as a $0-1$ matrix with $(i,j)$ entry
equal to 1 if player $v_{i}$ defeats player $v_{j}$ and 0 otherwise (see (\ref{outdeg})).
A tournament is completely determined by its out-degree matrix. Write an $O(n^{2})$ algorithm
to generate the out-degree matrix of a regular tournament on $n$ vertices, where $n$ is any odd positive integer.
\textit{Hint.} Circularly place $\textbinom{n-1}{2}$ ones in each row.
\vspace{-4mm}
\ujgyak\label{complexity}
Use Exercise \ref{regular} and the discussion in this section to determine
the worst-case running time of \textsc{Score-Reconstruction1}.\gyakindex{\textsc{Score-Reconstruction1}}
\ujgyak\label{ex}
Obtain the out-degree matrix of a tournament with score set $\{1,3,6\}$.
How many vertices does this tournament have? Draw this tournament and give its outdegree-matrix.
\ujgyak\label{exs}
Use the tournament obtained in Exercise \ref{ex} to generate the out-degree matrix of
a 1-tournament\index{onetournament@1-tournament}
with score set $\{1,3,6,10\}.$ Write the score sequence of your tournament.
\end{gyak}\index{score sets in 1-tournaments|)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Score sets in oriented graphs\label{sec30Sets2t}}\index{score sets in oriented graphs|(}
Oriented graphs are generalizations of tournaments. Formally, an \ki{oriented graph}\inddef{oriented graph}
$D(V,A)$ with vertex set $V$ and arc set $A$ is a digraph with no symmetric pairs of directed arcs and without loops.
In other words oriented graph is a directed graph in which every pair of different vertices is connected
with at most one arc, or oriented graphs are $(0,1)$-\textit{tournaments.}\index{zeroonetournament@$(0,1)$-tournament}
Figure \ref{figorientedgr} shows an oriented graph with score sequence $[1,3,3,5]$ and the coressponding
score set $\{1,3,5\}.$
\begin{figure}[t]
\centering
\includegraphics[width=6.2cm,height=3.7cm]{orientedgr}
\caption{An oriented graph with score sequence $[1,3,3,5]$ and score set $\{1,3,5\}$.\label{figorientedgr}}
\end{figure}
Thus tournaments are complete oriented graphs, in the sense that any pair of vertices in a tournament
is joined exactly by one arc. Several concepts defined for tournaments can be extended in a meaningful way
to oriented graphs. For example score of a player (vertex) in a tournament is defined as
its out-degree, as a player either wins (and earns one point) or looses (earning no points) a two-way clash.
In 1991, Peter Avery\nevindex{Avery, Peter} introduced the score structure for oriented graphs
based on the intuition that in a round-robin competition with ties allowed, a player may earn two,
one or no points in case the player wins, looses or makes a tie respectively.
More precisely, the score of a vertex $v_{i}$ in a $k$-tournament $D$ with $n$ vertices is defined as
$$
a(v_{i})= a_{i} =n-1+d^{+}_{v_{i}} -d^{-}_{v_{i}}\koz,
$$
where $d^+ _{v_i}$ and $d^- _{v_i}$ are the out-degree and in-degree, respectively, of $v_i$.
The score sequence of an oriented graph is formed by listing the vertex scores in non-decreasing order.
If we denote the number of non-arcs in $D$ containing the vertex $v_i$ as $d^* _{v_i}$, then
$$
a_{i} = 2d^{+}_{v_{i}}+d^{*}_{v_{i}} \koz .
$$
With this score structure, an oriented graph can be interpreted as the result of a round-robin competition
in which ties (draws) are allowed, that is, the players play each other once, with an arc from player
$u$ to $v$ if and only if $u$ defeats $v$. A player receives two points for each win,
and one point for each tie.
It is worth to remark that this is a sophisticated score structure comparing with the simple and natural
structure of 2-tournaments.\index{twotournament@2-tournament2-tournament}
Avery gave a complete characterization of score sequences of oriented graphs similar to Landau's theorem.
\begin{tetel}\label{avery} \emph{(Avery, 1991)}
A nondecreasing sequence $A = [a_1, \ldots, a_n ]$ of nonnegative integers is the score sequence
of an oriented graph if and only if
\begin{equation}\label{av}
\sum_{i=1}^{k}a_i \geq k(k - 1)
\end{equation}
\noindent for $1\leq k \leq n$ with equality when $k = n.$
\end{tetel}
\begin{biz}
This theorem is a special case of the theorem proved by Moon in 1963 or the theorem proved by
Kemnitz and Dulff in 1997 (see the theorem and its proof in Chapter \ref{chapterComparison},
that is chapter \textit{Comparison Based Ranking}).
\end{biz}
Just as in the case of 1-tournaments, the
\ki{score set of an oriented graph}\inddef{score set of an oriented graph}
is defined as the set of scores of its vertices. It is worth noting that
a $(0,1)$-tournament has different score sets under Avery's\nevindex{Avery, Peter} and
Landau's\nevindex{Landau, H. G.} score structures. In fact, the score of a vertex $v$
under Avery's score structure is twice the score of $v$ under Landau's score structure.
This is obviously due to Avery's assumption that a win contributes 2 points to the score.
The score set of an oriented graph can be determined by adapting \textsc{Quick-Set2} as follows:
\begin{algN}{Quick-Set2$(n,\mathcal{M})$\inddef{\textsc{Quick-Set2}}}
1 \' $S = \emptyset$ \\
2 \' \key{for} \= $i = 1$ \key{to} $n$ \\
3 \' \> $s_i = 0$ \\
4 \' \> \key{for} \= $j = 1$ \key{to} $n$ \\
5 \' \> \> $s_i = s_i + 2m_{ij}$ \\
6 \' \> \> \key{if} \= $m_{ij == 0}$ and $m_{ji} == 0$ \\
7 \' \> \> \> $s_i = s_i + 1$ \` \key{//} score sequence is computed \\
8 \' $S_1 = s_1$ \\
9 \' $k = 2$ \\
10 \' \key{for} \= $i = 2$ \key{to} $n$ \\
11 \' \> \key{if} \= $s_i \neq s_{i-1}$ \` \key{//} is the found score new? \\
12 \' \> \> $S_k = s_i$ \\
13 \' \> \> $k = k +1$ \\
14 \' \key{return} $\mathbf{s}, \ S$
\end{algN}
The running time of \textsc{Quick-Set2} is $\Theta(n^{2})$ since the nested loop in lines
02--07 requires $\Theta(n^2)$ the remaining lines require $\Theta(n)$ time.
\subsection{Oriented graphs with prescribed scoresets\label{subprescibedset2}}
In Section \ref{sec30Sets2t} we discussed score sets of tournaments
and noted that every non-empty set of nonnegative integers is the score set of some
tournament. In this section we study the corresponding question for oriented graphs,
i.e., which sets of nonnegative integers can arise as score sets of oriented graphs.
Pirzada\nevindex{Pirzada, Shariefuddin} and Naikoo\nevindex{Naikoo, Tariq A.}
investigated this question and gave two sufficient conditions for a set of nonnegative integers
to be the score set of some oriented graph.
\begin{tetel}\label{theorem30ssog1} \emph{(Pirzada, Naikoo, 2008)}
Let $a, \ d, \ n$ nonnegative integers, $a > 0$and $S = \{a, ad, ad^{2}, \ldots, ad^{n}\}$, with $d > 2$
or $d = 2$ and $n > 1.$ Then there exists an oriented graph with score set $S$ except for $a = 1, \ d = 2, \ n > 0$
and for $a = 1, \ d = 3, \ n > 0$.
\end{tetel}
\begin{tetel}\label{theorem30ssog2} \emph{(Pirzada, Naikoo, 2008)}
If $n$ is a positive integer and $a_1, a_2, \ldots, a_n$ are nonnegative integers with
$a_1 < a_2 < \cdots < a_n,$
then there exists an oriented graph with $a_n + 1$ vertices and with score set
$S = \{s_1, s_2, \ldots, s_n \},$ where
\begin{equation}\label{ss}
s_{i} = \left\{\begin{array}{l}
s_{i-1} + a_{i} + 1 \ \ \ \ \ \var{for } i > 1\koz, \\
s_{i} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \var{for } i = 1\koz.
\end{array} \right .
\end{equation}
\end{tetel}
Thus any set of positive integers whose elements form a geometric progression is the score set
of some oriented graph with few exceptions and any set of nonnegative integers whose elements are
of the form (\ref{ss}) is also a score set. It follows that every singleton set of nonnegative integers
is the score set of some oriented graph. On the other hand, for any positive integer $n,$
the sets $\{1, 2, 2^2, \ldots, 2^n \}$ and $\{1, 3, 3^2, \ldots, 3^n \}$ cannot be
the score sets of an oriented graph. Therefore, unlike in the case of tournaments, not all sets
of nonnegative integers are score sets of oriented graphs. So far no complete characterization
of score sets of oriented graphs is known.
The proof of Theorem \ref{theorem30ssog1} depends on the following auxiliary assertion.
\begin{lemma}\label{aux} \emph{(Naikoo, Pirzada, 2008)}
The number of vertices in an oriented graph with at least two distinct scores does not exceed its largest score.
\end{lemma}
\begin{biz} This assertion is the special case $k = 2$ of Lemma \ref{Lemma3031}
due to Iványi\nevindex{Iványi, Antal Miklós} and Phong.\nevindex{Phong, Bui Minh}
\end{biz}
Here we omit formal proofs of Theorems \ref{theorem30ssog1} and \ref{theorem30ssog2} since they
can be found on the internet and since we will implicitly prove these theorems when we check
the correctness of \textsc{Geometric-Construction2} and \textsc{Adding-Construction2}, respectively.
We first present a recursive algorithm that takes positive integers $a,$ $d,$ and $n,$ satisfying
the condition of Theorem \ref{ssog1}, as input and generates a 2-tournament $D(V,A)$
with score set $\{ a, ad, ad^2, \ldots, ad^n \}.$ Let $N_{p}$ denote the null digraph on $p$ vertices,
i.e., the digraph with $n$ vertices and no arcs.
\begin{algN}{Geometric-Construction2$(a,d,n)$}\inddef{\textsc{Geometric-Construction}}
1 \' \key{if} \ \ \ \ \= $n = 0$\\
2 \' \> $D = N_{a+1}$ \\
3 \' \> \key{return} $D$ \\
4 \' \key{if} \= $n = 1$\\
5 \' \> \key{if} \= $a = 1$ and $d = 3$ \\
6 \' \> \> $X = N_{a+1}$ \\
7 \' \> \> $Y = N_{ad - a - 1}$ \\
8 \' \> \> $D = X \oplus Y$\\
9 \' \> \> add arcs to $D$ such \\
10 \' \> \> $X$ dominates $Y$\\
11 \' \> \> \key{return} $D$ \\
12 \' \> \key{if} \= $a > 2$ and $d = 2$ \\
13 \' \> \> $X = N_2$ with vertex set $\{u_1,u_2 \}$\\
14 \' \> \> $Y = N_{a - 2}$ with vertex set $\{v_1,v_2,\ldots,v_{a - 2} \}$\\
15 \' \> \> $Z = N_a$ with vertex set $\{z_1,z_2,\ldots,z_a\}$ \\
16 \' \> \> $D = X \oplus Y \oplus Z$\\
17 \' \> \> add arcs to $D$ such that\\
18 \' \> \> $v_i \rightarrow u_1$ for $i = 1, 2, \ldots,a$ \\
19 \' \> \> $v_i \rightarrow u_2$ for $i = 1, 2, \ldots,a$ \\
20 \' \> \> $w_1 \rightarrow u_1$
\algnewpageN
21 \' \> \> $w_2 \rightarrow u_2$ \\
22 \' \> \> $w_{i+2} \rightarrow v_i$ for $i = 1, 2, \ldots,a - 2$ \\
23 \' \> \key{if} \= $a = 1$ and $d = 3$ \\
24 \' \> \> $X = N_{a+1}$ \\
25 \' \> \> $Y = N_{ad - a - 1}$ \\
26 \' \> \> $D = X \oplus Y$\\
27 \' \> \> add arcs to $D$ such \\
28 \' \> \> $X$ dominates $Y$\\
29 \' \> \> \key{return} $D$
\end{algN}
The running time of \textsc{Geometric-Construction2} is ???????
\begin{pelda} Let $a = 2, \ d = 2$ and $n = 2.$ Then the prescribed score set is $\{2,4,8\}.$ The first step
is the call of \textsc{Geometric} with parameters $(2,2,2).$
\end{pelda}
\subsubsection{Algorithm description}
If $n = 0,$ then the algorithm returns the null digraph $N_{a+1}.$ Note that $N_{a+1}$ is well-defined
as $a + 1 > 0.$ Each vertex of $N_{a+1}$ has score $a + 1 - 1 + 0 - 0 = a.$ Therefore the score set
of $N_{a+1}$ is $S = \{a\}.$ Thus the algorithm is correct for $n = 0.$
If $n = 1,$ then four cases arise.
Case i). If $a = 1$ and $d > 3,$ then $a + 1 > 0$ and $ad - 2a - 1 > 0.$ Construct an oriented graph $D$ with
vertex set $V = X \cup Y,$ where $X \cap Y = \emptyset,$ $|X| = a + 1,$ $|Y| = ad - 2a - 1$ and
$Y \rightarrow X.$ Then $D$ has $ad - a$ vertices and the different scores are $a$ and $ad.$
Case ii). If $a = 2$ and $d = 2.$ Construct an oriented graph $D$ with vertex set $\{v_1,v_2,v_3\}$ and
$v_4$ and arc set $(v_1,v_3),(v_2,v_4).$ The score set of $D$ is $\{2,4\}.$
case iii). If $a > 2$ and $d = 2,$ then
with vertex set $V = X \cup Y,$ where $X \cap Y = \emptyset,$ $|X| = a + 1,$ $|Y| = ad - 2a - 1$ and
$Y \rightarrow X.$ Then the scores are $a$ for all $x \in X$ and $ad$ for all $y \in Y.$
Now we prove the correctness of \textsc{Geometric} by induction. That is, we show that
if the algorithm is valid for $n = 0, 1,\ldots, p$ for some integer $p \geq 1$ then it is also valid
for $n = p + 1.$ Let $a$ and $d$ be positive integers with $a > 0$ and $d > 1$ such that for $a = 1,$
$d \neq 2, 3.$ By the induction hypothesis the algorithm can construct an oriented graph $D^{(1)}$
with score set $\{a, ad, \ldots, ad^p\}$ and $a, ad, \ldots, ad^p$ are the distinct scores
of the vertices of $D^{(1)}.$ Let $U$ be the vertex set of $D^{(1)}.$
There are three possibilities:
\begin{itemize}
\item $a = 1$ and $d > 3,$
\item $a > 1$ and $d = 2$ or
\item $a > 1$ and $d > 2.$
\end{itemize}
Obviously, for $d > 1$ in all the above cases we have $ad^{p+1}\geq 2ad^{p}.$ Also the score set
of $D^{(1)},$ namely $\{a, ad, \ldots, ad^{p}\},$ has at least two distinct scores for $p \geq 1.$
Therefore, by Lemma \ref{aux} we have $\vert U \vert \leq ad^{p}.$ Hence
$ad^{p + 1}\geq 2 \vert U \vert$ so that $ad^{p + 1} - 2 \vert U\vert + 1 > 0.$
Let $N_{ad^{p + 1} - 2 \vert U \vert + 1}$ be the null digraph with vertex set $X.$
The algorithm now generates the vertex and arc disjoint union $D=D^{(1)}\oplus N_{ad^{p+1}-2\vert U\vert+1}$
and adds an arc directed from each vertex in $N_{ad^{p+1}-2 \vert U\ vert + 1}$ to every vertex of $D^{(1)}.$
The output $D(V,A)$ of \textsc{Geometric-Construction2}, therefore, has
$\vert V\vert = \vert U \vert + ad^{p+1} - 2 \vert U \vert + 1 = ad^{p+1}-\vert U\vert + 1$ vertices.
Moreover, $a + \vert X \vert - \vert X \vert = a,$, $ad + \vert X \vert - \vert X \vert = ad.$
$ad^{2} + \vert X \vert - \vert X \vert = ad^2, \ldots, ad^p + \vert X \vert - \vert X \vert = ad^p$
are the distinct scores of the vertices in $U,$ while $a_{x} = \vert U \vert - 1 + \vert V\vert - 0 =
ad^{p+1} - \vert V \vert + 1 - 1 + \vert V \vert = ad^{p+1}$ for all vertices $x\in X.$
Therefore the score set of $D$ is $S = \{a, ad, ad^2, \ldots, ad^p, ad^{p+1}\}$
which shows that the algorithm works for $n = p + 1.$ Hence the algorithm is valid for all
$a,$ $d$ and $n$ satisfying the hypothesis of Theorem \ref{ssog1}.
The recursive procedure \textsc{Geometric} runs $n$ times and during its $i^{th}$ run
the procedure adds $O(ad^{n + 1 -i})$ arcs to the oriented graph $D.$ The overall complexity
of the algorithm is therefore $O(nad^n).$
As noted in Theorem \ref{ssog1}, there exists no 1-tournament when either $a = 1, \ d = 2, \ n > 0$ or
$a = 1, \ d = 3, \ n > 0.$ It is quite interesting to investigate these exceptional cases
as it provides more insight into the problem.
Let us assume that $\mathbf{S} = \{ 1, 2, 2^2,\ldots, 2^n\}$ is a score set of some oriented graph $D$
for $n > 0.$ Then there exist positive integers, say $x_1, x_2, x_3, \ldots, x_{n+1}$ such that
$$
S_1 = [1^{x_1},2^{x_2}, \ldots, (2^2)^{x_3},\ldots,(2^n)^{x_{n+1}}
$$
is the score sequence of $D.$ Therefore, by relations (\ref{av}) of score sequences of 1-tournaments, we have
$$
x_1 + 2x_2 + 2^{2}x_3 +\cdots+ 2^{n}x_{n+1} =
\left(\sum_{i=1}^{n+1}x_i\right)\left(\sum_{i=1}^{n+1}x_i -1 \right)\koz,
$$
which implies that $x_1$ is even. However, $x_1$ is a positive integer, therefore $x_1 \geq 2.$
Let the scores be $a_1 = 1,$ $a_2 = 1$ and $a_3 \geq 1.$ By inequalities (\ref{av})
$a_1 + a_2 + a_3 \geq 3(3-1) = 6,$ or in other words, $a_3 \geq 4.$ This implies that
$x_2 = 0,$ a contradiction.
The proof of the other exceptional case ($\mathcal{S} = \{ 1, 3, 3^2, \ldots, 3^n \}$) is left as an
exercise (Exercise \ref{case}).
Let $I_p = a_1 > a_2 > \cdots > a_p$for $1 \leq p \leq n.$
The next algorithm takes the set $I = \{a_1 < a_2 < \cdots < a_n \}$ consisting of $n$ nonnegative integers
as input and recursively constructs an oriented graph $D(V,A)$ with the score set
$S = \{s_1, s_2, \ldots, s_n\}$ where the scores $s_i$ are of the form \ref{ss}.
\begin{alg}{Adding-Construction2$(n,I_n)$}\inddef{\textsc{Adding-Construction}}
1 \' \key{if} \ \ \ \ \= $n = 0$\\
2 \' \> $D = N_{a_1+1}$ \\
3 \' \> \key{return} $D$ \\
4 \' \key{else} \> $D^{(1)}$ = \textsc{Adding-Construction}$(n - 1,I_{n - 1})$\\
5 \' \> $D =$ \= $D^1 \oplus N_{a_{n+1}-a_n}$\\
6 \' \> add arcs to $D$ such that $N_{a_{n}-a_{n-1}}$ dominates $D^{(1)}$ \\
7 \' \key{return} $D$\\
\end{alg}
The running time of \textsc{Adding-Construction2} is ???????
\begin{pelda} ?????
\end{pelda}
\subsubsection{Algorithm description}
If $n = 1,$ the algorithm returns the null digraph $N_{a_{1} + 1}.$ Each vertex of $N_{a_{1} + 1}$
has the score $a_1 + 1 - 1 + 0 - 0 = a_1 = a'_1.$ Therefore the score set of $N_{a_{1} + 1}$ is
$S = \{a'_{1}\}$ as required.
We prove the correctness of \textsc{Adding-Construction2} in general by induction on $n.$
Assume that the algorithm is valid for $n = 1, 2, \ldots, p,$ for some integer $p \geq 2.$
We show that the algorithm is also valid for $n=p + 1.$ Let $a_1, a_2, \ldots, a_{p+1}$
be nonnegative integers with $a_1 < a_2 < \cdots< a_{p+1}.$ Since $a_1 < a_2 < \cdots< a_p,$
by the induction hypothesis, the algorithm returns an oriented graph $D^{(1)}$ on $a_p + 1$
vertices with score set $\{a'_1, a'_2, \ldots, a'_p \},$ where $a'_i$ is given by equations (\ref{ss}).
That is, score set of $D^{(1)}$ is $\{a_1, a_1 + a_2 + 1, a_2 + a_3 + 1, \ldots, a_{p-1} + a_p + 1 \}.$
So $a_1,$ $a_1 + a_2 + 1,$ $a_2 + a_3 + 1, \ldots, a_{p-1} + a_p + 1$ are the distinct scores
of the vertices of $D.$ Let $X$ be the vertex set of $D^{(1)}$ so that $\vert X \vert = a_p + 1.$
Since $a_{p+1} > a_p,$ $a_{p+1} - a_p > 0,$ the algorithm constructs a new oriented graph
$D=D^{(1)}\oplus N_{p+1}$ with vertex set $V = X \cup Y,$ where $Y$ is the vertex set of
$N_{p+1}$ and $\vert Y \vert = a_{p+1} - a_p.$ Arcs are added to $D$ such that there is an arc
directed from each vertex in $Y$ to every vertex in $X.$ Thus $D$ has $\vert V \vert =
\vert X \vert + \vert Y \vert = a_p +1+ a_{p+1} - a_p = a_{p+1} + 1$ vertices.
The distinct score of vertices in $X$ are $a_1 + \vert Y \vert - \vert Y \vert =
a_1 = a'_1, a_1 + a_2 + 1 + \vert Y \vert - \vert Y \vert =
a_1 + a_2 + 1 = a'_2, a_2 + a_3 + 1 + \vert Y \vert - \vert Y \vert = a_2 + a_3 +1 = a'_3, \ldots,
a_{p-1}+a{p}+1+\vert Y\vert-\vert Y\vert =a_{p-1} + a_p + 1 = a'_p,$ while
$a_y = \vert X\vert - 1 + \vert V \vert - 0 = a_{p+1} + 1 - 1 + a_p + 1 = a_p + a_{p+1} + 1 =
a'_{p+1}$ for all $y \in Y.$
Therefore the score set of $D$ is $S = \{s_1, s_2, \ldots, s_p, s_{p+1} \}$ which proves
the validity of algorithm for $n = p + 1.$ Hence by induction,
\textsc{Adding-Construction2} is valid for all $n.$
The analysis of computational complexity of \textsc{General-Construction}
is left as an exercise (Exercise \ref{ss1complexity}).
\begin{gyak}
\ujgyak\label{case}
Prove that there exists no oriented graph with score set $\{1,3,3^{2},\ldots,3^{n}\}$ for any $n > 0.$
\ujgyak\label{bothexceptional}
Prove that if $n \geq 2$ and $\mathcal{S} = \{ 1,a_2,a_3,\ldots,a_n \},$ then $a_2 \geq 4.$
\ujgyak\label{ss1complexity}
\textsc{Adding-Construction} is a recursive algorithm. Analyse its running time and
compare its performance with the performance of \textsc{Geometric-Construction}.
\ujgyak\label{orientedgraph1}
Implement \textsc{Adding-Construction} in a suitable programming language and use it to construct
an oriented graph with score set $\{2,4,8\}.$ Write the score sequence of your oriented graph.
\ujgyak\label{orientedgraph2}
Implement \textsc{Adding-Construction} in a suitable programming language and use it to construct
an oriented graph with score set $\{1,4,6,9\}.$ Write the score sequence of your oriented graph.
\ujgyak\label{lemma}
Give a proof of Lemma \ref{aux}.
\ujgyak\label{tournamentgraph1}
For any nonnegative integer $n,$ what is the score set of the regular tournament $T_{2n+1}$
when considered as an oriented graph.
\ujgyak\label{tournamentgraph2}
Determine the score set of the oriented graph $D=T_{3}\oplus T_{5},$ where $T_{5}$ dominates
$T_{3},$ i.e., there is an arc directed from every vertex of $T_{5}$ to every vertex of $T_3.$
\vspace{-4mm}
\ujgyak\label{cyclealgo}
Write an $O(n)$ algorithm to determine the score set
of directed cycles\gyakindex{directed cycle}\gyakindex{cycle} (i.e., cycles with directed edges).
How can we make this algorithm work for directed wheels (note that a
\textit{wheel}\gyakindex{wheel}\gyakindex{directed wheel}
is a cycle with an additional vertex joined to all the vertices on the cycle).
\end{gyak}\index{score sets in oriented graphs|)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Unicity of score sets\label{sec30Unicity}}\index{unicity of score sets|(}
\ki{$k$-tournaments}\inddef{ktournament@$k$-tournament} (multitournaments)\index{multitournament}
are directed graphs in which each pair of vertices is connected with exactly $k$ arcs.
Reid formulated the following conjecture in \cite{Reid1978}.
\begin{sejtes} Any set of nonnegative integers is the score set of some 1-tournament T.
\end{sejtes}
Using Landau's theorem this conjecture can be formulated in the following arithmetic form too.
\begin{sejtes} If $0 \leq r_1 < r_2 < \cdots < r_m,$ then there exist such positive integers
$x_1, \ x_2, \ \ldots, \ x_m,$ that
$$\sum_{i=1}^{j} x_i r_i \geq \frac{(\sum_{i=1}^{j} x_i)(\sum_{i=1}^{j} x_i - 1)}{2}, \ j \in[1:m]$$
and
$$\sum_{i=1}^{m} x_i r_i = \frac{(\sum_{i=1}^{m} x_i)(\sum_{i=1}^{m} x_i - 1)}{2}\koz .$$
\end{sejtes}
In this case we say that the sequence $\mathbf{s} = \langle s_1,\ldots,s_n \rangle = \langle r_1^{x_1},
\ldots, r_m^{x_m} \rangle$ realizes the sequence $\mathbf{r} = \langle r_1,\ldots,r_m \rangle$ or
$\mathbf{s}$ is a solution for $\mathbf{r}.$
Reid gave a constructive proof of his conjecture for sets containing one, two or three elements \cite{Reid1978}.
Later Hager published a constructive proof for sets with four and five elements \cite{Hager1986} and
Yao \cite{Yao1989} published the outline of a nonconstructive proof of the general case.
A score set is called \ki{k-unique,}\inddef{kunique score set@$k$-unique score set}
if there exists exactly 1 score sequence of $k$-tournaments\index{ktournament@$k$-tournament}
generating the given set. In the talk we investigate the following questions:
\begin{enumerate}
\item
characterization of the unique score sets of 1-tournaments;
\item
extension of the Reid's conjecture to 2-tournaments.
\end{enumerate}
\subsection{1-unique score sets\label{subsec3031}}
At first we formulate a useful necessary condition.
\begin{lemma}\label{lemma3031m1} (Iványi\nevindex{Iványi, Antal Miklós} and Phong,\nevindex{Phong, Bui Minh} 2004)
If $k \geq 1,$ then for any $(n,k)$-tournament
holds that the sequence $\mathbf{s}$ is a solution for $\mathbf{r},$ then
in the case $m = 1$ we have
\begin{equation}
n = 2r_1 + 1
\end{equation}
and in the case $m \geq 2$ we have
\begin{equation}
\frac{2r_1}{k} + 1 < n < \frac{2r_m}{k} + 1
\end{equation}
and
\begin{equation}
n \geq r_m + 1\koz.
\end{equation}
\end{lemma}
\begin{biz} If
\end{biz}
This lemma implies the exact answer for the case $m = 1.$
\begin{kov} (Iványi\nevindex{Iványi, Antal Miklós} and Phong,\nevindex{Phong, Bui Minh}
2004) If $\mathbf{r} = \langle r_1 \rangle,$ then exactly the sequence
$\mathbf{s} = \langle r_1^{2r_1 + 1} \rangle$ is a solution for $\mathbf{r}.$
\end{kov}
\begin{biz} Lemma \ref{lemmam3031m1} implies that only this solution is acceptable. One can check that it
satisfies the required inequality and equality.
\end{biz}
Now we present a useful method of the investigation of the uniqueness. Let
$\mathbf{r} = \langle a, a + d \rangle.$ Then according to the Reid-equa\-lity we get
$$2ax + 2(a + d)y = n(n - 1)$$
implying
\begin{equation}
y = \frac{n(n - 2a - 1)}{2d} \koz .\label{eqe14}
\end{equation}
But here only the values $n = 2a + 1 + i \ (i \in [1,2d - 1])$ are permitted where
\begin{equation}
i \geq d + 1 - a \koz.
\end{equation}
By substitution $a = (q - 1)d$ from (\ref{eqe14}) we get
\begin{equation}
y = \frac{(2qd - 2d + 2r + 1 + i)i}{2d}\koz.
\end{equation}
Here $y$ must be an integer, so transform this formula into
\begin{equation}
y = i(q - d) + \frac{i(2r + 1 + i)}{2d}\koz. \label{eqe15}
\end{equation}
\begin{tetel} If $0 \leq a < b,$ then there exist positive integers $x$ and $y$ satisfying
$$ax \geq \frac{x(x - 1)}{2}$$
and
$$ax + by = \frac{(x + y)(x + y - 1)}{2}\koz.$$
In the following cases there is only one solution:
\begin{itemize}
\item
a = 0;
\item
d = 1;
\item
d = 2.
\end{itemize}
In the following case there are at least two solutions:
\begin{itemize}
\item
$d$ is odd and $3 \leq d \leq a.$
\end{itemize}
\end{tetel}
\begin{biz} a) Existence of a solution.
Let $d = b - a$ and $i = 2d - 2r -1.$ Then $n = 2(b -r),$
$y = q(2d - 2r -1), \ x = q(2r + 1)$ satisfy all requirements.
b) Uniqueness. If $a = 0,$ then $d = b,$ $q = 1$ and $y$ is integer only if $i = 2b - 1.$ So we get the unique
$\langle 0^1, b^{2b - 1} \rangle$ solution.
If $d = 1,$ then only $i = 1$ is permitted, implying the unique solution $\langle a^b,b^b \rangle.$
If $d = 2$ or $d$ is odd, then we also can analyse formula (\ref{eqe15}).
\end{biz}
This theorem left open the case when the difference $d$ is odd and the investigated set is sparse
and also the case when the difference is an even number greater then 2.
\subsection{2-unique score sets\label{subs2unique}}
Now we present a new form of Reid-problem for 2-tournaments.
For a fixed sequence $\mathbf{q}[m]= \langle q_1,\ldots,q_m \rangle$ with $q_1 < \cdots$ $ < q_m$
of positive integers, we shall
denote by $\mathcal{G}(\mathbf{q}[m])$ the set $\mathcal{G}$ of sequences $\mathbf{g} =
\langle g_1,\ldots,g_m \rangle$ such that
$$\sum_{i=1}^{k}q_ig_i~\ge ~ \left(\sum_{i=1}^{k}g_i\right)^2, ~~~ k \in [1:m-1]$$
and
$$\sum_{i=1}^{m}q_ig_i~=~ \left(\sum_{i=1}^{m}g_i\right)^2.$$
Here we also say that \textbf{g} is a solution for \textbf{q.}
We wish to give necessary and sufficient conditions for $\mathbf{q}[m]$ to have a solution that is a nonempty
$\mathcal{G}(\mathbf{q}[m]).$)
\bigskip
\begin{tetel} For the sequence $\mathbf{q}[1]=\langle q_1 \rangle,$ we have
$\mathcal{G}(\mathbf{q}[1])=\langle q_1 \rangle.$
\end{tetel}
\begin{biz} If $\mathbf{q}[1] = \langle q_1 \rangle,$ then it is obvious that the solution
of $q_1 g_1 = g_1^2$ is given in the form $g_1=q_1$. Hence we have $\mathcal{G}(\mathbf{q}[1])=\langle q_1 \rangle.$
\end{biz}
\begin{tetel} Let $\mathbf{q}[2]=\langle q_1,q_2 \rangle$ be a sequence of positive integers
with $d = q_2 - q_1 > 0.$
Then $\mathcal{G}(\mathbf{q}[2])\neq \emptyset$ if and only if either
$d\not\vert (q_1,q_2)$ or $d\vert (q_1,q_2)$ and there is a
prime $p$ such that $p^2\vert d$.
\end{tetel}
\begin{biz} According to the definition of
$\mathcal{G}(\mathbf{q}[m]),$ we need only find positive integers $g_1,g_2$ such that
$q_1 \geq g_1$ and $q_1g_1 + q_2g_2 = (g_1 + g_2)^2.$
Let $q,~r$ be integers for which $q_2 = qd + r,$ where $0\le rq_2 - (q_2 - r) - r = 0$$
and
$$q_1g_1 + q_2g_2 = q_1rq + q_2^2 - q_2r(q + 1)$$
$$ = q_2^2 + r(q_1q - q_2q + q_2) - 2q_2r=$$
$$=(q_2 - r)^2 = (g_1 + g_2)^2.$$
Now assume that $d \vert (q_1,q_2)$ and there is a prime $p$ such that $p^2 \vert d.$ In this case
$r = 0$ and we choose $g_1,~g_2$ as follows:
$$g_1:={q_2 \over p}-{d \over {p^2}}~~\hbox{and}~~g_2:=g_1(p-1)\koz.$$
It is obvious that
$$g_1 > 0,~g_2 > 0~,~g_1 \le R_1$$
and
$$q_1g_1 + q_2g_2 = g_1(q_1 + (p - 1)q_2)$$
$$= g_1(pq_2 - d) =$$
$$= g_1p^2({q_2\over p}-{d\over {p^2}}) = (g_1p)^2 = (g_1 + g_2)^2.$$
Finally, assume that $d = 1$ or $d \vert (q_1,q_2)$ and $d$ is the product of distinct primes.
If there are positive integers $g_1, g_2$ such that $q_1\ge g_1$ and
$q_1g_1 + R_2g_2 = (g_1 + g_2)^2,$ then we have $d \vert g_1 + g_2$ and
$${1 \over d}(g_1 + g_2)^2-{q_1 \over d}(g_1 + g_2) = g_2>0\koz,$$
$${1\over d}(g_1+g_2)^2-{R_2\over d}(g_1+g_2)=-g_1 < 0\koz,$$
consequently
$${q_2\over d} = {q_1 \over d} + 1 > {g_1 + g_2\over d} > {q_1\over d}\koz.$$
This is impossible.
\end{biz}
\begin{tetel}\label{th30two} \emph{Iványi, Phong, 2004} Let $\mathbf{q}[2] = $ be the sequence
of positive integers with conditions $q_1 < R_2,$~$(q_1,q_2)=1$,~$2q_1>q_2$~~and~~$d:=q_2-R_1$~has
$s$ distinct prime factors. Then
$$\vert \mathcal{G}(\mathbf{q}[2]) \vert = 2^s - 1\koz.$$
\end{tetel}
\begin{biz} Since $d = q_2 - q_1 < q_1$ and $(q_1,q_2) = 1,$ the congruence $x^2\equiv q_2x\pmod d$
has $2^s-1$ solutions in positive integers less than $d.$ For each solution $x$ we
set $g_1={x(q_2 - x)\over d}$ and $g_2 = (d - x){q_2 - x\over d}.$
One can check that $g_1, ~ g_2$ satisfy conditions $q_1\ge g_1$ and $q_1g_1 + q_2g_2=(g_1 + g_2)^2.$
\end{biz}
\begin{gyak}
\ujgyak
How many ?
\ujgyak
Design an algorithm
\end{gyak}\index{unicity of score sets|)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Kings and serfs in tournaments\label{sec30Kings1t}}\index{kings and serfs in 1-tournaments|(}
Sociologists are often interested in determining the most \textit{dominant} actors in a social network.
Moreover, dominance in animal societies is an important theme in ecology and population biology.
Social networks are generally modelled as digraphs with vertices representing actors and arcs
representing dominance relations among actors. The concept of ``king''
is very closely related to dominance in digraphs. Kings and serfs were initially introduced
to study dominance in round-robin competitions. These concepts were latter extended to more general
families of digraphs such as multipartite tournaments, quasi-transitive digraphs,
semicomplete multipartite digraphs and oriented graphs. In this section our focus will be on algorithmic
aspects of kings and serfs in tournaments and their applications in majority preference voting.
A king in a tournament dominates every other vertex either directly or through another vertex.
To make the idea more formal we define a \textit{path} of length $k$ from a vertex $u$ to a vertex
$v$ in a tournament (or any digraph) as a sequence of arcs $e_{1}, e_{2},\ldots, e_{k}$ where $u$
is the initial vertex of $e_{1}$, $v$ is the terminal vertex of $e_{k}$ and the terminal vertex of
$e_i$ is the same as the initial vertex of $e_{i+1}$, for all $1\leq i\leq k-1$. If there is a path
of length 1 or 2 from a vertex $u$ to a vertex $v$, then $v$
is said to be \ki{reachable}\inddef{reachable vertex}
from $u$ within two steps. Analogously, if there is a path of length $1,2,\ldots$ or $r$ from $u$ to $v$
then $v$ is said to be reachable from $u$ within $r$ steps.
Let $T$ be an $n$-tournament. A vertex $u$ in $T$ is called an \ki{r-king,}\inddef{rking@$r$-king}
where $1 \leq r \leq n-1,$ if every other vertex $v$ in the tournament is reachable within $r$ steps
from $u.$ A vertex $u$ is called an \ki{r-serf}\index{rserf@$r$-serf} if $u$ is reachable within $r$
if $u$ is reachable within $r$
steps from every other vertex $v$ in $T.$ In particular, a 2-king is simply called a king and a
2-serf is called a serf.
\begin{figure}[!t]
\centering
\includegraphics{kingsandserfs}
\caption{A tournament with three kings $\{u,v,y\}$ and three serfs $\{u,v,x\}.$
Note that $z$ is neither a king nor a serf and $\{u.v\}$ are both kings and serfs.\label{fig:kingsandserfs}}
\end{figure}
S. B. Maurer\nevindex{Maurer, Stephen B.} introduced the dual terms of king and serf in a delightful exposition
of a tournament model for dominance in flocks of chicken. In his influential series of papers
on dominance in animal societies, H. G. Landau\nevindex{Landau, H. G.} proved that every tournament
has a king (although he did not use the word king). In fact, he showed the following.
\begin{tetel}\label{max} \emph{(Landau, 1953)}
Every vertex of maximum score in a tournament is a king.
\end{tetel}
The proof is quite intuitive. Suppose to the contrary that $u$ is a vertex with maximum score in a tournament
$T$ and $u$ is not a king. Then there exists another vertex $v$ in $T$ such that $v$ is not reachable
from $u$ within 2 steps. But this means that $u$ and all out-neighbours of $u$ are reachable
from $v$ in 1 step and so $s(v)>s(u),$ a contradiction. Another classical result by
J. W. Moon\nevindex{Moon, John W.} states that
\begin{tetel}\label{NumberOfKings} \emph{(Moon, 1968)}
A tournament without transmitters (vertices with in-degree 0) contains at least three kings.
\end{tetel}
It is natural to ask if the bound on the number of kings given in Theorem \ref{NumberOfKings} is tight.
The answer is yes, as demonstrated by the following example.
\begin{pelda}\label{threekings} Let $T$ be a tournament with vertex set $\{v_1, v_2,\ldots,v_5\}.$
Let us denote by $(u,v),$ an arc directed from $u$ to $v.$ Suppose that the arc set of $T$
consists of the arcs $(v_3, v_5),$ $(v_4, v_3),$ all arcs of the form $(v_{j-1}, v_{j}),$
with $1< j\leq 5$ and all arcs of the form $(v_{{j+2}},v_{j}),(v_{{j+3}},v_{j}),\ldots,(v_{{n}},v_{j})$
with $j=1,2,4.$ Then it can be easily verified (Exercise \ref{example}) that $T$ has no
transmitters and $v_2,$ $v_3$ and $v_4$ are the only kings in $T.$
\end{pelda}
K. B. Reid\nevindex{Reid, K. Brooks} proved the existence of a tournament with an arbitrary number
of vertices and an arbitrary number of kings, with few exceptions.
\begin{tetel}\label{except} \emph{(Reid, 1982)}
For all integers $n\geq k \geq 1$ there exists a tournament on $n$ vertices with exactly $k$
kings except when $k = 2$ or when $n = k = 4$ (in which case no such $n$-tournament exists).
\end{tetel}
Hence no tournament has exactly two kings. The above theorems can be stated just as well in terms of serfs.
To see this, note that the \textit{converse} $T'$ of a tournament $T,$ obtained by reversing
the arcs of $T,$ is also a tournament and that the kings and serfs of $T$ and $T'$ are interchanged.
The \ki{king set}\inddef{king set} of a tournament consists of all kings in the tournament.
We can define the \ki{serf set}\inddef{serf set} analogously. The problem of determining the king set
of a tournament is very important both for theoretical and practical considerations. In voting theory
literature, political scientists often refer to the uncovered set in majority preference voting.
This uncovered set is actually the king set for the tournament whose vertices consist of the candidates
to be elected and arcs represent the outcomes of the two-way race between candidates.
Here we present a simple polynomial time algorithm for determining the king set of a tournament.
Given an $n$-tournament $T,$ let us define an $n \times n$ matrix $D^{+}_{T}$ as
\begin{equation}\label{outdeg}
(D^+_T)_{ij} = \left \{
\begin{array}{l}
\ 1 \ \ \ \ \hbox{if } (v_i,v_j) \textrm{ is an arc of } T\koz, \\
\ 0 \ \ \ \ \hbox{ otherwise}\koz.
\end{array} \right .
\end{equation}
We call $D^{+}_{T},$ the \textit{out-degree matrix} of $T.$ When there is no danger of ambiguity we will
drop the subscript $T$ and simply denote the out-degree matrix by $D^{+}.$ \textsc{King-Set}
takes a tournament $T(V,A)$ as input, calculates the out-degree matrix $D^{+}$ of $T$ and uses
it to generate the king set $K$ of $T.$ Let $O$ be the $n \times n$ zero matrix and let $I$ be the
$n \times n$ identity matrix.
\begin{alg}{King-Set$(V,A)$}\inddef{\textsc{King-Set}}
1 \' $D^{+} = $\\
2 \' $K = \emptyset$ \\
3 \' \key{for} \= $i = 1$ \key{to} $n$\\
4 \' \> \key{for} \= $j = 1$ \key{to} $n$\\
5 \' \> \> \key{if} \= $(v_{i},v_{j})\in A$ \\
6 \' \> \> \> $(D^{+})_{{ij}} = 1$ \\
7 \' $M = I+D^{+}+(D^{+})^{2}$\\
8 \' $K = \{v_{i} \in V \vert \forall v_{j} \in V, (M)_{{ij}} \neq 0\}$\\
9 \' \> $N_n$ dominates $D^(1)$ \\
9 \' \key{return} $K$
\end{alg}
\subsubsection{Algorithm description}
The algorithm works on the same principle as the algorithm for finding the number of paths,
from one vertex to another, in a digraph (Exercise \ref{path} asks you to derive this algorithm).
The $(i,j)$ entry of the matrix $(D^{+})^{2}$ is equal to the number of paths of length two from vertex
$v_{i}$ to vertex $v_{j}$ (check this!). Therefore, the $(i,j)$ entry of matrix $D^{+}+(D^{+})^{2}$
counts the number of paths of length one or two from $v_{i}$ to $v_{j}$; and if vertex $v_{i}$ is a king,
all entries in the $i^{th}$ row of $I+D^{+}+(D^{+})^{2}$ must be non-zero.
The computational complexity of Algorithm \textsc{King-Set} depends on the way $(D^{+}_{T})^{2}$ is computed.
If naive matrix multiplication is used, the algorithm runs in $\Theta(n^{3})$ time.
However, using the fast matrix multiplication by Coppersmith\nevindex{Coppersmith, Don} and
Winograd,\nevindex{Winograd, Shmuel} the running time can be reduced to $O(n^{2.38}).$
The Reader should note that by using the duality of kings and serfs, \textsc{King-Set} can be adapted
for finding the serf set of a tournament.
\subsubsection{King sets in majority preference voting}
Kings frequently arise in political science literature. A
\ki{majority preference voting}\inddef{majority preference voting} procedure asks each voter to rank
candidates in order of preference. The results can be modeled by a tournament where vertices represent
the candidates and arcs point toward the loser of each two way race, where candidate $u$ defeats
candidate $v$ if some majority of voters prefer $u$ to $v.$ Political scientists are often
interested in determining uncovered vertices in the resulting tournament. A vertex $u$ is said
to \textit{cover}\index{vertex cover} another vertex $v$ if $u$ defeats $v$
and also defeats every vertex that $v$ defeats.
The covering relation is clearly transitive and has maximal elements, called
\ki{uncovered vertices.}\inddef{uncovered vertex} An uncovered vertex $u$ has the strategically
important property that $u$ defeats any other vertex $v$ in no more than two steps, i.e., either
\begin{enumerate}
\item $u$ defeats $v$ or
\item there is some third alternative $w$ such that $u$ defeats $w$ and $w$ defeats $v$.
\end{enumerate}
Thus an uncovered vertex is actually a king. In fact the uncovered set, consisting of all uncovered vertices,
is precisely the set of all kings (see Exercise \ref{uncover}).
The idea behind finding kings in a tournament can be easily extended to finding $r$-kings
for any positive integer $r.$
\begin{alg}{$r$King-Set$(V,A,r)$}\inddef{rKingSet@$r$\textsc{King-Set}}
1 \' $D^{+} = 0$\\
2 \' $K = \emptyset$ \\
3 \' \key{for} \= $i = 1$ \key{to} $n$\\
4 \' \> \key{for} \= $j = 1$ \key{to} $n$\\
5 \' \> \> \key{if} \= $(v_{i},v_{j})\in A$ \\
6 \' \> \> \> $(D^{+})_{{ij}} = 1$ \\
7 \' $M =I+D^{+} + \ldots+(D^{+})^{r}$\\
8 \' $K = \{v_{i} \in V \vert \forall v_{j}\in V, (M)_{{ij}}\neq 0\}$\\
9 \' \key{return} $K$\\
\end{alg}
The above algorithm runs in $O(rn^3)$ if the matrix multiplications are performed naively,
and in $O(rn^{2.38})$ time if fast matrix multiplication is incorporated.
As we have seen, kings dominate in tournaments. However, there exists a stronger notion of dominance
in tournaments in the form of strong kings. Let us write $u\rightarrow v$
to denote that $u$ defeats $v$ in a tournament $T,$ or in other words $(u,v)$ is an arc of $T.$
If $U_{1}$ and $U_{2}$ are disjoint subsets of vertices of $T$ then we write $U_{1}\rightarrow U_{2}$
to denote that all vertices in $U_{1}$ defeat all vertices in $U_{2}.$ We define
$B_{T}(u, v) = \{w\in V-\{u,v\}: u\rightarrow w \mbox{ and } w\rightarrow v\},$ where $V$ denotes
the vertex set of $T.$ Let $b_{T}(u, v) = \vert B_{T}(u, v)\vert.$ When no ambiguity arises,
we drop the subscript $T$ from the notation.
A vertex $u$ in a tournament $T$ is said to be a \ki{strong king}\inddef{strong king} if
$u\rightarrow v$ or $b(u,v)>b(v,u)$ for every other vertex $v$ of $T.$
Note that $b_{T}(u, v)$ is the number of paths of length two through which $v$ is reachable from $u.$
Therefore, $b_{T}(v_{i}, v_{j}) = ((D^{+}_{_T})^{2})_{{ij}},$ where $D^{+}_{T}$ is the out-degree
matrix of $T.$
Obviously, it is not true that every king is a strong king. For example, Figure
\ref{figtwostrongkings} demonstrates a tournament with three kings, namely $x,$ $y$ and $z.$
However, only $x$ and $y$ are strong kings as $b(z,x) < b(x,z).$
Figure \ref{figtwostrongkings} also shows that when searching for the most dominant vertex
in real life applications, a king may not be the best choice (vertex $z$ is a king,
but it defeats only one vertex and is defeated by all other vertices). Therefore, choosing a strong king
is a better option. This intuition is further confirmed by the fact that, in the probabilistic sense
it can be shown that in almost all tournaments every vertex is a king.
\begin{figure}[h]
\centering
\includegraphics{twostrongkings}
\caption{A tournament with three kings and two strong kings}
\label{figtwostrongkings}
\end{figure}
We have already shown that every tournament has a king.
We now prove that every tournament has a strong king.
\begin{tetel}\label{stronking} (???, ????)
Every vertex with maximum score in a tournament is a strong king.
\end{tetel}
\begin{biz} Suppose $u$ is a vertex with maximum score in a tournament $T$ that is not a strong king.
Then there is a vertex $v$ in $T$ such that $v \rightarrow u$ and $b(u,v)\leq b(v,u).$ Let $V$ be
the vertex set of $T.$ Define
\begin{equation*}
W = \{w\in V-\{u,v\}: u\rightarrow w \textnormal{ and } v\rightarrow w\}\koz.
\end{equation*}
Then $s(u) = b(u, v) + \vert W\vert $ and $s(v) = b(v,u) +\vert W\vert + 1.$ This implies that
$s(u) < s(v),$ a contradiction.
\end{biz}
The problem of finding strong kings is no harder than finding kings in tournaments.
Like \textsc{King-Set}, we present a polynomial time algorithm for finding all strong kings
in a tournament using the out-degree matrix $D^+.$
\begin{alg}{Strong-Kings$(V,A)$}\inddef{\textsc{Strong-Kings}}
1 \' $D^+ = 0$\\
2 \' $K = \emptyset$ \\
3 \' \key{for} \= $i = 1$ \key{to} $n$\\
4 \' \> \key{for} \= $j = 1$ \key{to} $n$\\
5 \' \> \> \key{if} \= $(v_{i},v_{j})\in A$ \\
6 \' \> \> \> $D^+_{ij} = 1$ \\
7 \' $M = D^+ + (D^+)^2$\\
8 \' $K = \{ v_i \in V \ \vert \ \forall j (1\leq j\leq n \textnormal{ and } j\neq i), M_{ij} > M_{ji} \}$\\
9 \' \key{return} $K$\\
\end{alg}
\textsc{Strong-Kings} has the same order of running time \textsc{King-Set}.
So far we have been focusing on finding certain type of dominant vertices (like kings and strong kings)
in a tournament. Another very important problem is to construct tournaments with a certain number
of dominant vertices. Maurer posed the problem of determining all 4-tuples $(n,k,s,b)$
for which there exists a tournament on $n$ vertices with exactly $k$ kings and $s$ serfs such
that $b$ of the kings are also serfs. Such a tournament is called an $(n,k,s,b)$-tournament.
For example the tournament given in Figure \ref{figkingsandserfs} is a $(5,3,3,2)$-tournament.
Reid gave the following characterization of such 4-tuples.
\begin{tetel}
Suppose that $n \geq k \geq s \geq b \geq 0$ and $n > 0.$ There exists an $(n,k,s,b)$-tournament
if and only if the following conditions hold.
\begin{enumerate}
\item $n\geq k+s-b$,
\item $s\neq 2$ and $k\neq 2$,
\item either $n= k= s= b\neq 4$ or $n>k$ and $s>b$,
\item $(n,k,s,b)$ is none of $(n,4,3,2)$, $(5,4,1,0)$, or $(7,6,3,2)$.
\end{enumerate}
\end{tetel}
However, the corresponding problem for strong kings has been considered only recently.
For $1\leq k \leq n,$ a tournament on $n$ vertices is called an $(n, k)$-tournament if it has exactly
$k$ strong kings. The construction of $(n,k)$- tournaments follows from the results proved by Chen, Chang, Cheng and Wang in 2004. The results imply the existence of $(n,k)$-tournaments for all $1\leq k\leq n$ satisfying
\begin{eqnarray}
k \neq n - 1, \ \mbox{when } n \mbox{ is odd} \\
\ \ \ \ \ \ \ \ \ k \neq n, \ \ \ \ \ \mbox{when } n \mbox{ is even\koz.}
\end{eqnarray}
Algorithm $nk$-\textsc{Tournament} takes positive integers $n$ and $k$ as input satisfying the constraints
(26.2) and (26.3) and outputs an $(n,k)$-tournament and the set $K$ of its strong kings.
Also for any vertex $u$ of a tournament $T,$ we adopt the notation of Chen et al. in letting
$O(u)$ (respectively, $I(u)$) denote the set of vertices reachable from $u$ in one step
(respectively, set of vertices from which $u$ is reachable in one step). Note that $O(u)$ and $I(u)$
are often referred to as the first out-neighbourhood and first in-neighbourhood of $u$ respectively.
\begin{algN}{$nk$-Tournament$(n,k)$}\inddef{nktournament@$nk$-\textsc{Tournament}}
1 \' $K = \emptyset$ \\
3 \' $T =$ null digraph on $n$ verices\\
4 \' \key{if} \= $k$ is odd\\
5 \' \> $T = T_k$ \\
6 \' \> $K = \{v_{1},\ldots,v_{k}\}$ \\
7 \' \key{if} \= $n \neq k$ \\
8 \' \> \key{for} \= $i = k + 1$ \key{to} $n$ \\
9 \' \> \> $V = V \cup \{v_{i}\}$ \\
10 \' \> \> $A = A\cup \{(u,v_{i}): u\in V - \{v_{i} \} \}$ \\
11 \' \key{if} \= $k$ is even \\
12 \' \> $T = T_{k-1}$ \\
13 \' \> $V = V \cup \{x,y,z \}$ \\
14 \' \> $K = \{v_{1},\ldots,v_{k-3},x\}$ \\
15 \' \> choose $u \in V$ arbitrarily \\
16 \' \> $A = A \cup \{(v,x): v\in O(u)\}$\\
17 \' \> $A = A \cup \{(x,v): v\in \{u,y\} \cup I(u) \}$ \\
18 \' \> $A = A \cup \{(v,y): v\in \{u\}\cup I(u)\cup O(u)\}$ \\
19 \' \> $A = A \cup \{(v,z): v\in \{u\} \cup I(u)\}$ \\
20 \' \> $A = A \cup \{(z,v): v\in O(u)\}$ \\
21 \' \> \key{if} \= $n \neq k + 2$ \\
22 \' \> \> \key{for} \= $i = k + 1$ \key{to} $n$ \\
23 \' \> \> \> $V = V \cup \{v_{i}\}$ \\
24 \' \> \> \> $A = A\cup \{(u,v_{i}): u\in V-\{v_{i}\}\}$ \\
25 \' \key{return} $T,K$
\end{algN}
\subsubsection{Algorithm description} The algorithm consists of performing two separate inductions
to generate an $(n,k)$-tournament, one for odd $k$ and one for even $k.$.
If $k$ is odd then we start by letting $T=T_k,$ the regular tournament on $k$ vertices
(which always exists for odd $k$), and inductively add $n-k$ vertices to $T$ that are defeated
by all the vertices of $T_k.$ Thus the resulting tournament has $n$ vertices and $k$ kings
(the vertices of $T_k$). The construction for even $k$ is a bit more involved. We start with
$T=T_{k-1}.$ Note that every vertex of $T_{k-1}$ has score $m = \textbinom{n-4}{2}.$
We then add three vertices $x,$ $y$ and $z$ and several arcs to $T_{k-1}$ such that for a fixed
existing vertex $u$ of $T_{k-1}.$
\begin{itemize}
\item $O(u) \rightarrow \{x\} \rightarrow \{u,y\}\cup I(u),$
\item $\{u\}\cup I(u)\cup O(u)\rightarrow \{y\} \rightarrow \{x, z\},$
\item $\{u\}\cup I(u)\rightarrow \{z\} \rightarrow O(u).$
\end{itemize}
\begin{figure}[!t]
\centering
\includegraphics{nk}
\caption{Construction of an $(n,k)$-tournament with even $k$.\label{fignk}}
\end{figure}
The resulting tournament $T$ (illustrated in Figure \ref{fignk}) has $k+2$ vertices with scores
$s(x)=\vert I(x)\vert+2=m+2,$ $s(y)=2,$ $s(z)=\vert O(x)\vert = m$ and $s(v) = m+2,$, for all vertices
$v$ of $T_{k-1}.$ Now by Theorem \ref{stronking} all vertices $v$ of $T_{k-1}$ and the new vertex
$x$ are strong kings of $T,$ while $y$ and $z$ are not (Exercise \ref{maxscore}). Thus $T$ is a
$(k+2, k)$-tournament that can now be extended to an $(n,k)$-tournament by adding $n-k-2$
more vertices that are defeated by all the existing vertices of $T$ (just like in the case of odd $k$).
$nk$-\textsc{Tournament} runs in quadratic time as it takes $O(n^{2})$ operations
to construct a regular tournament and the remaining steps in the algorithm are completed in linear time.
\begin{gyak}
\ujgyak\label{path}
The out-degree matrix $D^+$ of an $n$-vertex oriented graph is an $n \times n$ matrix
whose $(i,j)$ entry is given by $d_{ij}=\mbox{number of arcs directed from }v_i \mbox{ to } v_j.$
Describe an algorithm based on the out-degree matrix for finding the number of paths of length
$k s(u).$ which contradicts the choice of $u.$
If $z_0(1-0)x$ and $z_0(0-0)y$ for each $x\in X$ and each $y\in Y,$ then
$s(z_0)\geq 2+2n_1+n_2 = s(u)+2 > s(u),$ again contradicting the choice of $u.$
This establishes the claim, and hence the proof is complete.
\end{biz}
We now consider the problem of finding all weak kings in an oriented graph
(as kings can be determined by applying Algorithm \ref{KingSet1}). Let $D^{-}$ and $D^{+}$
respectively denote the in-degree and out-degree matrix of an oriented graph $D(V,A)$ with $n$ vertices.
Also let $O$ and $J$ denote the $n \times n$ zero matrix and all-ones matrix respectively.
\begin{algN}{Weak-Kings$(V,A)$}\inddef{\textsc{Weak-Kings}}
1 \' $D^+ = 0$\\
2 \' $D^- = 0$\\
3 \' $K = \emptyset$ \\
4 \' \key{for} \= $i = 1$ \key{to} $n$ and $j = 1$ \key{to} n\\
5 \' \> \key{for} \= $j = 1$ \key{to} $n$\\
6 \' \> \> \key{if} \ \ \ \= $(v_{i},v_{j})\in A$ \\
7 \' \> \> \> $D^+_{ij} = 1$ \\
8 \' \> \> \key{else} \> \key{if} \= $(v_{i},v_{j}) \in A$ \\
9 \' \> \> \> \> $D^-_{ij} = 1$ \\
10 \' $M = J - D^-$ \\
11 \' $M = D^+ + (D^+)^2$\\
12 \' $N = M + M D^+ + D^+ M$ \\
13 \' $K = \{v_i \in V \ \vert \ \forall v_j \in V, (N)_{ij} \neq 0 \}$ \\
14 \' \key{return} $K$\\
\end{algN}
Algorithm \ref{WeakKings} returns the set of all weak kings of an oriented graph. Exercise \ref{weak}
asks you to prove that the algorithm works correctly and to determine its running time.
Indeed, it is also possible to extend Theorem \ref{NumberOfKings} to weak kings in oriented graphs
as an oriented graph $D$ without transmitters (vertices of in-degree 0) has at least three weak kings.
To see this let $u$ be a vertex of maximum score in the oriented graph $D$.
Clearly, by Theorem \ref{maxweak}, $u$ is a weak king. As $D$ has no transmitters,
there is at least one vertex $v$ such that $v(1-0)u.$ Let $S$ be the set of these vertices $v,$
and let $v_{1}$ be a vertex of maximum score in $S.$ Let $X,$ $Y$ and $Z$ respectively be the set
of vertices $x,$ $y$ and $z,$ other than $u,$ with $v_{1}(1-0)x,$ $v_{1}(0-0)y$ and $v_{1}(0-1)z.$
Assume that $\vert X\vert=n_{1},$ $\vert Y\vert=n_{2},$ and $\vert Z\vert=n_{3}$ so that
$s(v_1) = 2n_1 + n_2 + 2.$ We note that all vertices of $Z$ are weakly reachable within two steps from
$v_1.$ If this is not the case, let $z_0$ be a vertex which is not weakly reachable within two steps
from $v_1.$ Then $z_0(1-0)u,$ and (a) $z_{0}(1-0)x$ and (b) $z_{0}(1-0)y$ or $z_{0}(0-0)y$
for each $x \in X$ and each $y \in Y.$
If for each $x$ in $X$ and each $y$ in $Y,$ $z_{0}(1-0)x$ and $z_{0}(1-0)y,$ then $s(z_0) \geq 2n_1 + 2n_2 + 4
= s(v_1) + n_2 + 2 > s(v_1).$ This contradicts the choice of $v_1.$ If for each $x$ in $X$ and each
$y$ in $Y,$ $z_0(1-0)x$ and $z_0(0-0)y,$ then $s(z_{0}) \geq 2n_1 + n_2 + 4 > s(v_1),$
again contradicting the choice of $v_1.$ This establishes the claim, and thus $v_1$ is also a weak king.
Now let $W$ be set of vertices $w$ with $w(1-0)v_1$ and let $w_1$ be the vertex of maximum score in $W.$
Then by the same argument as above, every other vertex in $D$ is weakly reachable within two steps from $w_1,$
and so $w_1$ is a weak king. Since $D$ is asymmetric, and in $D$ we have $w_1(1-0)v_1$ and $v_1(1-0)u,$
therefore $u,$ $v_1$ and $w_1$ are necessarily distinct vertices. Hence $D$ contains at least three weak kings.
Although, no oriented graph with 4 vertices and exactly 4 kings exists, it is possible to generate
an oriented graph on $n$ vertices with exactly $k$ weak kings, for all integers $n \geq k \geq 1.$
The following algorithm constructs such an oriented graph.
\begin{algN}{$k$-Weak-Kings$(n,k)$}\inddef{nkweakkings@$nk$-\textsc{Weak-Kings}}
1 \' $V = \{ x, y, u_1, u_2, \ldots, u_{n-2} \}$ \\
2 \' $x(0-0)y$ \\
3 \' \key{if} \= $k > 2$ \\
4 \' \> \key{for} \= $i = 1$ \key{to} $n - 2$ \\
5 \' \> \> $u_i(1-0)x $ \\
6 \' \> \> $u_i(0-1)y$ \\
7 \' \> \> \\
8 \' \> \key{for} \> $i = n - 3$ \key{downto} $k - 2$ \\
9 \' \> \> $u_{n-2}(1-0)u_i$ \\
10 \' \> \key{for} \> $i = k - 3$ \key{downto} $1$ \\
11 \' \> \> $u_{n-2}(0-0)u_i$ \\
12 \' \> $K = \{ x,y,u_{n-2} \} \cup \{ u_i \ \vert \ i = 1, \ldots, k-3 \}$ \\
13 \' \> \key{else} \= \key{if} \ \ \ \= $k = 2$ \\
14 \' \> \> \> \key{for} \= $i = 1$ \key{to} $n - 2$ \\
15 \' \> \> \> \> $x(1-0)u_{i}$ \\
16 \' \> \> \> \> $y(1-0)u_{i}$ \\
17 \' \> \> \> \key{for} \= $j = 1$ \key{to} $n - 2$ \\
18 \' \> \> \> \> \key{if} \= $i \neq j$ \\
19 \' \> \> \> \> \> $u_i(0-0)u_j$ \\
20 \' \> \> \> $K = \{ x,y \} $ \\
21 \' \> \> \key{else} \> $x(1-0)u_i$ \\
22 \' \> \> \> $u_1(1-0)y$ \\
23 \' \> \> \> \key{for} \= $i = 2$ \key{to} $n - 2$ \\
24 \' \> \> \> \> $u_1(1-0)u_i$ \\
25 \' \> \> \> \> $x(1-0)u_i$ \\
26 \' \> \> \> \> $y(1-0)u_i$ \\
27 \' \> \> \> $K = \{ u_1 \}$ \\
28 \' \key{return} $V,A,K$\\
\end{algN}
\subsubsection{Algorithm description}
When $k = n,$ the algorithm defines the arcs of a 2-tournament $D$
with vertex set $V = \lbrace x, y, u_{1}, u_{2},\cdots, u_{n-2}\rbrace$ as
$x(0-0)y,$
$u_{i}(1-0)x$ and $u_{i}(0-1)y$ for all $1\leq i\leq n-2,$
$u_{i}(0-0)u_{j}$ \ for all $i\neq j$ and $1\leq i \leq n-2$, $1\leq j\leq n-2,$
Clearly, $x$ is a weak king as $x(0-0)y$ and $x(0-0)y(1-0)u_{i}$ for all $1\leq i\leq n-2.$.
Also $y$ is a weak king as $y(0-0)x$ and $y(1-0)u_{i}$ for all $1\leq i\leq n-2.$
Finally, every $u_{i}$ is a weak king, since $u_{i}(0-0)u_{j},$ for all $i\neq j$ and $u_{i}(1-0)x$
and $u_{i}(1-0)x(0-0)y.$ Thus $D$ contains exactly $n$ weak kings.
If $n=k-1,$ the algorithm creates one additional arc $u_{n-2}(1-0)u_{n-3}$ in $D.$
The resulting oriented graph contains exactly $n-1$ weak kings, since now $u_{n-2}$
is not weakly reachable within two steps from $u_{n-3}$ and so $u_{n-3}$ is not a weak king.
If $n=k-2$ then the algorithm creates two additional arcs in $D.$ namely $u_{n-2}(1-0)u_{n-3}$ and
$u_{n-2}(1-0)u_{n-4}.$ Thus $D$ now contains exactly $n-2$ weak kings, with $u_{n-3}$ and $u_{n-4}$
not being weak kings.
Continuing in this way, for any $3\leq k\leq n,$ the algorithm creates new arcs $u_{n-2}(1-0)u_{i}$
in $D$ for all $k-2\leq i\leq n-3.$ The resulting graph $D$ contains exactly $k$ weak kings.
If $k=2,$ then $D$ is constructed so that $x(0-0)y,$ $x(1-0)u_{i}.$ $y(1-0)u_{i}$ and $u_{i}(0-0)u_{j}$
for all $1\leq i\leq n-2,$ $1\leq j\leq n-2$ and $i\neq j.$ Thus $D$ contains exactly two weak kings $x$ and $y.$
Finally, $D$ has exactly one weak king if it is constructed such that $x(0-0)y,$ $u_{1}(1-0)x,$
$u_{1}(1-0)y$ and $u_{1}(1-0)u_{i},$ $x(1-0)u_{i}$ and $y(1-0)u_{i}$ for all $2\leq i\leq n-2.$
Due to the nested \key{for} loops the algorithm runs in $O(n^{2})$ time.
Figure \ref{figp2a} shows a 6 vertex oriented graph with exactly 6 weak kings, Figure \ref{figp2b}
shows a 6 vertex oriented graph with exactly 5 weak kings namely $x,$ $y,$ $v_{1},$ $v_{2}$ and
$v_{4},$ Figure \ref{figp2c} shows a 6 vertex oriented graph with exactly 4 weak kings namely $x,$
$y.$ $v_{1}$ and $v_{4}.$ Figure \ref{figp2d} shows a 6 vertex oriented graph with exactly 3 weak kings
namely $x,$ $y$ and $v_4$ and Figure \ref{figp2e} shows a 6 vertex oriented graph with exactly
2 weak kings namely $x$ and $y.$
The directional dual of a weak king is a weak serf, and thus a vertex $u$ is a weak king of
an oriented graph $D$ if and only if $u$ is a weak serf of $\bar{D},$ the converse of $D.$
So by duality, there exists an oriented graph on $n$ vertices with exactly $s$ weak serfs for all integers
$n \geq s \geq 1.$ If $n = k \geq 1,$ then every vertex in any such oriented graph is both a weak king
and a weak serf. Also if $n > k \geq 1,$ the oriented graph described in algorithm $k$\textsc{WeakKings}
contains vertices which are both weak kings and weak serfs, and also contains vertices which are
weak kings but not weak serfs and vice versa. These ideas give rise to the following problem.
For what 4-tuples $(n, k, s, b)$ does there exist an oriented graph with $n$ vertices,
exactly $k$ weak kings, $s$ weak serfs and that exactly $b$ of the weak kings are also serfs?
By analogy with $(n, k, s, b)$-tournaments, such oriented graphs are called
$(n, k, s, b)$-oriented graphs. Without loss of generality, we assume that $k \geq s.$
The following results by Pirzada\nevindex{Pirzada, Shariefuddin} and
Shah\nevindex{Shah, N. A.} address this problem.
\begin{tetel}\label{nkss} \emph{(Pirzada, Shah, 2008)}
If $n > k \geq s \geq 0,$ then there exists no $(n, k, s, s)$-oriented graph.
\end{tetel}
\begin{tetel}\label{nksb} \emph{(Pirzada, Shah, 2008)}
There exist $(n, k, s, b)$-oriented graphs, $n \geq k \geq s > b \geq 0$ and $n > 0,$ $n \geq k + s - b.$
\end{tetel}
\begin{biz} Let $D_1$ be the oriented graph with vertex set $\lbrace x_1, y_1, u_1, u_2,
\cdots ,u_{k-b-2}\rbrace$ and $x_1(0-0)y_1,$ $u_{i}(1-0)x_{1},$ $u_{i}(0-1)y_{1}$ for all
$1 \leq i \leq k-b-2,$ and $u_{i}(0-0)u_{j}$ for all $i\neq j.$
Take the oriented graph $D_2$ with vertex set $\lbrace x_2, y_2, v_1, v_2, \ldots, v_{b-2}\rbrace$
and arcs defined as in $D_1.$ Let $D_3$ be the oriented graph with vertex set $\lbrace z_1, z_2,
\ldots,z_{s-b}\rbrace$ and $z_i(0-0)z_j$ for all $i, j.$ Let $D$ be the oriented graph
$D_1 \cup D_2 \cup D_3$ (see Figure \ref{figp3}) with\\
$z_i(1-0)y_2$ \ for $1 \leq i \leq s - b$
$z_i(0-0)x_2$ \ for $1 \leq i \leq s - b$
$z_i(0-0)v_j$ \ for $1 \leq i \leq s-b,$ $1 \leq j \leq b - 2$
$x_1(1-0)z_i,$ \ $y_1(1-0)z_i$ for $1 \leq i \leq s - b$
$u_r(0-0)z_i$ \ for $1 \leq r \leq k-b-2,$ $1 \leq i \leq s - b$
$x_1(1-0)y_2,$ \ $y_1 (1-0)y_2$
$v_r(1-0)y_2$ \ for $1 \leq r \leq k - b - 2$
$x_1(0-0)x_2,$ \ $y_1(0-0)x_2$
$v_r(0-0)v_j,$ \ for $1 \leq r \leq k - b - 2,$ $1 \leq j \leq b-2.$
\begin{figure}[!t]
\centering
\includegraphics[width=12cm,height=9cm]{p3}
\caption{Construction of an $(n, k, s, b)$-oriented graph.}
\label{figp3}
\end{figure}
Clearly $D$ contains exactly $k$ weak kings and the weak king set is $\lbrace x_1, y_1\rbrace\cup\lbrace
u_1, u_2,\ldots, u_{k-b-2}\rbrace\cup\lbrace x_2, y_2\rbrace\cup\lbrace v_1, v_2,\ldots,
v_{b-2}\rbrace.$ $D$ contains exactly $s$ weak serfs with the weak serf set
as $\lbrace x_2, y_2\rbrace\cup\lbrace v_1, v_2, \ldots, v_{b-2}\rbrace\cup\lbrace z_1, z_2,\ldots,
z_{s-b}\rbrace.$ Also from these $k$ weak kings, exactly $b$ are weak serfs. The weak king-serf set
is $\lbrace x_2, y_2\rbrace\cup\lbrace v_1, v_2,\ldots, v_{b-2}\rbrace.$
\end{biz}
Exercise \ref{do} asks the reader to derive an algorithm for generating an $(n,k,s,b)$-oriented graph
when the hypothesis of Theorem \ref{nksb} is satisfied.
\begin{gyak}
\ujgyak\label{exactlytwokings}
Give an algorithm that generates an oriented graph with $n$ vertices and exactly 2 kings.
Prove the correctness of your algorithm.
\ujgyak\label{counterex}
Draw the graph $D^*$ discussed in Example \ref{counterexample}.
\ujgyak\label{weak}
Prove that \textsc{Weak-Kings2} is correct. Also determine its runtime.
\ujgyak\label{weak2}
Construct an oriented graph with six vertices and exactly one king.
\ujgyak\label{do}
Derive an algorithm that takes a 4-tuple $(n,k,s,b)$ satisfying the hypothesis of Theorem \ref{nksb}
as input and generates an $(n,k,s,b)$-oriented graph. Analyze the performance of your algorithm.
\end{gyak}\index{weak kings in 2-tournaments|)}
\begin{fld}
\ujfld{Optimal reconstruction of score sets\label{Optimalscoreset}}
{In connection with the reconstruction of graphs the basic questions are the existence and the construction
of at least one corresponding graph. These basic questions are often solvable in polynomial time. In given sense
optimal reconstruction is usually a deeper problem.
a) Analyse Exercise \ref{regular} and try to find a smaller tournament with score set $\{0,1,3,6,10\}$.
b) Write a back-track program which constructs the smallest tournament whose score set is $\{0,1,3,6,10\}$.
c) Write a back-track program which constructs the smallest tournament arbitrary given score set.
d) Estimate the running time of your programmes.
\textit{Hint.} Read Yoo's proof.}
\ujfld{Losing set\label{loosingset}}
{We define the \ki{losing score}\felindex{losing score} of a vertex
as the in-degree of the vertex. The \textit{loosing score set}\felindex{losing score set}
of a tournament is the set of in-degrees of its vertices.
a) Give an argument to show that any set of nonnegative integers is the loosing score set of some tournament.}
b) Given a set $L = \{r_{1},r_{2},\ldots,r_{n}\}$ of nonnegative integers with
$r_{1} < r_{2} - r_{1} < r_{3} - r_{2} < \cdots < r_{n} - r_{n-1},$ write an algorithm to generate a tournament
with loosing score set $L.$
\ujfld{Imbalance set\label{imbalanceset}}
{Let}
\ujfld{Unicity\label{imbalanceset}}
{Let}
\ujfld{generalized weak kings}\label{strongabkings}
{Extend the definition of strong kings to $(a,b)$-tournaments and give sufficient conditions of the existence of
the defined new types of kings.}
\ujfld{generalized weak kings}\label{weakabkings}
{Extend the definition of weak kings to $(a,b)$-tournaments and give sufficient conditions of the existence of
the defined new types of kings.}
\end{fld}
\begin{fejmegj}{\label{secChapterNotes}}
Many classical ans several contemporary graph theory textbooks are available to Readers. Such books are e.g.
the books of Dénes Kőnig\nevindex{Kőnig, Dénes (1884--1944)} \cite{Konig1936},
Claude Berge\nevindex{Berge, Claude (1926--2002)} \cite{Berge1976} and
László Lovász\nevindex{Lovász, László} \cite{Lovasz1979}.
However, there is a dearth of books
focusing on recent advances in the theory of digraphs. The book due to
Bang-Jensen\nevindex{Bang-Jensen, J{\o}rgen} and Gutin \nevindex{Gutin, Gregory} \cite{BangG2009}
probably comes closest and the Reader can refer to it for a comprehensive treatment of the theoretical
and algorithmic aspects of digraphs.
The books by Harary,\nevindex{Harary, Frank}
Norman\nevindex{Norman, R. Z.} and Cartwright\nevindex{Cartwright, D.} \cite{HararyNC1965},
and Chartrand,\nevindex{Chartrand, Gary} Lesniak\nevindex{Lesniak, Linda} and Zhang\nevindex{Zhang, Ping}
\cite{ChartrandL2005,ChartrandLZ2010}, Gross and Yellen \cite{GrossY2004}
present introductory material on tournaments and score structures.
Moon's\nevindex{Moon, John W.} book on tournaments \cite{Moon1968}
is also a good resource but is now out of print.
The books A. Schrijver\nevindex{Schrijver, Alexander} \cite{Schrijver2003} and
A. Frank\nevindex{Frank, András} \cite{Frank2011} contain reach material on optimization problems
connected with directed graphs.
The algorithms discussed in this chapter are not commonly found in literature.
In particular the algorithms presented here for constructing tournaments and oriented graphs
with special properties are not available in textbooks. Most of these algorithms are based on
fairly recent researchs on tournaments and oriented graphs.
Majority of the researches connected with score sequences and score sets were inspired by the work of
H. G. Landau,\nevindex{Landau, H. G.} K. B. Reid\nevindex{Reid, K. Brooks} and
J. W. Moon.\nevindex{Moon, John W.} For classical and recent results in this area we refer
to the excellent surveys by Reid \cite{Reid1978,Reid1996,Reid2004}.\nevindex{Reid, K. Brooks}
Landau's pioneering work on kings and score structure
appeared in 1953 \cite{Landau1953}. Reid stated his famous score set conjecture in \cite{Reid1978}.
Partial results were proved by M. Hager\nevindex{Hager, Michael} \cite{Hager1986}.
Yao's proof of Reid's conjecture appeared in English in 1989 \cite{Yao1989}.\nevindex{Yao, Tianxing} The comment
of Q. Li\nevindex{Li, Qiao} on Reid's conjecture and Yao's proof was published in 2006 \cite{Li2006}.
The construction of a new special tournament
with a prescribed score set is due to Pirzada and Naikoo \cite{PirzadaN2006}. The score structure
for 1-tournaments was introduced by H. G. Landau \cite{Landau1953} and extended for $k$-tournaments
by J. W. Moon in 1963. This result of Moon later was reproved by Avery for $k = 2$ \cite{Avery1991}
and for arbitrary $k$ by Kemnitz and Dolff \cite{KemnitzD1997}. Score sets of oriented graphs were investigated
by Pirzada and Naikoo in 2008 \cite{PirzadaN2008}.\nevindex{Naikoo, Tariq A.}\nevindex{Pirzada, Shariefuddin}
Authors of a lot of papers investigated the score sets of different generalized tournament, among others Pirzada,
Naikoo and Chisthi\nevindex{Chisthi, T. A.} in 2006 (bipartite graphs),\index{bipartite graph}
Pirzada and Naikoo in 2006 \cite{PirzadaN2006AKCE} ($k$-partite graphs),\index{kpartite graph@$k$-partite graph}
Pirzada and Naikoo in 2006 \cite{PirzadaN2006App}
($k$-partite graphs).\index{kpartite tournaments@$k$-partite tournaments} Pirzada,
Naikoo and Dar\nevindex{Dar, F. A.} analyzed signed degree sets\index{signed degree set}
of signed bipartite graphs\index{signed bipartite graph} \cite{PirzadaND2008}.
The basic results on kings are due to K. Brooks Reid\nevindex{Reid, K. Brooks}
\cite{Reid1980,Reid1982,Reid1996,Reid2004} and Vojislav Petrovi\'c\nevindex{Petrovi\'c, Vojislav}
\cite{BrcanovP2010,Petrovic1995,Petrovic1997,PetrovicT1991,PetrovicT1998}.
The problem of the unicity of score sequences was posed and studied by Antal Iványi\nevindex{Iványi, Antal Miklós}
and Bui Minh Phong\nevindex{Phong, Bui Minh} \cite{IvanyiB2004}. Another unicity results connected with
tournaments was published e.g. by P.\nevindex{Tetali, Prasad} Tetali, J. W. Moon\nevindex{Moon, John W.}
and recently by Chen\nevindex{Chen, An-Hang} et al. \cite{Chen2007,ChenCCW2008,Moon1982,Tetali1998}.
The term king in tournaments was first used by Maurer\nevindex{Maurer, Stephen B.} \cite{Maurer1980}. Strong kings
were introduced by Ho\nevindex{Ho, Ting-Yem} and Chang\nevindex{Chang, Jou-Ming}
\cite{HoC2003} and studied later by Chen et al.\nevindex{Chen, An-Hang} \cite{Chen2007,ChenCCW2008},
while Pirzada and Shah\nevindex{Shah, N. A.} \cite{PirzadaS2008} introduced
weak kings in oriented graphs. The problems connected with 3-kings\index{threeking@3-king}
and 4-kings\index{fourking@4-king} were discussed by Tan in \cite{Tan2006} and
the construction of tournaments with given number of strong kings by Chen et al. in \cite{ChenCCW2008}.
The difference of the out-degree and of the in-degree of a given vertex is called
\textit{the imbalance} of the given vertex. The imbalance set\index{imbalance set}
of directed multigraphs were studied
by Pirzada, Naikoo, Samee\nevindex{Samee, U.} and Iványi\nevindex{Iványi, Antal Miklós}
in \cite{PirzadaNSI2010}, while the imbalance sets of multipartite oriented graphs by Pirzada,
Al-Assaf\nevindex{Al-Assaf, Abdulaziz M.} and Kayibi \cite{PirzadaAK2011}.\nevindex{Kayibi, Koko K.}
In connection with Problem \ref{Optimalscoreset} see \cite{Ivanyi2009,Ivanyi2010}\nevindex{Iványi, Antal Miklós}
Problem 2
Problem 3
Problem 4
Problem 5
Problem 6
An interesting new direction is proposed by "L. B. Beasley,\nevindex{Beasley, LeRoy B.}
D. E. Brown,\nevindex{Brown, David E.} and. K. B. Reid\nevindex{Reid, K. Brooks}
in \cite{BeasleyBR2009}: the problem
is the reconstruction of tournaments on the base of the partially given out-degree matrix.
\end{fejmegj}
\bibliography{AlgofInf3-11February}
This bibliography is made by HBib\TeX. First key of the sorting is the name of
the authors (first author, second author etc.), second key is the year of publication,
third key is the title of the document.
Underlying shows that the electronic version of the bibliography on the home page of the book
contains a link to the corresponding address.
\bibliographystyle{algofinf}
\begin{printindex}
This index uses the following conventions. Numbers are alphabetised as if spelled out; for example,
``2-3-4-tree'' is indexed as if were ``two-three-four-tree''.
When an entry refers to a place other than the main text, the page number is followed by a tag:
\textit{exe} for exercise, \textit{exa} for example, \textit{fig} for figure, \textit{pr}
for problem and \textit{fn} for footnote.
The numbers of pages containing a definition are printed in \textit{italic} font, e.g. \\
time complexity, \underline{\textit{583}}.
\end{printindex}
\begin{printnevindex}
This index uses the following conventions. If we know the full name of a cited person, then
we print it. If the cited person is not living, and we know the correct data, then we print also the
year of her/his birth and death.
\end{printnevindex}
\end{document}