Answered: Let R be a relation on set {1,2,3,4,5}… | bartleby

Related questions

Question

Let R be a relation on set {1,2,3,4,5} with R = {(1,2), (1,3), (2, 1), (3,2), (4,5),
(5,4)}. Represent R as a directed graph G and answer the following questions:
a. Is there a walk of length 3 from 1 to 4 in G? If so, find one. If not, explain why.
b. Is there a cycle of length 3 starting at 2 in G? If so, find one. If not, explain why.
c. Is there an edge from 3 to 2 in G³? Justify your answer.

Expert Solution

Step by step

Solved in 3 steps with 14 images

SEE SOLUTION Check out a sample Q&A here

Blurred answer

Similar questions

Discrete mathematics. Let G = (V, E) be a simple graph4 with n = |V| vertices, and let A be its adjacency matrix of dimension n × n. We want to count the L-cycles : such a cycle, denoted by C = u0u1 · · · uL with uL = u0 contains L distinct vertices u0, . . . , uL-1 et L edges E(C) = {uiui+1 | 0 ≤ i ≤ L − 1} ⊆ E. Two cycles are distinct if the edge sets are different : C = C' if and only if E(C) = E(C'). We define the matrices D, T, Q, the powers of A by matrix multiplication : D = A · A = A2, T = A · D = A3, Q = A · T = A4. Consider the values on the diagonals. Prove that the number of 3-cycles N3 in the whole graph is N3 = 1/6 ∑ u∈V Tu,u
Given a graph G = (V;E) an almost independent set I V is a generalization of an independent set whereeach vertex u 2 I is connected to at most one other vertex in I but no more. In other words for all u; v 2 Iif (u; v) 2 E then (u; z) =2 E for all z 2 I (equvalently (v; z) =2 E). Note that every independent set is alsoalmost independent. Prove that the problem of nding whether there exists an almost independent set ofsize k for some k, is NP-complete.
Consider this graph with 11 vertices and 20 edges. Our goal is to colour each of the 11 vertices with one of three colours (Apricot, Brown, Cyan) so that no edge joins two vertices of the same colour. For example, if the vertex 6 is coloured Brown, then the four vertices adjacent to this vertex (10, 5, 2, 7) cannot be coloured Brown, since that would create a Brown-Brown edge. If we can assign a colour to each vertex so that no edge joins two vertices of the same colour, then we say that this graph is 3-Colourable. If this task is impossible (i.e., no matter what, we must create at least one edge joining two vertices of the same colour), then we say that this graph is not 3-Colourable. Determine whether this graph is 3-Colourable. Answer either YES or NO.