Suppose we are given a train map which consists of a set of 20 cities, and certain pairs of those

cities are connected by direct train lines. Note that a train between two cities does not necessarily travel

in both directions. Let S = {1, 2, ... 20} represent the set of cities, where each unique city is identified

with a number. Define a binary relation on S as follows: (a,b) E R if and only if there is a direct train

from city a to city b. A tourist is interested in going from one city to another using at most three trains.

Specifically, she would like to identify the pairs of cities (a, b) for which she can go from city a to city b

(where b is not a) using at most 3 trains.

Express these pairs in terms of the relation R. Justify your reasoning.

Suppose the train connections are stored in a double array T[ ][ ], where entry T[ i ][ j ] = true if there

is a direct train from city i to city j. Write the basic pseudo-code to print out all the pairs of cities

that are connected by exactly two trains.

2 2 (a) Suppose we are given a train map which consists of a set of 20 cities, and certain pairs of those cities are connected by direct train lines. Note that a train between two cities does not necessarily travel in both directions. Let S {1, 2, ...,20} represent the set of cities, where each unique city is identified with a number. Define a binary relation on S as follows: (a,b) E R if and only if there is a direct train from city a to city b. A tourist is interested in going from one city to another using at most three trains. Specifically, she would like to identify the pairs of cities (a,b) for which she can go from city a to city b (where b + a) using at most 3 trains. Express these pairs in terms of the relation R. Justify your reasoning. Suppose the train connections are stored in a double array T[]), where entry T[i][j] = true if there is a direct train from city i to city j. Write the basic pseudo-code to print out all the pairs of cities that are connected by exactly two trains