University:
University of Michigan
Course:
ECON 613 | Advanced Topic in Mathematics for Economists
Academic year:

2022
Views:

455

Pages:

7
Author:

NebulaNavigator

PATHS Let R be a relatim on a set A. A path of length n from a to b in R is a finite sequence II: 9,x1, x2, X, b beginning with a and ending with b such that a Rai, x, Ron, Note (1): A path of length n involves nti elements of A. Note (2) The elements in a path need not be different. Note (3) Length of a path = No. of edges in the path OR No. of Vertives in it - I Escample Conssder the disraph of a relation R 1 5 2 4 03 TT: 1,2,5,4,3 is a path of length 4 from 1 to 3. Ta: 1,2,2,5,1 is a path of length 4 from 1 to 1 13: 1,2,3 is a path of length 2 from 1 to 3 TH4: 2,2 is a path of length I fom 2 to 2. Is 2,2,2 is a path of length 3 fom 2 to 2. TL: 2,2,2,2 is a path of length 4 foom 2 to 2. Ty: 2,5 is a path of length I fom 2 to 5 Cycle A path beginning and ending at the Same verter is called a cycle. In the above example, Ta is a cycle. Also Hy, its and to are cycles. Also 5,1,2,5 is a cycle. Defn! Let n be a fired tre integer. We define R" on A as follows: (x, y) ER" if and only if there is a path of length n from or to y in R. ive, If there is then (2) ER path of length 2 from a toy, If there is a path of length 3 from a toy 3 then (21, y) ER Consider the above disroph 1,2,5.4 is an path of length 3 form 1 to 4 (14) ER³ 3 1,2,5 is path of length 2 from 1 to 5 (15)ER2 2,5,1,2,3 15 • path of length 4 for 2 to 3 (2,3) ER4 5,1, 2,5 is a path of length 3 fom 5 to 5 (5.5)ER3 Nolk (LY) ER" is also written as Ry Degn Roo is defined as follows: 8 (x, y) ER if and only if there is some path from se to y in R. egt consider the above disreph. There is a path from I to 2 (1,2) ER There is a path from 1 to 3 (1,3) ER These is Q patt form 5 t63 (5,3) R There is a Path from 4403 (4,3) ER There is path fom 2 to 2 (22) ER There is a path from I tol (1-1) ER Noli There is no path from 3 to 2 (3.2) R There is no path from 4 to 1 (4,1) R Nole! (2YJER is also written as "Ry Note: Ro is called the connectivity relation for R 1 Let A = {a, b, c, d, e] and R = {(aa) (ab), (b,c), (ce), (Cd), (de)} Compute R² and Roo R= {(a,a), (ab)_(bc), (Ce), (cd) (de)} & a e a, a a is a peth of length 2 for a to a a9b is a peth of length 2 frim a to b GWER abc is e pett of length 2 tom a to (1) ER R² = {(a,a), (a,b), (a_c)_(b_d),(be), (c,e)} R = {(a,a), (a,b), (c), (6.d) (ae), (bc) (bd) (be) (c,d) (ce), (de)} 2 Let R be the relation on A={1,2,3,4,5,6} Such that R= {1(1,2), (1.6),(2,3), (33),(3,4),(4.1), (4,3), (4,5), (6,4)} (1) Find R and draw the digraph of R². (1) Find Mra (i) Find MR (iv) Find a cycle starting at 2 (V) Find a cycle starting at 6 R={(1,2),4,6),(2,3), (33), (3,4), (4,1), (4,3), (4,5),(6,4)} Digraph of R is (1) 6 3 (i) R={(1,3), (1,4),(2,3), (2,4), (3, 1), (3,3), (34), (25), (4, 2) (4,3), (4,4), (4,6), (6,1), (6,3),(6,5)} Now we draw the digraph of R². (do it yourself)