Question

answer all and asap please

Solve the following recurrence relation in terms of m f(n) 5f(n-1) - 6f(n-2); n> 1 f(1) 1 5) f0)0 6) Explain how the two cycle are found in the graph illustrated below, using Depth First Search (DFS (int v, the graph as a linked-list. int p) using the where p is the parent node of the vertex v. Represent

Answer 1

5. This recurrence relation is homogeneous recurrence relation. So let us write it in homogeneous form as

By putting a_n = f(n)

Then the recurrence relation is

a_n - 5a_n-1 + 6a_n-2 = 0

The characteristic equation of this recurrence relation is

t² - 5t + 6 = 0

The equation will be (t-2)(t-3) = 0

The solution will be t = 2, 3

Hence the solution will be a_n = c₁2ⁿ + c₂3ⁿ

Now for n = 0, a₀ = c₁ + c₂ = 0

and for n=1, a₁ = 2c₁ + 3c₂ = 1

The solution will be

c₁ = -1, c₂ = 1

Hence f(n) = a_a = 3ⁿ - 2ⁿ

6. Now that any vertex u in graph G=(V,E) can be the source of two cycle like vertex 3 in above figure. For a vertex u to be the source of two cycles, the degree of vertex must be at least 4.

Now let us discuss how we can detect whether a vertex u is source of two cycles or not using DFS.

First of all, note that if we perform DFS from vertex u and in DFS tree, if the degree of node u in DFS tree is less than the degree of node u in original graph G, then vertex u must be the part of some cycle in G because of which not all the edges incident on node u could become the part of DFS tree.  

Hence we perform DFS on vertex u, and check if degree of u in DFS is less than degree of u in original graph. If this does not happen then vertex u cannot be part of any cycle and we test on some other vertex. If this condition is satisfied then we check what is the difference between the degree of vertex u in original graph G and in DFS tree T, if the difference is more than 1 then this means vertex u is part of more than one cycle and select vertex u as the source vertex of 2 cycle and if the difference is 1 then u is only part of one cycle and hence try on some other vertex.

Since time complexity of DFS is O(V+E) and we perform DFS on each vertices, so the time complexity will be O(V(V+E)).

Please comment for any clarification.