GRAPH UTILITIES PACKAGE SYMBOL
MaximalIndependentVertexSet
MaximalIndependentVertexSet[g]
gives a maximal independent vertex set of an undirected graph g.
gives a maximal independent vertex set of g with vertices weighted by w.
- To use
, you first need to load the Graph Utilities Package using Needs["GraphUtilities`"].
gives an (approximate) maximal set of vertices such that 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.
This specifies a small graph:
| Out[3]= |  |
This shows that the maximal independent vertex set contains three vertices:
| Out[4]= |  |
This plots the graph's maximal independent vertex set highlighted in red circles:
| Out[5]= |  |
This finds a maximal independent vertex set with preference given to vertices with even labels:
| Out[6]= |  |
This plots the new graph's maximal independent vertex set highlighted in red circles:
| Out[7]= |  |
