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 or x and y is 1.
a)write R as an ordered pair
b)Draw a diagraph representing R
c)Find the in-degree and the out-degree of each vertex
d)List all paths of length 4 starting from vertex 3
e)Compute R^ and draw the digraph.
R = {(2,3),(2,9),(3,2),(3,4),(4,3),(4,9),(9,2),(9,4)}
To answer the questions related to the given relation R, let's break down each part individually.
a) Writing R as an ordered pair:
An ordered pair (x, y) is in the relation R if and only if x is relatively prime to y, which means the only positive divisor of x and y is 1. Based on the set A={2, 3, 4, 6, 9}, we can determine the pairs in R as follows:
R = {(2, 3), (2, 4), (2, 6), (2, 9), (3, 2), (3, 4), (3, 6), (3, 9), (4, 2), (4, 3), (4, 6), (4, 9), (6, 2), (6, 3), (6, 4), (6, 9), (9, 2), (9, 3), (9, 4), (9, 6)}
b) Drawing a digraph representing R:
To represent the relation R as a directed graph or digraph, we can label each vertex as the elements of A={2, 3, 4, 6, 9} and draw arrows between the vertices based on the pairs in R. The resulting digraph would look like this:
2 <-- 3
↙ ↖ ↙ ↖
4 ↔ 6 ↔ 9
c) Finding the in-degree and out-degree of each vertex:
In-degree: The in-degree of a vertex refers to the number of arrows pointing into that vertex. For each vertex, we count the number of arrows pointing towards it.
In-degree of 2: 3
In-degree of 3: 2
In-degree of 4: 2
In-degree of 6: 2
In-degree of 9: 2
Out-degree: The out-degree of a vertex refers to the number of arrows pointing out from that vertex. For each vertex, we count the number of arrows pointing away from it.
Out-degree of 2: 4
Out-degree of 3: 4
Out-degree of 4: 4
Out-degree of 6: 4
Out-degree of 9: 4
d) Listing all paths of length 4 starting from vertex 3:
To find all paths of length 4 starting from vertex 3, we can explore all possible paths by traversing the digraph. Starting from vertex 3, we can move to any neighboring vertex until we reach a path length of 4. The paths of length 4 starting from vertex 3 are:
(3, 2, 4, 6, 2)
(3, 2, 4, 6, 3)
(3, 2, 4, 6, 4)
(3, 2, 4, 6, 9)
e) Computing R^ and drawing the digraph:
R^ (R raised to the power of 1) represents the composition of R with itself. In other words, it is the relation obtained by combining pairs of elements from R.
To compute R^, we need to find all possible combinations of pairs from the relation R and check if they satisfy the given condition (x is relatively prime to y). Here are the pairs in R^:
R^ = {(2, 2), (2, 3), (2, 4), (2, 6), (2, 9), (3, 2), (3, 3), (3, 4), (3, 6), (3, 9), (4, 2), (4, 3), (4, 4), (4, 6), (4, 9), (6, 2), (6, 3), (6, 4), (6, 6), (6, 9), (9, 2), (9, 3), (9, 4), (9, 6), (9, 9)}
The digraph representing R^ would have the same vertices (2, 3, 4, 6, 9) as the original digraph but with additional edges based on the pairs in R^.