Maximal independent set

From Wikipedia, the free encyclopedia

You have new messages (last change).

In graph theory, an independent set (or an internally stable set) is a set of nodes on a graph such that no edge is complete. That is so that all the members of an edge are not part of the set. (In the case of a normal graph, the nodes in the set are not neighbors.)

A maximal independent set (or a maximal internally stable set) is an independent set such that adding any other node to the set makes the set no longer independent.

[edit] See also


This combinatorics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../m/a/x/Maximal_independent_set.html"