Independent Sets
A graph is called planar if it can be drawn in the plane without
edge crossings. In a drawing of a graph, nodes are identified with points
in the plane and edges with lines connecting the corresponding end nodes.
The edges are not allowed to cross nodes in the drawing.
LEDA Function for Independent Sets
INDEPENDENT_SET() determines for a G=(V,E)an
independent set of nodes I in G. An indepent
set of nodes is a set of nodes such that no two nodes in the set are
adjacent. If G is planar and has no parallel edges, then
I contains at least |V|/6 nodes.
Example of How To Use INDEPENDENT_SET()
The following program shows how the function INDEPENDENT_SET()
can be used.
Remark: The graph algorithms in LEDA are generic, that is, they
accept graphs as well as parameterized
graphs.
We first create a random planar graph G with 10 nodes and
30 edges and compute INDEPENDENT_SET() for G
and a list<node>
independent_set.
#include <LEDA/graph/graph.h>
#include <LEDA/core/list.h>
#include <LEDA/graph/plane_graph_alg.h>
using namespace leda;
int main()
{
graph G;
random_planar_graph(G,10,30);
list<node> independent_set;
INDEPENDENT_SET(G,independent_set);
std::cout << "independent_set.size()="
<< independent_set.size() << std::endl;
node v; forall(v,independent_set) G.print_node(v);
std::cout << std::endl;
return 0;
}
|