Weighted Paths and Trees

Traveling Salesman Problems: 

Traveling Salesman Problems Graphs can help us to represent geographic locations and how to travel between them. Traveling salesman problems work on finding the least expensive or shortest route to take so that each location is visited exactly once before returning home.

Methods : 

Methods Brute Force (Optimal Solution) Represent the problem with a complete, weighted graph. (This kind of graph lists the weights or numbers on the edges.) List all Hamilton circuits possible. Determine the cost or distance associated with each Hamilton circuit. Choose the optimal solution as the Hamilton circuit with the lowest cost (or shortest distance).

Example 1: 

Example 1 Karissa is attending medical conferences in four different cities: Eugene, OR; Orlando, FL; Atlanta, GA; and Memphis, TN. She will start in her home city of Eugene and fly to each city before returning home. She wants to find the cheapest route to take.

Example 1 cont’d: 

Example 1 cont’d Using the Internet, she found the least-expensive one-way airfares offered between each city. Use this information to create a complete, weighted graph and find the optimal route. Orlando Atlanta Memphis Eugene Orlando * $67 $95 $69 Atlanta $67 * $57 $68 Memphis $95 $57 * $99 Eugene $69 $68 $99 *

Methods (continued): 

Methods (continued) Nearest Neighbor (Approximate of the Optimal Solution) Draw a complete, weighted graph to represent the problem. Identify the starting vertex. Choose the edge that has the smallest weight and travel to the next vertex. Again, choose the edge that has the smallest weight and goes to an unused vertex. Travel to that next vertex. Repeat this process until all vertices are visited. Return home.

Example 2: 

Example 2 Vladimir is going to go on a tour of 6 major U.S. cities in an attempt to strengthen his run for President of the Wombats. He plans on starting in Houston, TX, then visiting Los Angeles, CA; Minneapolis, MN; Phoenix, AZ; Sacramento, CA; and Seattle, WA, before returning back to Houston. The airfares between each of the cities are as follows:

Example 2 cont’d: 

Example 2 cont’d Houston Los Angeles Minneapolis Phoenix Sacramento Seattle Houston * $156 $114 $154 $150 $170 Los Angeles $156 * $124 $64 $105 $198 Minneapolis $114 $124 * $144 $125 $134 Phoenix $154 $64 $144 * $94 $149 Sacramento $150 $105 $125 $94 * $131 Seattle $170 $198 $134 $149 $131 * Use the Good-Neighbor Method to find an approximate optimal solution.

Methods (continued): 

Methods (continued) Cheapest-Link Algorithm To start with, consider all edges as acceptable and unselected. From the acceptable edges, select the edge with the smallest weight. (If there are more than 1, just pick.) Continue to select edges of lowest weights without choosing ones that cause 3 selected edges at the same vertex or that close a circuit that is non-Hamiltonian. Once you have a Hamilton circuit, you can add up the weights to see an approximation for the lowest cost.

Trees: 

Trees

Trees: 

Trees A tree is a connected graph in which each edge is a bridge. It has no redundant connections. A spanning tree , a type of subgraph, is a tree created from another graph by removing edges while keeping at least one path to each vertex. (Bridges cannot be removed since that would result in a disconnected graph.)

Practical Uses: 

Practical Uses Data Networks Telephone E-Mail Electromagnetic Telegraph Optical Telegraph Snail Mail Pathways Sidewalk Coverings

Minimum-Cost Spanning Tree: 

Minimum-Cost Spanning Tree A minimum-cost spanning tree is the least expensive spanning tree of all spanning trees under consideration. To construct a minimum-cost spanning tree from a weighted graph, use Kruskal’s Algorithm.

Kruskal’s Algorithm: 

Kruskal’s Algorithm To construct a minimum-cost spanning tree from a weighted graph: Select the lowest-cost edge on the graph. Select the next-lowest cost edge that does not form a circuit with the first edge. Select the next-lowest cost edge that does not form a circuit with any of the previously chosen edges. Repeat until the spanning tree is complete.