Assume the Boolean matrix below is MR and that MR represents the relation R wher
ID: 2901605 • Letter: A
Question
Assume the Boolean matrix below is MR and that MR represents the relation R where R
represents the connecting flights that an airline has between 4 cities: a, b, c, and d.
The 1 in row a column b means there is a flight from city a (Manchester) to city b
(Boston). The 1 in row x column x means that there are planes in airport x. In general,
there is a 1 in row x column y if there is a connecting flight between (from) city x and
(to) city y That is, the rows of the matrix represent the cities of the origins of the flights
and the columns represent the destination cities.
Let MR =
abcd
a1 1 0 1
b1 1 1 0
c1 0 1 0
d0 0 1 1
3
(i) Let a stand for the airport in the city of Manchester, let b stand for the airport in
Boston, c stand for the Chicago airport, d for the airport in the city of Denver. Is their a
flight from Denver to Chicago? Explain.
(ii) Compute and interpret the Boolean products: MR
2
, and MR
3
. (Remember to use
Boolean arithmetic). What do these Boolean products give you? That is, explain what the
Boolean entries in the matrices MR
2
and MR
3
mean.
(iii) Now call the given matrix A and compute A2
and A3
, using regular, not Boolean
arithmetic. What do these products give you?
(v) What does MR + M2
R + M3
R + M4
R give you? Note, this is Theorem 3 page
602where the text
Explanation / Answer
a b c d
a 1 1 0 1
b 1 1 1 0
c 1 0 1 0
d 0 0 1 1
(1)
a -- Manchester
b --- Boston
c --- Chicago
d -- Denver
Yes there is flight from Denver (d) to Chicago (c) since in the boolen matrix (d,c) entry is 1.
(ii)
M_R^2 = a b c d
a 1 1 1 1
b 1 1 1 1
c 1 1 1 1
d 1 0 1 1
M_R^3 = a b c d
a 1 1 1 1
b 1 1 1 1
c 1 1 1 1
d 1 1 1 1
entry (x,y) in M_R^2 represent that we can reach form x to y by making break journey with one stop means from x we can go to some z city and from z we can catch the flight for y.
for example in M_r (a,c) entry is zero means there is no direct flight from a to c. but in M_r^2 (a,c) entry is 1 means we can reach from a to c with one stop (through one city). first a to b then from b to c.
entry (x,y) in M_R^3 represent that either we can reach form x to y by making break journey with two stop (through two city).
for example in M_R and M_R^2 (d,b) entry is zero means there is no direct flight d to b and we can not reach from d to b with stop also (through one city) but in M_R^3 (b,d) entry is 1 means there is way to reach b from d throught two city. d to c then c to a then a to b.
(iii)
A^2 = a b c d
a 2 2 2 2
b 3 2 2 1
c 2 1 1 1
d 1 0 2 1
A^3 = a b c d
a 6 4 6 4
b 7 5 5 4
c 4 3 3 3
d 3 1 3 2
entry (x,y) in A^2 represent no of ways to reach y form x with one stops.
entry (x,y) in A^3 represent no of ways to reach y form x with two stops.
(v)
M_R + M_R^2 + M_R^3 + M_R^4 represent the is there is way to reach to a city
either directly or atmost 3 stops (through one or two or three stops).