Re: Difference between an "independent set" and a "maximal independent set"

iwan2no@xxxxxxxxxxx wrote:
Hi,

What's the difference between an "independent set" and a "maximal
independent set"? I've tried looking up quite a few definitions, but
they basically say the same thing:

Independent set: A set of vertices in a graph such that for any pair of
vertices, there is no edge between them.

Maximal independent set: A set of vertices in a graph such that for any
pair of vertices, there is no edge between them AND such that no more
vertices can be added and it still be an independent set.

I don't get the second part of the definition of the Maximal
independent set: "...such that no more vertices can be added and it
still be an independent set." - what does this mean?

Exactly what it says. A single vertex is an independent set,
but usually a single vertex is not a maximal independent set.

Suppose I've for the following graph:
(Vx: Vertex no. x)

V1--------V2--------V3--------V4

Now is it true that the following are independent sets?
1. {V1,V3}
2. {V2,V4}
3. {V1,V4}
4. {V1,V3}

Yes, but {V1} , {V2}, {V3} and {V4} are also independent
sets.

How is it actually possible now to ADD another node and make sure that
one of the 4 sets is NOT indepent anymore?

You do not add a new vertex to the graph. You add a new
vertex to the indendent set.

For example, {V1} is an independent set. But it is
not maximal, because I could add {V3} to it to get
{V1, V3} which is an independent set.

{V1, V3} is a maximal independent set. If I add
{V2} or {V4} to {V1,V3} the result will not be a
independent set.

e.g. if I just add V5:

V1--------V2--------V3--------V4--------V5

I'll just be creating a NEW set of independent sets. But my original
list will not be affected. So that brings me back to my original
question: What's the meaning of the second part of the definition of a
Maximal Independent Set.

To me it seems that an Independent set is ALWAYS a Maximal Independent
Set (MIS). When is an Independent set NOT an MIS as well?

Would really appreciate if someone could help me out with this
definition. Could you please give an example that illustrates the
second part of the definition?

Thanks a lot!
Sam


Here is a more interesting graph

V1
|
|
V2--------V3--------V4------V6
|
|
V5

{V1, V5, V6} is an independent set. There does not exist
an edge between any pair. {V1, V5, V6 } is not maximal
however, because I could add V2 to it, and still have
an independent set.

{V3, V6} is a maximal independent set. The other
vertices are all adjacent to either V3 or V6 so
I cannot add any of them and still have an independent set.

Stephen
.

Relevant Pages