Need help with Exercises 3.2 and 3.3
3.3 | Logistics: Route Planning Suppose we have a business operating in six cities around the Pacific Rim:an Diego, San Francisco, Tokyo, Shanghai, Manila, and Honolulu. We are interested in counting the number of ways we can travel from one city to another with at most n stopovers. We look up all the direct fights and put tham ina table San DiegoSan Francisco San Francisco San Diego, Tokyo, Shanghai, Manila, Honolulu Tokyo San Francisco, Shanghai, Manila Shanghai San Diego, San Francisco, Tokyo, Manila Manila Tokyo, Shanghai, Honolulu Honolulu an Francisco, Shanghai, Manila Let's say we want to get from San Diego to Manila with at most three stops along the way. For example the trip going from San Diego through San Francisco, then Honclulu, then Shanghai, then Manila is a trip with exactly three stops. Exercise 3.2 List all possible ways to get from San Diego to Manila with exactly three stops. Doing that last exercise by hand is a pain because there are so many cases to check, and this is a relatively simple example. If we want to do this efficiently, linear algabra is the perfect tool. We'll start by encoding the data from our table into wha's callad an adjocency matrix. The first step is to number our cities in the order they are listed: San Diego is 1, San Francisco is 2, and so on. We now determine the entries of our adjacency matrix, which we will call A using the following rule: if there is a flight from city i to cityj then the entry A is set to 1. Otherwise, we set that entry to 0. We will also set all of the diagonal entries to 0, since you can't take a fight from a city to itself. This procedure gives us the following matrixA 0 100 0 0 0 1011 0 111 01 0 0 01101 0 1011 0 What's neat about this is that the powers of A have useful information too. For example take the entry A,the entry of A in the third row and siuth column) We compute this as Let's look at the terms here: A:As is 1 if and only if both A and Aare1. This means we get a 1for the kh term if and only if we can fly from Tokyo (city 3) to dity k and from city k to Honolulu (city 6) Thus, (A0a6 counts the number of ways to fiy from Tokyo to Honolulu with exactly one stop. Similar reasoning shows that the number of ways of flying from city i to cityj with exactly n stops is just (A Exercise 3.3 a Enter the above adjacancy matrix: A into MATLAB. By looking at the entry of A in the first row and the fifth column, find the number of ways to gat from San Diago to Manila with exactly three stops. Does your answer here agree with your explicit count in the previous exxercise? If not. find the missing trips. Include your input and output in your document b. Now use MATLAB find the number of ways to get from San Francisco to Tokyo with at most four stops. (This is not the same as finding the number of ways with exoctly four stops!) Indlude all of your commands and output in your write-up. Note 31: As you may have realized the method we've just used counts silly trips like San Francisco- Shanghaian Frandsco Shanghai as a trip with two stops. User baware
