TADM2E 5.27
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
