Difference between revisions of "TADM2E 5.27"

Revision as of 11:22, 22 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