FindMaximumCut
✖
FindMaximumCut
Details and Options

- FindMaximumCut is also known as the max-cut problem.
- Typically used in cluster analysis, VLSI design and statistical physics.
- A maximum cut of a graph g is a partition of the vertices of g into two disjoint subsets with the largest number of edges between them.
- FindMaximumCut returns a list of the form {cmin,{c1,c2}}, where cmin is the value of a maximum cut found, and {c1,c2} is a partition of the vertices for which it is found.
- For weighted graphs, FindMaximumCut gives a partition {c1,c2} with the largest sum of edge weights possible between the sets ci.
- The following options can be given:
-
EdgeWeight Automatic edge weight for each edge PerformanceGoal "Speed" aspects of performance to try to optimize

Examples
open allclose allBasic Examples (1)Summary of the most common use cases
Scope (5)Survey of the scope of standard use cases
FindMaximumCut works with undirected graphs:
In[1]:=1

✖
https://wolfram.com/xid/0n4kzmwrw28-cf8y58
Out[1]=1

In[1]:=1

✖
https://wolfram.com/xid/0n4kzmwrw28-w5x6ap
Out[1]=1

In[1]:=1

✖
https://wolfram.com/xid/0n4kzmwrw28-ykb9h2
Out[1]=1

In[1]:=1

✖
https://wolfram.com/xid/0n4kzmwrw28-68ynlo
Out[1]=1

In[1]:=1

✖
https://wolfram.com/xid/0n4kzmwrw28-s1cts9
Out[1]=1

Options (1)Common values & functionality for each option
EdgeWeight (1)
By default, the edge weight of an edge is taken to be its EdgeWeight property if available, otherwise 1.
In[1]:=1

✖
https://wolfram.com/xid/0n4kzmwrw28-xjk9gx
Out[1]=1

Use EdgeWeight->weights to set the edge weight:
In[2]:=2

✖
https://wolfram.com/xid/0n4kzmwrw28-ztdl4i
Out[2]=2

Properties & Relations (1)Properties of the function, and connections to other functions
Use FindGraphPartition to find a cut with approximately equal-sized parts:
In[1]:=1

✖
https://wolfram.com/xid/0n4kzmwrw28-obiug0
In[2]:=2

✖
https://wolfram.com/xid/0n4kzmwrw28-vv2j2r
Out[2]=2

In[3]:=3

✖
https://wolfram.com/xid/0n4kzmwrw28-k2y17h
Out[3]=3

Wolfram Research (2020), FindMaximumCut, Wolfram Language function, https://reference.wolfram.com/language/ref/FindMaximumCut.html.
✖
Wolfram Research (2020), FindMaximumCut, Wolfram Language function, https://reference.wolfram.com/language/ref/FindMaximumCut.html.
Text
Wolfram Research (2020), FindMaximumCut, Wolfram Language function, https://reference.wolfram.com/language/ref/FindMaximumCut.html.
✖
Wolfram Research (2020), FindMaximumCut, Wolfram Language function, https://reference.wolfram.com/language/ref/FindMaximumCut.html.
CMS
Wolfram Language. 2020. "FindMaximumCut." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/FindMaximumCut.html.
✖
Wolfram Language. 2020. "FindMaximumCut." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/FindMaximumCut.html.
APA
Wolfram Language. (2020). FindMaximumCut. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindMaximumCut.html
✖
Wolfram Language. (2020). FindMaximumCut. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindMaximumCut.html
BibTeX
✖
@misc{reference.wolfram_2025_findmaximumcut, author="Wolfram Research", title="{FindMaximumCut}", year="2020", howpublished="\url{https://reference.wolfram.com/language/ref/FindMaximumCut.html}", note=[Accessed: 21-June-2025
]}
BibLaTeX
✖
@online{reference.wolfram_2025_findmaximumcut, organization={Wolfram Research}, title={FindMaximumCut}, year={2020}, url={https://reference.wolfram.com/language/ref/FindMaximumCut.html}, note=[Accessed: 21-June-2025
]}