Using Graph Theory to Count Routes
Date: 07/15/98 at 06:04:56 From: patrice blackman Subject: Use a tree diagram or systematic list. There is a rumor that Daddy Warbucks is planning to start a new airline. He plans to serve 5 cities: Atlanta, Boston, Chicago, Dallas and Erie. There will be direct flights between each pair of cities. Use a diagram or a list to show how many different routes this will create. (Remember that going from Atlanta to Boston is the same route as going from Boston to Atlanta). How many different routes are there?
Date: 07/24/98 at 10:20:07 From: Doctor Erra Subject: Re: use a tree diagram or systemmatic list. Hello Patrice, Your question is in fact a question about a "complete graph." Let us see how it can be shown. For two cities you have one route: A----------B This is called a graph with two vertices A and B and one edge (a route for you). It is "complete" because all vertices are "connected" by a route. When we say that "going from Atlanta to Boston is the same route as "going from Boston to Atlanta" this means that we have an "undirected graph." Going from A to B is the same "cost" (time, distance, money) as going from B to A. With 3 cities, we have a triangle: A-------B \ / \ / \ / C To answer your question, we'll start by considering the conjecture: are there n routes when we have n cities? No! Because for example, with 4 cities you will have 6 routes. Make a picture with 4 cities A, B, C, D as the 4 corners of a square. There will be 4 sides plus 2 diagonals. For 5 cities, make a picture with 5 points on a pentagon and show all routes. You will see that for n cities the number of routes is equal to ...? I leave you the exact computation. Remember, any of the n cities is connected to the (n-1) other cities, but since the graph is undirected, all of the routes are counted twice. This means that we must divide by 2. Hope it helps, - Doctor Erra, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.