此为 Mathematica 7 文档,内容基于更早版本的 Wolfram 语言
查看最新文档(版本11.1)

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.
  • MaximalIndependentVertexSet 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.
Needs["GraphUtilities`"]
This specifies a small graph:
In[2]:=
Click for copyable input
In[3]:=
Click for copyable input
Out[3]=
This shows that the maximal independent vertex set contains three vertices:
In[4]:=
Click for copyable input
Out[4]=
This plots the graph's maximal independent vertex set highlighted in red circles:
In[5]:=
Click for copyable input
Out[5]=
This finds a maximal independent vertex set with preference given to vertices with even labels:
In[6]:=
Click for copyable input
Out[6]=
This plots the new graph's maximal independent vertex set highlighted in red circles:
In[7]:=
Click for copyable input
Out[7]=