DOCUMENTATION CENTER SEARCH

Graph Utilities Package >

Graph Utilities Package Symbol

Tutorials »|See Also »|More About »

MaximalIndependentVertexSet

MaximalIndependentVertexSet[g]
gives a maximal independent vertex set of an undirected graph g.

MaximalIndependentVertexSet[g, w]
gives a maximal independent vertex set of g with vertices weighted by w.

MORE INFORMATION

To use MaximalIndependentVertexSet, you first need to load the Graph Utilities Package using Needs["GraphUtilities`"].

MaximalIndependentVertexSet gives an (approximate) maximal set of vertices such the no two vertices form an edge. It treats the input as an undirected graph.

The length of the vector w must be the same as the number of vertices in g.

Basic Examples (1)

Needs["GraphUtilities`"]

This specifies a small graph:

This shows that the maximal independent vertex set contains three vertices:

This plots the graph's maximal independent vertex set highlighted in red circles:

This finds a maximal independent vertex set with preference given to vertices with even labels:

This plots the new graph's maximal independent vertex set highlighted in red circles:

Applications (1)

MaximalIndependentEdgeSet

Graph Utilities Package

Graph Utilities Package

© 2008 Wolfram Research, Inc.

Ask a question about this page | Suggest an improvement | Leave a message for the team