View more editions

Introduction to Algorithms 2nd Edition

  • 865 step-by-step solutions
  • Solved by publishers, professors & experts
  • iOS, Android, & web
May 2015 Chegg Study Survey
Chapter: Problem:

Suppose that a complete undirected graph G = (V, E) with at least 3 vertices has a cost function c that satisfies the triangle inequality. Prove that c(u, v) ≥ 0 for all u, vV.

Chapter: Problem:
  • Step 1 of 6

    Triangle Inequality

    According to triangle inequality the sum of the length of two sides of a triangle must be greater than the third side. If this condition is true for any triangle then the triangle follows the inequality.

    C:\Users\evelyn 16\Desktop\CDR TIP\12.tif

    It states that:



  • Step 2 of 6

    Travelling salesman problem: The travelling salesman problem follows the triangular inequality. It is the problem in which a salesman in a city travels to the other cities for selling his products without repeating any city twice except the city from where he has started his tour. There is fixed cost incurred for travelling from one city to the other city.

    It can be represented using a graph G (V, E) in which V is the number of nodes which represents the number of cities the salesman visits. The number of edges E of the graph are representing the r out that is followed by the salesman. The cost for any route from u to v is which is shown on the edges of the graph. The graph showing the travelling salesman problem is as:

    C:\Users\evelyn 16\Desktop\CDR TIP\8.tif

    In the above graph it is shown that the salesman starts his tour from city a he goes to the city b from there he goes forward to c, d, e and f after thathe came back to city a. The cost of each route is shown on the respective edges.

  • Step 3 of 6

    Metric Travelling salesman problem: This is the TSP which follows triangular inequality, and minimum cost is incurred while visiting each vertex single time. According to metric travelling salesman problem the cost elapsed for travelling from one city to other is less than that cost if he follows any indirect route.

    For example: The cost of going from u to v will be lesser than the cost incurred when he goes from u to w and then from w to v. This shows the inequality because the sum of cost incurred in the indirect path is greater than the cost in the direst path. That is the sum of two sides of triangle is greater than one side.

  • Step 4 of 6

    The algorithm to solve the metric TSP is as:


    // A MST is a spanning tree which has minimum weight of all the spanning trees.

    1. Find minimum spanning tree from G.

    // increase every edge of MST to get a eulerian graph.

    2. Increase each of the minimum spanning trees to get an Eulerian graph

    // Eulerian circuit is a path which each vertex only once and start and it is trailing on

    // same vertex.

    3. Find out Eulerian circuit E from.

    4. Output the vertices of as found out in.

    In the above algorithm first step is to find the minimum spanning tree (MST) for the graph. The minimum spanning tree is the graph without any cycle such that it can cover all the vertices of the graph and its weight or cost is lesser than all other spanning trees for the same graph.

    After that is finds the Euler graph for the MST, for finding the Euler graph it extends the edges of MST. Euler graph is the one that contains the Euler cycle and Euler cycle is path which contains each edge of the graph exactly once. Now, the Euler circuit for the graph is calculated which is the path in which each vertex is added only once accept the starting vertex which is also the ending vertex.

    TSP WITH THREE VERTICES: Consider the graph with three vertices u, v, and w. it is the graph with three edges and is a complete undirected graph as shown below:

    C:\Users\evelyn 16\Desktop\CDR TIP\14.tif

    The cost of the edges of the graph is as:

    Cost function c in going from u to v=

    Cost function c in going from u to w=

    Cost function c in going from v to w=

    Hence, the cost incurred in this MST travelling salesman problem will be:

    The reason is this; in any triangle the basis property is that any two side length sum is greater than the third one side. So, here triangle side length is same as cost from one point to other and points are same as vertices as in the triangle.

    Now, if there is any transformation of triangle in any traveling sales man problem structure the triangular inequality can be applied to check which route has less cost charges. If triangle inequality fails it means those point cannot make any triangle structure.

    Thus, it is proved that for all.

  • Step 5 of 6

    TSP WITH FOUR VERTICES: Now, consider the graph for TSP in which there are four vertices. In this graph, there is a path with four vertices u, v, w and x. To traverse the path from vertex u to vertex x there are two routes that is it can be traced either from u to v then x or u to w then u and finally x.

    C:\Users\evelyn 16\Desktop\CDR TIP\9.tif

    As according to the condition the triangle u, v, w follows triangular inequality

    Cost function c in going from u to v=

    Cost function c in going from w to u =

    Cost function c in going from v to w =

    Cost function c in going from to x =

    Therefore, which also fulfills the condition that for all.

  • Step 6 of 6

    TSP WITH n VERTICES: For n vertex TSP consider the graph given below

    D:\Tiffs<br/>ew folder (2)\2254.tif

    From the above graph first consider the path v, u, and w. Starting from v to reach u, the path that can be tracedis either from v to u or v to w and then u. From, triangular inequality:

    Hence, the path from v to u will be chosen, and thus again the cost for all.Similarly, it can be proved for rest of all the paths in the above figure.

    Thus, it is proved that in a complete undirected pathwith at least three vertices will always have a cost function c followed with triangle inequality, which will be for all.

Corresponding Textbook

Introduction to Algorithms 2nd edition 9780070131514 0070131511
Introduction to Algorithms | 2nd Edition
9780070131514ISBN-13: 0070131511ISBN: Ronald L. Rivest, Charles E. Leiserson, Clifford Stein, Thomas H. CormenAuthors: