Question

Design a Maximum-Weight independent Set Tree with at least 13 nodes.  You may connect and label the nodes however you deem fit.  Once you have the tree draw, determine the largest independent set.

Answer 1

Maximum-Weight Independent Set :- It is a set in which any vertex present in the set ,If you take any pair of vertex its should not be directly connect with the common edge or in a simple way it should not be neughbour of vertex and not directly connected.

For Example:- Given in the Image

In Image Its just an Example we find the maximum independent set .

Process:- Select any Random vertex from graph i.e. given in the C set in which all the vertex are given there and the eliminating all the neighbour or directly connected vertex through which you have randomly selected and those are not eliminate take that vertex and find all the neighbour or directly connected vertex like wise you have to solve every vertex so that you get maximum weight Independent set. In the image {A,C,E,G,I,L} i.e. 6 vertex in which its is the largest set present in the graph.