# 7.37

Proof by induction.

A tournament with 2 vertices (1,2) has a Hamiltonian path. 1 -> 2 or vice versa

Now suppose our tournament with n vertices has a Hamiltonian path 1,..,n. Now add a vertex (n+1) that is connected to every other node. 3 cases may occur:

case1) If the first node of the n Hamiltonian path can be reached by vertex (n+1), add (n+1) to the beginning of the path. New Hamiltonian path: n+1,1,...,n

case2) If the last node of the n Hamiltonian path can reach the vertex (n+1), add (n+1) to the end of the path. New Hamiltonian path: 1,...,n,n+1

case3) Take the first node of the n Hamiltonian path that can be reached by (n+1). This must exist, because we are not in case 2. Call this node k. By definition of this node, (k-1) can reach (n+1). Form the new Hamiltonian path as: 1,...,k-1,n+1,k,...,n.

II. Algorithm O(n^2) H = [] # Hamiltonian path Create a queue Q from all the vertices of the tournament, the order of the vertices in the queue does not matter Cycle until the queue is empty: - Extract vertex V0 from the queue - If H is empty, add V0 to H, continue - Find the vertex Vi in H: ∃ V0->Vi, where i is the minimum index # O(n) - If Vi was not found V0->Vi does not exist, then insert V0 at the end of H # O(1). All edges of V0 incoming - Otherwise, if Vi was found V0->Vi exists, then inserting V0 in H before Vi # O(n) III. Algorithm O(n*logn) 1. Initializing the adjacency matrix A # The time complexity of initialization is O (n^2) in any case, since the graph is complete => processing n*(n-1)/2 edges - The matrix is initialized with n arrays of n elements. After adding arrays, assign 0 to all elements on the main diagonal # Graph without loops 2. Data preparation - Mentally change the complete undirected graph with the complete strongly connected directed graph - Eliminating strong connectivity - for each pair (V, W), remove 1 of the edges A[V][W] = 0 or A[W][V] = 0 3. Finding the Hamiltonian path - If A[s_i][s_j] == 1, there is an edge s_i->s_j => s_i dominates s_j => s_i > s_j - As it is possible to establish a relationship between the vertices, it is possible to sort them out # O(n*logn)

```
""" O(n*logn) implementation """
from random import randint
from functools import cmp_to_key
from time import perf_counter
for m in range(100):
cap = 12
size = 2 ** cap
graph = [[1 for i in range(size)] for k in range(size)] # Adjacency matrix representation
for i in range(size): # Building 1 big tournament
for j in range(i, size):
if randint(0, 1) or j == i: # Setting directions and removing loops
graph[i][j] = 0 # Removing i -> j
else:
graph[j][i] = 0 # Removing j -> i
for i in range(size): # Tournament correctness check
for j in range(size):
if i != j:
assert graph[i][j] != graph[j][i]
else:
assert graph[i][j] == 0
for z in range(2, cap + 1): # Finding Hamiltonian paths for subgraphs
subgraph_size = 2 ** z
start_time = perf_counter()
hamiltonian_path = sorted(range(subgraph_size), key=cmp_to_key(lambda a, b: graph[b][a] - graph[a][b]))
# print(hamiltonian_path, end='\n\n') # Output path
print('Time: {:f}s | Size: {:d}'.format(perf_counter() - start_time, subgraph_size))
for i in range(subgraph_size - 1): # Hamiltonian path check
assert graph[hamiltonian_path[i]][hamiltonian_path[i + 1]] # Next vertex in path must be reachable
print('') # New line between cases
```

--Bkarpov96 (talk) 17:34, 8 July 2020 (UTC)

Back to Chapter 7