Suppose n teams play each other, and let Team 
In general, let 
- Construct the list of spanning trees of
- Construct the sublist of Hamiltonian paths (from the spanning trees of maximum degree 2).
- For each Hamiltonian path, compute the associated upset number: the total number of edges transversal in
- Locate a Hamiltonian for which this upset number is as large as possible.
Use this sagemath/python code to compute such a Hamiltonian path.
def hamiltonian_paths(Gamma, signed_adjacency_matrix = []):
"""
Returns a list of hamiltonian paths (spanning trees of
max degree <=2).
EXAMPLES:
sage: Gamma = graphs.GridGraph([3,3])
sage: HP = hamiltonian_paths(Gamma)
sage: len(HP)
20
sage: A = matrix(QQ,[
[0 , -1 , 1 , -1 , -1 , -1 ],
[1, 0 , -1, 1, 1, -1 ],
[-1 , 1 , 0 , 1 , 1 , -1 ],
[1 , -1 , -1, 0 , -1 , -1 ],
[1 , - 1 , - 1 , 1 , 0 , - 1 ],
[1 , 1 , 1 , 1 , 1 , 0 ]
])
sage: Gamma = Graph(A, format='weighted_adjacency_matrix')
sage: HP = hamiltonian_paths(Gamma, signed_adjacency_matrix = A)
sage: L = [sum(x[2]) for x in HP]; max(L)
5
sage: L.index(5)
21
sage: HP[21]
[Graph on 6 vertices,
[0, 5, 2, 1, 3, 4],
[-1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1]]
sage: L.count(5)
1
"""
ST = Gamma.spanning_trees()
if signed_adjacency_matrix == []:
HP = []
for X in ST:
L = X.degree_sequence()
if max(L)<=2:
#print L,ST.index(X), max(L)
HP.append(X)
return HP
if signed_adjacency_matrix != []:
A = signed_adjacency_matrix
HP = []
for X in ST:
L = X.degree_sequence()
if max(L)<=2:
#VX = X.vertices()
EX = X.edges()
if EX[0][1] != EX[-1][1]:
ranking = X.shortest_path(EX[0][0],EX[-1][1])
else:
ranking = X.shortest_path(EX[0][0],EX[-1][0])
signature = [A[ranking[i]][ranking[j]] for i in range(len(ranking)-1) for j in range(i+1,len(ranking))]
HP.append([X,ranking,signature])
return HP
Wessell describes this method in a different way.
- Construct a matrix,
, with rows and columns indexed by the teams in some fixed order. The entry in the i-th row and the j-th column is defined by
- Reorder the rows (and corresponding columns) to in a basic win-loss order: the teams that won the most games go at the
top of, and those that lost the most at the bottom.
- Randomly swap rows and their associated columns, each time checking if the
number of upsets has gone down or not from the previous time. If it has gone down, we keep
the swap that just happened, if not we switch the two rows and columns back and try again.
An implementaiton of this in Sagemath/python code is:
def minimum_upset_random(M,N=10):
"""
EXAMPLES:
sage: M = matrix(QQ,[
[0 , 0 , 1 , 0 , 0 , 0 ],
[1, 0 , 0, 1, 1, 0 ],
[0 , 1 , 0 , 1 , 1 , 0 ],
[1 , 0 , 0, 0 , 0 , 0 ],
[1 , 0 , 0 , 1 , 0 , 0 ],
[1 , 1 , 1 , 1 , 1 , 0 ]
])
sage: minimum_upset_random(M)
(
[0 0 1 1 0 1]
[1 0 0 1 0 1]
[0 1 0 0 0 0]
[0 0 1 0 0 0]
[1 1 1 1 0 1]
[0 0 1 1 0 0], [1, 2, 0, 3, 5, 4]
)
"""
n = len(M.rows())
Sn = SymmetricGroup(n)
M1 = M
wins = sum([sum([M1[j][i] for i in range(j,6)]) for j in range(6)])
g0 = Sn(1)
for k in range(N):
g = Sn.random_element()
P = g.matrix()
M0 = P*M1*P^(-1)
if sum([sum([M0[j][i] for i in range(j,6)]) for j in range(6)])>wins:
M1 = M0
g0 = g*g0
return M1,g0(range(n))
on the set of positive integers:
is even, divide it by two: 
.
.
, and 
. Believe it or not, this is the restriction to the positive integers of the complex-valued map 
.
for the residue of n modulo d. Show that the residue modulo 7 of a (large) integer n can be found by separating the integer into 3-digit blocks 
.(Note that b(s) may have 1, 2, or 3 digits, but every other block must have exactly three digits.) Then the residue modulo 7 of n is the same as the residue modulo 7 of 
. For example,
.
and 
.
.
.
board may be represented graph theoretically as a Hamiltonian cycle on a particular graph with 
vertices, of which 
of them have degree 
, 
have degree 
and the remaining 
vertices have degree 
. The problem of finding an algorithm to find a hamiltonian circuit in a general graph is known to be NP complete. The problem of finding an efficient algorithm to search for such a tour therefore appears to be very hard problem. In [BK], C. Bailey and M. Kidwell proved that complete even king tours do not exist. They left the question of the existence of complete odd tours open but showed that if they did exist then it would have to end at the edge of the board.
and 
,
, 
and 
or 
, 
and the tour is “rapidly filling”.
array of neighboring squares on the board. A foursome is called completed if all four squares have been visited by the the king at some point in a tour, including the case where the king is still on one of the four squares.
denote the change in the number of completed foursomes and let 
denote the change in the number of completed neighbor pairs. Note that 
then 
. If 
then 
. If 
then 
. If 
then 
. 
. If 
. If 
. If 
. 
and 
.
denote the total number of completed neighbor pairs after a given point of a given odd king tour. We may represent the values of 
. Here 
is the total number of completed neighbor pairs after the first move, 
for after the second move, and so on. Each time the king moves, $N$ must increase by an odd number of neighbors – either 
. In particular, the parity of 
, which is obviously even. This is a contradiction. QED
is odd. This follows from a computer computation, an argument from Sands [Sa], and the sequence of lemmas that follow. The proofs are in the original paper, and omitted.
denote the number of completed foursomes in a given odd king tour. Let $M$ denote the number of moves in a given odd king tour. Let 
, where 
are defined as above. Then 
equals 
, 
only occurs when 
.
denote the largest number of non-overlapping ![[m/2][n/2]](https://s0.wp.com/latex.php?latex=%5Bm%2F2%5D%5Bn%2F2%5D&bg=ffffff&fg=323232&s=0&c=20201002)
0’s.
on an 
then all 
boards have nearly complete odd king tours.
Yet Another Mathblog 
You must be logged in to post a comment.