Assume the Boolean matrix below is Mr and that Mr represents the relation R wher
ID: 2901609 • 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 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. Compute and interpret the Boolean products: Mr2, and Mr3. (Remember to use Boolean arithmetic). What do these Boolean products give you? That is, explain what the Boolean entries in the matrices Mr2 and Mr3mean Now call the given matrix A and compute A2 and A3 . using regular, not Boolean arithmetic. What do these products give you? ) What does Mr + M2r + M3r + M4r give you? Note, this is Theorem 3 page 602where the text's symbol, v, for Boolean addition is replaced by+, another symbol for Boolean addition .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).