|
For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the Max-Cut Problem. The problem can be stated simply as follows. One wants a subset ''S'' of the vertex set such that the number of edges between ''S'' and the complementary subset is as large as possible. There is a more advanced version of the problem called weighted Max-Cut. In this version each edge has a real number, its weight, and the objective is to maximize not the number of edges but the total weight of the edges between ''S'' and its complement. The weighted Max-Cut problem is often, but not always, restricted to non-negative weights, because negative weights can change the nature of the problem. ==Computational complexity== The following decision problem related to maximum cuts has been studied widely in theoretical computer science: :Given a graph ''G'' and an integer ''k'', determine whether there is a cut of size at least ''k'' in ''G''. This problem is known to be NP-complete. It is easy to see that the problem is in NP: a ''yes'' answer is easy to prove by presenting a large enough cut. The NP-completeness of the problem can be shown, for example, by a transformation from maximum 2-satisfiability (a restriction of the maximum satisfiability problem).〔.〕 The weighted version of the decision problem was one of Karp's 21 NP-complete problems;〔.〕 Karp showed the NP-completeness by a reduction from the partition problem. The canonical optimization variant of the above decision problem is usually known as the ''Maximum-Cut Problem'' or ''Max-Cut'' and is defined as: :Given a graph ''G'', find a maximum cut. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Maximum cut」の詳細全文を読む スポンサード リンク
|