Binary 1-factorization:
The binary 1-factorization is an 1-factorization
(F1,F2,..., Fn-1) of the
complete graph Kn with even n
where the nodes are partitioned into two subsets with n/2 elements.
Breaks:
A break occurs if a team has two consecutive home or away games
in two consecutive rounds (then the alternating sequence of home and away
games in the home-away pattern of the team is broken).
Canonical 1-factorization:
The canonical 1-factorization is an 1-factorization
(F1,F2,..., Fn-1) of the
complete graph Kn with even n.
The 1-factor Ft (t=1,...,n-1) contains the edge [n,t] and all
edges [(t+k) mod (n-1), (t-k) mod (n-1)] for k=1,...,n/2-1
(where the numbers 1,...,n-1 have to be taken in the mod-expressions).
For odd n after introducing a dummy node n+1 the construction for an
even number of nodes can be applied.
Carry-over effect:
Team i gives a so-called carry-over effect to team j if some other
team k plays first against i in some round t and immediatly after that against
team j in round t+1, where the rounds are considered cyclically (i.e. the
first round 1 follows the last round n-1).
If several teams play consecutively against i and j and i is a very strong
or weak team, team j may be handicapped or favoured compared with other teams.
In an `ideal' schedule with respect to balanced carry-over effects no teams
i,j,k,l should exist such that teams k and l both play against team j
immediately after playing against team i.
The best balanced schedules known so far are based on the algebraic
structure of a starter.
Complementary teams:
In sports tournaments with home-away assignments complementary teams
are teams with complementary
home-away patterns (i.e. one team plays at home if and only
if the other team plays away).
Complete graph:
The complete graph Kn is a graph
consisting of n nodes and n(n-1)/2 edges between all pair of nodes.
Directed canonical 1-factorization:
The directed canonical 1-factorization is the directed (oriented)
version of the canonical 1-factorization
(F1,F2,..., Fn-1) of the
complete graph Kn with even n.
The 1-factor Ft (t=1,...,n-1) contains the edge [n,t] and all
edges [(t+k) mod (n-1), (t-k) mod (n-1)] for k=1,...,n/2-1
(where the numbers 1,...,n-1 have to be taken in the mod-expressions).
The edge [n,t] is oriented into (t,n) if t is odd, and
(n,t) if t is even.
The edge [(t+k) mod (n-1), (t-k) mod (n-1)] for k=1,...,n/2-1
is oriented into the arc ((t+k) mod (n-1), (t-k) mod (n-1)) when k is odd
and the other way round, when k is even.
For odd n after introducing a dummy node n+1 the construction for an
even number of nodes can be applied.
Schedules constructed from the directed canonical 1-factorization have
a minimum number of breaks: n-2 for even n and 0 for odd n.
Double Round Robin Tournament (DRRT):
In a double round robin tournament (DRRT) each team plays against each
other team exactly twice. The tournament is divided into two half series,
where in each half series a SRRT is scheduled (with
different home teams).
A DRRT with n teams may be scheduled as a mirrored DRRT
with at least 3(n-2) breaks or according to the
English System with 2(n-2) breaks.
Edge coloring:
An edge coloring of a graph G=(V,E) is an
assignment of colors to all edges from the set E such that edges with
a common node receive different colors.
English system:
The English system is used for a DRRT when
the number of breaks is to be minimized. The first
round of the second half series is the same as the last round of the first
half series, afterwards the rounds are scheduled in the same order as in the
first half series. This system ensures that for n teams only 2(n-2) breaks
are needed.
Graph:
An (undirected) graph G=(V,E) consists of a finite set V of nodes
(vertices) i=1,..,|V| and a set E of (undirected) edges, where each
edge [i,j] is an unordered pair of different elements i,j from V.
A directed graph G=(V,E) consists of a finite set V of nodes (vertices)
i=1,..,|V| and a set E of (directed) arcs, where each arc (i,j) is an
ordered pair of different elements i,j from V.
Graph model:
A single round robin tournament SRRT for n teams
can be represented by the complete graph Kn.
While the nodes i=1,...,n represent the teams, the edge [i,j] models the
game between teams i and j.
A schedule corresponds to an edge coloring of the
Kn with n-1 colors, i.e. an 1-factorization
(F1,F2,..., Fn-1), where the 1-factor
Ft consists of n/2 non-adjacent edges corresponding to the games
scheduled in round t.
If additionally home-away patterns have to be calculated,
the edge [i,j] is oriented into the arc (i,j) for a home game of team j and
into the arc (j,i) for a home game of team i.
Groups:
In tournaments with groups the n teams are partitioned into g groups
(e.g. according to their strengths) where all groups contain n/g teams.
The objective is to find
group-changing or even
group-balanced schedules.
Group-balanced schedule:
In group-balanced schedules for tournaments with g
groups no team plays more than once against teams
of the same group within g consecutive games.
A group-balanced schedule exists if and only if n is odd or n and n/g are
both even.
A weaker form are group-changing schedules.
Group-changing schedule:
In group-changing schedules for tournaments with g
groups no team plays two consecutive games
against teams of the same group. More restricted are
group-balanced schedules.
Home-away pattern (HAP):
A home-away pattern for a team states for every round whether the
team plays at home or away. Usually, home-away patterns with alternating
sequences of home and away games (i.e. without breaks)
are prefered.
Mirrored Double Round Robin Tournament:
A mirrored double round robin tournament is a DRRT
where the rounds of the second half series are scheduled in the same order
as in the first half series. For n teams such schedules have at least 3(n-2)
breaks.
Oberwolfach problem:
In the Oberwolfach problem (cf. e.g.
Colbourn & Dinitz (2006)) the
complete graph Kn with odd n
and integers l1,...,lt >=3 with
l1+...+lt=n are given. The question is whether the
edges of Kn can be decomposed
into (n-1)/2 2-factors where each 2-factor consists of t cycles
with lengths l1,...,lt.
One-factorization (1-factorization):
An 1-factorization of a graph G=(V,E) is a
partitioning of the edge set E into edge-disjoint 1-factors
(F1,F2,..., Ff) with f=2|E|/|V|, where
each 1-factor Fk is a subset of edges such that
every node is incident to exactly one edge in Fk.
Opponent schedule:
In an opponent schedule the rows are indexed by teams, the columns
by rounds. The entry opp[i][t] contains the team j against which i
plays in round t.
In sports tournaments with home-away assignments the entry opp[i][t]
is j if the game is a home game for team i and -j if the game is a home
game for team j.
Other representations of schedules are slot schedules
or table schedules.
Rounds:
In sports tournaments rounds are the days when games are played.
If the number n of teams is even, usually n-1 rounds are
used; if n is odd, schedules contain n rounds.
Single Round Robin Tournament (SRRT):
In a single round robin tournament (SRRT) each team plays against
each other team exactly once. If the number n of teams
is even, the schedules contain n-1 rounds and each team
plays exactly one game in each round.
If n is odd, the schedules contain n rounds and in each round one team has a
bye (i.e. it does not play).
For even n schedules have at least n-2 breaks,
for odd n schedules without any breaks exist.
Slot schedule:
In a slot schedule the rows and columns are indexed by teams.
The entry slot[i][j] contains the round t in which teams i and j
play against each other.
In sports tournaments with home-away assignments the entry slot[i][j]
is t if the game is a home game for team i and -t if the game is a home
game for team j.
Other representations of schedules are opponent schedules
or table schedules.
Starter:
The pairs {x1, y1},...,{xn-1, yn-1} form a starter
in the additive group (Zn-1,+) if
* the numbers
x1,...,xn-1, y1,...,yn-1
are precisely all elements of Zn-1 without 0,
* the differences
(x1-y1),...,(xn-1-yn-1),
(y1-x1),...,(yn-1-xn-1)
are also precisely all the nonzero elements of Zn-1.
Any starter along with the pair {0,infinity} gives the first round of a
cyclic schedule in which the teams xi
have to play against yi for i =1,...,n-1.
Starters are used for schedules balancing
carry-over effects.
Table schedule:
In a table schedule columns are indexed by rounds. Column t
contains all games i-j which are scheduled in round t.
In sports tournaments with home-away assignments the entry i-j means a
home game for team i, the entry j-i means a home game for team j.
Other representations of schedules are opponent schedules
or slot schedules.
Teams:
In sports tournaments teams (e.g. in soccer, icehockey) or individual
players (e.g. in tennis, tabletennis) play games against each other.
In this web application all teams are identified by the numbers 1,...,n.
Two-factorization (2-factorization):
A 2-factorization of a graph G=(V,E) is a
partitioning of the edge set E into edge-disjoint 2-factors
(F1,F2,..., Ff) with f=4|E|/|V|, where
each 2-factor Fk is a subset of edges such that
every node is incident to exactly two edges in Fk.
|
|
