18 juillet 20193 août 2020 Patrick Meyer Which of the following statements define the Traveling Salesman Problem? To find the shortest cycle in a weighted graph from an initial vertex. To find the shortest route going through all vertices of a weighted graph from an initial vertex. To find a minimum spanning tree on a weighted graph from an initial vertex. Consider a situation in which we are interested in the complexity of algorithms that operate on graphs as a function of the order n of these graphs. Check the following problems that can be reduced to finding a shortest path between two vertices u and v in a weighted graph: Finding a shortest path between two vertices u and v in an unweighted graph. The TSP. Checking if there is a path between two vertices u and v in a weighted graph. When solving the TSP using backtracking, which of the following statements are true? The exploration of the current branch is aborted if the length of the partial route is greater than the best route found so far. In the best case, only the first branch has been fully explored. If branches are explored in decreasing length order, then we explore as many solutions as the simple exhaustive search. Consider a problem for which we have a solution algorithm with complexity O(n²). Select the correct statements: The complexity of the problem cannot be higher than n². There is not an algorithm that can solve the problem with complexity O(n). The complexity of the problem is O(n²). The problem is at least as difficult as the TSP. The complexity of a problem is... the maximum complexity of an algorithm used to solve it. the minimum complexity of an algorithm used to solve it. Time is Up!