Problem 5. (25 pts) A tournament is a n-node directed graph such that between any two vertices ui and uj there is either a directed edge from ui to uj or a directed edge from uj to ui, but not both directed edges. In other words, a tournament is formed by taking the (undirected) complete graph over n nodes and assigning each edge a direction arbitrariljy As the name 'tournament' suggests, imagine you have n tennis players and all possible pairs of player have a match between them, and so for player i and player j you have a directed edge (i,j) if i losses to j in the match they had.) (a) (15 pts) Prove (by induction on n) that in any n-node tournament one can order all vertices from first to last V1, U2,..., Vnsuch that in this order we get a directed path of length n - 1 starting at vi and ending at vn. (L.e. for every i we have that there's a directed edge from vi to vi+1.) FYI, such a path is called a Hamiltonian path in a directed graph u1 Figure 4: An example of a 5-node tournament, where: _ one possible path is ul-ul, U2- 14, U3-u5, v4-U3,V5-up; and yet another possible path is u, v2-u2, v3-u5, v4u1, U5u3 (and there are others too) Hint: the induction step, where we add a new node un to a tournament of size n - 1 has two easy cases One easy case is where there's an edge from un to vi, and the other easy case is where there's an edge from vn-1 to un. What happens if neither hold? (b) (10 pts) Convert your proof into a recursive algorithm that takes as an input such a tournament G in the adjacency-matrix model, and returns such a n - 1-edge path. What is the runtime of your algorithm? Does it remind you of any sorting algorithm? Problem 5. (25 pts) A tournament is a n-node directed graph such that between any two vertices ui and uj there is either a directed edge from ui to uj or a directed edge from uj to ui, but not both directed edges. In other words, a tournament is formed by taking the (undirected) complete graph over n nodes and assigning each edge a direction arbitrariljy As the name 'tournament' suggests, imagine you have n tennis players and all possible pairs of player have a match between them, and so for player i and player j you have a directed edge (i,j) if i losses to j in the match they had.) (a) (15 pts) Prove (by induction on n) that in any n-node tournament one can order all vertices from first to last V1, U2,..., Vnsuch that in this order we get a directed path of length n - 1 starting at vi and ending at vn. (L.e. for every i we have that there's a directed edge from vi to vi+1.) FYI, such a path is called a Hamiltonian path in a directed graph u1 Figure 4: An example of a 5-node tournament, where: _ one possible path is ul-ul, U2- 14, U3-u5, v4-U3,V5-up; and yet another possible path is u, v2-u2, v3-u5, v4u1, U5u3 (and there are others too) Hint: the induction step, where we add a new node un to a tournament of size n - 1 has two easy cases One easy case is where there's an edge from un to vi, and the other easy case is where there's an edge from vn-1 to un. What happens if neither hold? (b) (10 pts) Convert your proof into a recursive algorithm that takes as an input such a tournament G in the adjacency-matrix model, and returns such a n - 1-edge path. What is the runtime of your algorithm? Does it remind you of any sorting algorithm