# Difference between revisions of "TADM2E 5.27"

GreatSalmon (Talk | contribs) |
(5.27 algorithms) |
||

Line 10: | Line 10: | ||

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. | 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. | ||

+ | |||

+ | ---- | ||

+ | <pre> | ||

+ | 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) | ||

+ | </pre> | ||

+ | <source lang="python"> | ||

+ | """ 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 | ||

+ | </source>--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 17:34, 8 July 2020 (UTC) |

## Revision as of 17:34, 8 July 2020

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