Let G (V, E) be an undirected graph with n nodes. Recall that a subset of the no

Question

Let G (V, E) be an undirected graph with n nodes. Recall that a subset of the nodes is called an independent set if no two of them are joined by an edge. Finding large independent sets is difficult in general, but here we'll see that it can be done efficiently if the graph is "simple" enough Call a graph G (V, E) a path if its nodes can be written as v1, vn, with an edge between vi and vj if and only if the numbers i and j differ by exactly 1. With each node vi, we associate a positive integer weight wi. Consider, for example, the five-node path drawn in Figure 1. The weights are the numbers drawn inside the nodes. The goal in this question is to solve the following problem: Find an independent set in a path G whose total weight is as large as possible (a) Give an example to show that the following algorithm does not always find an independent set of maximum total weight. The "heaviest first" greedy algorithm Start with S equal to the empty set While some node remains in G Pick a node vi of maximum weight Add v to S Delete vi and its neighbors from G End while Return S (b) Give an example to show that the following algorithm also does not always find an independent set of maximum total weight. Let Si be the set of all vi where i is an odd number Let S2 be the set of all vi where i is an even number (Note that Si and S2 are both independent sets) Determine which of Si or S2 has greater total weight and return this one

Explanation / Answer

1) from the graph given if we select the set s is empty.

according to algorithm we will select the first vertax is having weight 8.

then delete the vertex having weight 6 and 1.so remaing vertex in graph is 6 and 3.

suppose if there is a weight 2 in place of 6 at last then we will not be able to find independent set with maximum weight.ex.

1->8->6->3->2

2)s1=(1,3,5), s2=(2,4,6) maximum weight =12

here the independent set will belongs to set s2 but in examle s1=(3,5,7) s2=(2,4,6) independent set will belongs to set s1.maximum weight =15

3) select an empty set s.

select maximum weight vertax and delete neighbour with minmum weight.

select next maximum weight vertex.

repeat step 1 to 3.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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