TADM2E 5.27 - Revision history

Bkarpov96: Undo revision 882 | Why are u doing this? What's the point? It's wiki for learning book

2020-07-23T08:13:36Z

Undo revision 882 | Why are u doing this? What's the point? It's wiki for learning book

Fucs: Undo revision 871 by Bkarpov96 (talk)

2020-07-22T22:53:13Z

Undo revision 871 by Bkarpov96 (talk)

Bkarpov96: Undo revision 780 by FuckYou (talk)

2020-07-22T11:22:03Z

Undo revision 780 by FuckYou (talk)

FuckYou: Replaced content with "Stupid man.."

2020-07-14T01:47:13Z

Replaced content with "Stupid man.."

Bkarpov96: 5.27 algorithms

2020-07-08T17:34:23Z

5.27 algorithms

GreatSalmon at 15:14, 29 March 2016

2016-03-29T15:14:08Z

GreatSalmon at 15:13, 29 March 2016

2016-03-29T15:13:46Z

GreatSalmon: Created page with "Proof by induction. A tournament with 2 vertices (1,2) has a Hamiltonian path. 1 -> 2 or vice versa Suppose our tournament with n vertices has a Hamiltonian path 1,..,n. Now..."

2016-03-29T15:13:07Z

Created page with "Proof by induction. A tournament with 2 vertices (1,2) has a Hamiltonian path. 1 -> 2 or vice versa Suppose our tournament with n vertices has a Hamiltonian path 1,..,n. Now..."

New page

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

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.

← Older revision		Revision as of 08:13, 23 July 2020
Line 1:		Line 1:
−	~~Stupid man~~..	+	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.
		+
		+	----
		+	<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)

← Older revision		Revision as of 22:53, 22 July 2020
Line 1:		Line 1:
−	~~Proof by induction~~.	+	Stupid man..
−
−	~~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.
−
−	~~----~~
−	~~<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)~~

← Older revision		Revision as of 11:22, 22 July 2020
Line 1:		Line 1:
−	~~Stupid man~~..	+	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.
		+
		+	----
		+	<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)

← Older revision		Revision as of 01:47, 14 July 2020
Line 1:		Line 1:
−	~~Proof by induction~~.	+	Stupid man..
−
−	~~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.
−
−	~~----~~
−	~~<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)~~

← Older revision		Revision as of 17:34, 8 July 2020
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)

@@ Line 6: / Line 6: @@
 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.

@@ Line 1: / Line 1: @@
 Proof by induction.
 A tournament with 2 vertices (1,2) has a Hamiltonian path. 1 -> 2 or vice versa
-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:
+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.