最大カット問題と最小カット問題の違い

質問

グラフ理論において辺に重みが付されているときに、最大カット問題あるいは最小カット問題というのが定義されると思うのですが、これらは学問的に別の意義を持つものなのでしょうか？
重みの正負を逆にすれば同じ問題ではありますが、もし重みを非負としたら、最大カット問題はカットに含む辺の数が必然的にn/2に近づくので、グラフ分割問題と似た様相を呈することになるのかなーと考えています。
もし学問的に問題ごとに明確な定義が与えられているのなら是非知りたいです。
ご意見お待ちしております。

回答No.2

Tacosan · ベストアンサー

その辺は定義しだい. まじめに考えてないけど, 多分負の値を許したとしても極端に「何かが変わる」ってことはないんじゃないかなぁ.

ちなみに n が頂点数だとしたら「最大カット問題はカットに含む辺の数が必然的にn/2に近づく」とはいえないよ. n=2m頂点の完全グラフを考えてみて.

お礼

うーむ確かにあまり変わらないかもしれないですね。
n/2も確かにそうならないです。もうちょっといろいろ調べてみます。
ご回答ありがとうございました。

回答No.1

Tacosan

うん? 定義がわからなかったら「重みの正負を逆にすれば同じ問題ではありますが」などと言えないのでは?

あと「最大カット問題はカットに含む辺の数が必然的にn/2に近づく」も意味がわかりません. n って何?

補足

すみません質問の仕方が悪かったようです。nというのは点の数です。
最大カット問題には「重みが非負である」という条件があるのでしょうか？という質問です。