FindIndependentEdgeSet

FindIndependentEdgeSet[g]

finds an independent edge set of the graph g with a maximum number of edges.

FindIndependentEdgeSet[{vw,}]

uses rules vw to specify the graph g.

Details and Options

  • An independent edge set is also known as a matching.
  • An independent edge set is a set of edges that are never incident to the same vertex.
  • FindIndependentEdgeSet returns a list of edges.
  • FindIndependentEdgeSet works with undirected graphs, directed graphs, weighted graphs, and multigraphs.

Examples

open allclose all

Basic Examples  (1)

Find an independent edge set in a graph:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=

Show the edge set:

In[3]:=
Click for copyable input
Out[3]=

Scope  (6)

Applications  (3)

Properties & Relations  (3)

See Also

IndependentEdgeSetQ  FindIndependentVertexSet

Introduced in 2010
(8.0)
| Updated in 2015
(10.3)