3) (16 pts.) (i) G is an undirected graph on n vertices and m edges. Given two v

Question

3) (16 pts.) (i) G is an undirected graph on n vertices and m edges. Given two vertices u and v, you need to determine whether G contains three cycles of length three, each including the edge (u, v). For example, graph G1 in the figure below contains 4 triangles, but not three triangles that contain a common edge. Describe and analyze an efficient algorithm when (a) G is represented by adjacency lists (give the time bound in terms of n and m) and (b) G is represented by an adjacency matrix (give the time bound in terms of n) (ii) G is an undirected graph on n vertices and m edges represented by adjacency lists. Describe and analyze and O(n m) time algorithm determining whether G contains exactly two cycles of length at least three that are edge-disjoint. Edge disjoint means any edge of G can only appear in at most one cycle. For example, graph G2 in the figure below contains two edge disjoint cycles. 0 4 Graph G1 Graph G2 (iii) A game consists of n levels, numbered from 1 to n. To win the game, one needs to play all n levels. Some levels have conditions on what levels need to be played before. These conditions are given in the form of pairs [p, q indicating level p is required for level q. For example, if the pair [4,2 is present, level 4 needs to be played before level 2. For n- 4 and the pairs [1,3 and [3,2], the levels can be payed in the order 1,3,4,2 Given n and m pairs, describe and analyze an efficient algorithm determining an order in which to play the n levels so that the orderings given by the pairs is satisfied. If no order exists, determine so. If multiple solutions exist, choose an arbitrary one. Express any bounds in terms of n and m.

Explanation / Answer

Note : Refer image for graph

(1) a. A disjoint set is a data structure that keeps track of a set of elements seprated into number of various disjoints.

There are two operations

Find and Union

Union-Find algorithm is used to find that whether the given graph contains a cycle or not.

Algorithm

1. Initially all slots of root array are initialised to -1.

0 1 2

-1 -1 -1

2. Edge 0-1, which has vertices 0 and 1 are

0 1 2

1 -1 -1

subset {0,1}

3. Edge 1-2

0 1 2

1 2 -1

subset{0,1,2}

4. Edge 0-2

0 is in subset 2 and 2 is also in subset 2, which forms a cycle.

b.

Adjacency Matrix is array of size V x V where V represents the number of vertices. Let the

array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.

matrix is

0 1 1

1 0 1

1 1 0

2.

int s(int[] na, int[] ma)

{

int s=0;

for(int i:na)

{

s+=i;

}

for (int i:ma)

{

s+=i;

}

return s;

}

the overall complexity will be O(m+n)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.