finds an independent edge set of the graph g with a maximum number of edges.
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.
Examplesopen allclose all
FindIndependentEdgeSet works with undirected graphs:
Use rules to specify the graph:
FindIndependentEdgeSet works with large graphs:
A company has a number of different jobs. Each employee is suited for some of these jobs, and each person can perform at most one job at a time:
Maximize the number of jobs that can be performed simultaneously:
Given a set of women, each of whom has a preference for some subset of men, find a maximal matching where only matches that agree with preferences are allowed:
An art history department would like to offer six courses. There are eight professors, each of whom is willing to teach certain courses. Find a maximal matching where professors only teach courses they are interested in teaching:
Properties & Relations (3)
Test whether a set of edges is an independent edge set using IndependentEdgeSetQ:
Bipartite graphs have independent edge sets and vertex covers of equal length:
For a graph without isolated vertices, the sum of the size of the independent edge set and the size of the edge cover is equal to the number of vertices:
Wolfram Research (2010), FindIndependentEdgeSet, Wolfram Language function, https://reference.wolfram.com/language/ref/FindIndependentEdgeSet.html (updated 2015).
Wolfram Language. 2010. "FindIndependentEdgeSet." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindIndependentEdgeSet.html.
Wolfram Language. (2010). FindIndependentEdgeSet. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindIndependentEdgeSet.html