Questions   
Sort: 
 #1
avatar+33653 
+5
Jul 9, 2016
 #1
avatar+21 
+10
Jul 9, 2016
Jul 8, 2016
 #3
avatar
0
Jul 8, 2016
 #2
avatar+118659 
+5
Jul 8, 2016
 #2
avatar+23251 
+10

Melody -- I have little confidence that I know what I'm talking about, but I thought it was fun to think of the problem this way (I had to rewrite a little):

 

Let R be a relation on A={2,3,4,6.9) defined by "x is relatively prime to y"; that is the only positive divisor of x and y is 1.

 

a) Write R as a set of ordered pairs:

     {  (2,3), (2,9), (3,2), (3,4), (4,3), (4,9), (9,2), (9,4) }

     Notice that 6 is not a member of any of the ordered pairs.

 

b) Draw a digraph representing R:

    On a piece of paper, draw 5 dots and label them '2', '3', '4', '6', and '9'.

    Then, to represent (2,3), draw an arrow from dot '2' to dot '3' (the tail of the arrow is at '2' and the head points to '3').

    Draw all the other arrows: from 2 to 9, from 3 to 2, from 3 to 4, from 4 to 3, from 4 to 9, from 9 to 2 and from 9 to 4.

    The dot at '6' has no arrows that either point from it or point to it.

 

c)  Find the in-degree and the out-degree of each vertex (dot).

    The in-degree of a vertex is the number of arrows that point to that vertex.

         Since there are two arrows to dot '2', one from '3' and the other from '9', the in-degree of '2' is 2.

         Similarly, the in-degrees of '3', '4', and '9', are each 2; the in-degree of '6' is 0.

 

    The out-degree of a vertex is the number of arrows that start at that vertex and point to another vertex..

         Since there are two arrows from dot '2', one to '3' and the other to '9', the out-degree of '2' is 2.

         Similarly, the out-degrees of '3', '4', and '9', are each 2; the out-degree of '6' is 0.

 

d) List all paths of length 4 starting from vertex 3.

    1)  3 ► 4 ► 9 ► 2 ► 3

    2)  3 ► 4 ► 9 ► 2 ► 9

    3)  3 ► 4 ► 9 ► 4 ► 3

    4)  3 ► 4 ► 3 ► 2 ► 9

    5)  3 ► 4 ► 3 ► 2 ► 3

    6)  3 ► 4 ► 3 ► 4 ► 3

    7)  3 ► 4 ► 3 ► 4 ► 9

    8)  3 ► 2 ► 9 ► 4 ► 3

                  etc,

 

7)  Compute R2:

     From  {  (2,3), (2,9), (3,2), (3,4), (4,3), (4,9), (9,2), (9,4) }:

     (2,3) x (3,2) = (2,2)

     (2,9) x (9,4) = (2,4)

     (3,2) x (2,3) = (3,3)

     (3,2) x (2,9) = (3,9)

     (4,3) x (3,2) = (4,2)

     (4,9) x (9,4) = (4,4)

     (9,2) x (2,3) = (9,3)

     (9,4) x (4,9) = (9,9)

     --->     { (2,2), (2,4), (3,3), (4,2), (4,4), (9,3), (9,9) } 

     [It's interesting that these are either identical values or squares or square roots.]

 

    This digraph would contain the same five dots, but the arrow would be determined by these final ordered pairs.

 

Accept this answer at your own risk!

Jul 8, 2016

1 Online Users

avatar