Consider a weighted, undirected connected graph G = (V, E) with vertex set V := {v1,..., Vn} and cost (weight) matrix C = (cij). We will assume that the graph is complete (there is an edge between any two vertices); if it weren't, we coud just add all the missing edges and assign an arbitrarily high cost to each of them. The (symmetric) Traveling Salesman Problem consists of finding a closed path (cycle) of minimum total cost that visits each vertex exactly once. Consider the greedy algorithm for this problem that consists of starting at some vertex v,, taking the lowest-cost edge from any vertex that does not lead to a previously-visited vertex, and then repeating this process at every visited vertex. For the graph represented by the following distance matrix, find the result of this greedy algorithm starting at vertex v, = 1, and show that it in fact produces the highest cost among all possible traveling-salesman paths. 200 201 400 200 200 201 300 201 200 400 201 300 Consider a weighted, undirected connected graph G = (V, E) with vertex set V := {v1,..., Vn} and cost (weight) matrix C = (cij). We will assume that the graph is complete (there is an edge between any two vertices); if it weren't, we coud just add all the missing edges and assign an arbitrarily high cost to each of them. The (symmetric) Traveling Salesman Problem consists of finding a closed path (cycle) of minimum total cost that visits each vertex exactly once. Consider the greedy algorithm for this problem that consists of starting at some vertex v,, taking the lowest-cost edge from any vertex that does not lead to a previously-visited vertex, and then repeating this process at every visited vertex. For the graph represented by the following distance matrix, find the result of this greedy algorithm starting at vertex v, = 1, and show that it in fact produces the highest cost among all possible traveling-salesman paths. 200 201 400 200 200 201 300 201 200 400 201 300