- ベストアンサー
最大カット問題と最小カット問題の違い
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
その辺は定義しだい. まじめに考えてないけど, 多分負の値を許したとしても極端に「何かが変わる」ってことはないんじゃないかなぁ. ちなみに n が頂点数だとしたら「最大カット問題はカットに含む辺の数が必然的にn/2に近づく」とはいえないよ. n=2m頂点の完全グラフを考えてみて.
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
うん? 定義がわからなかったら「重みの正負を逆にすれば同じ問題ではありますが」などと言えないのでは? あと「最大カット問題はカットに含む辺の数が必然的にn/2に近づく」も意味がわかりません. n って何?
補足
すみません質問の仕方が悪かったようです。nというのは点の数です。 最大カット問題には「重みが非負である」という条件があるのでしょうか？という質問です。
関連するQ&A
- ２次関数の最大・最小問題の場合分けについて
定義域と関数の式が与えられていて、どちらかに文字を含んでいるとき（定義域は固定・グラフが動くときや、定義域が動きグラフが固定されるときについて）、場合分けの方法は２種類ありますよね。 端点のみで最大値・最小値を取る場合は、定義域の真ん中の点と軸との大小関係を考えた場合分け。 端点だけでなく、頂点で最小値・最大値を取る場合は、定義域の端点と軸との大小関係を考えた場合分け。 定義域の端点と軸とを比べる場合はなんとなくわかります。 定義域の真ん中の点と軸とを比べればよいことも、グラフを見れば確かにそうだなぁーとは想います。 ですが、イマイチ納得できないのです。 とくに、定義域の真ん中を考えるという発想がなぜ出てくるのか… 回答よろしくお願いします。
- ベストアンサー
- 数学・算数
- 2次関数の最大・最小
2次関数の最大・最小 aが実数として、a<=x<=a+2で定義される関数f(x)=x^2-2x+3がある。この関数の最大値、最小値をそれぞれM(a),m(a)とするとき、関数b=M(a),b=m(a)のグラフをab平面に（別々に）書け。 最大・最小となる候補を利用 y=d(x-p)^2+qのグラフが下に凸の場合、 ・区間α<=x<=βにおける最小値は、x=pが区間内であれば、頂点のｙ座標q そうでなければ、区間の端点でのf(α）,f(β）のうち小さいほう ・区間α<=x<=βにおける最大値は、区間の端点での値f(α）,f(β）のうちの大きいほう である。結局、「最大値や最小値にｂなる可能性のある点は、頂点と両端の点の３つのみ」であるから、 「頂点のy座標（頂点が区間内にあるとき）、および区間の端点のｙ座標からなる３つのグラフを描いておき、最も高いところをたどったものが最大値のグラフ、最も低いものをたどったものが最小値のグラフである。 教えてほしいところ 「最大値や最小値にｂなる可能性のある点は、頂点と両端の点の３つのみ」であるのは理解できます。しかし、 「頂点のy座標（頂点が区間内にあるとき）、および区間の端点のｙ座標からなる３つのグラフを描いておき、最も高いところをたどったものが最大値のグラフ、最も低いものをたどったものが最小値のグラフである。という部分が理解できません。 何故、たどったものがそれぞれ最大値または最小値のグラフだといえるんですか？？ 論理的に教えてください
- ベストアンサー
- 数学・算数
- 三次関数の最大値・最小値
グラフの大体のイメージはつくれるんですがよくわかりません。 具体的な問題ですが y=2x^3+3x^2-12xで xのとる範囲が[-3,+3]であるときの最大値、最小値なのですが 自分なりの答えはx=3のときmax45で、x=1のときmin-7 なのですがグラフを書いて最大値、最小値の 見当をつけて計算でだしたのですが、何かいい方法があったら教えてください。
- ベストアンサー
- 数学・算数
- 三角形においての最大最小
クリックありがとうございます。 三角形ABCにおいて、AB=3、BC=2、CA=4とし、点P,Qをそれぞれ辺AB,AC上にとる。 線分PQが三角形ABCの面積をニ等分するとき、PQの最大値と最小値をもとめよ。 という問題なのですが、 xy=6 という式をだして、 あとはPQについて余弦定理を用いたのですが、 PQ^2=(x-y)^2+15/2 となり、ここからどうやって最小、最大をだせばいいのかわからず困っています。 相加平均・相乗平均を用いてやる。。 というのもかんがえたのですが、 数Iの範囲での問題なので、x=yで最小値 でそのときのx,yの値をだす方法がわかりません・・・ また最大はどのようにだせばいいのか・・ 考え方、式等もまちがっていましたらご指摘ください。
- 締切済み
- 数学・算数
- y=x^4-2x^2+3の最大値最小値を求める問題について
y=x^4-2x^2+3の最大値最小値を求める問題について y=x^4-2x^2+3の最大値最小値を求める問題についてわからないところがあるのでおしえてください。 x^2=tでy=t^2-2t+3=(t-1)^2+2 定義域が(-1≦x≦2)より0≦t≦4 ここで4は二の二乗だから分かったのですが-1がどうして0なのかがよく理解できません・・。 そこを説明していただけませんか？よろしくおねがいします。
- ベストアンサー
- 数学・算数
- 2次関数の定義域の最大・最小について
ｙ＝X²－４ｘ＋１ (0≦Ｘ≦3)の最大値・最小値を求める問題ですが、ｙ＝(X－2)²－3と直して解く方法があるのですが、いちいち直さなくても、ｙ＝－４ｘ＋１の式にXの定義域の最大・最小を代入すれば解けそうなのですが、このやり方でも大丈夫なのでしょうか。
- ベストアンサー
- 数学・算数
- 最小全域木について
現在、最小全域木の問題はグラフ理論や遺伝的アルゴリズムの文献など様々な分野で解説されていますが、この「最小全域木」について気になることがあります。 最小全域木とは辺に対して一つの重みがあるものですが、この重みが多重化すること、つまり一つの辺に対して二つ以上の重みが存在する最小全域木とは存在しないのでしょうか？？ つまりは「二重の重みを持つグラフ」を対象とした研究とは世の中では行われていないのでしょうか？？ 厳密な解を求めるのが不可能など、様々な問題が生じてくるから不可能なのかなと思ったりしたのですが、、、違うのでしょうか？？ もし、この分野に詳しい方がいらっしゃったら返事をお願いしたいです。
- ベストアンサー
- その他（プログラミング・開発）
- 2次関数のグラフの最大値・最小値について
2次関数のグラフの最大値・最小値の問題でxの範囲が限られている時に≦等号を含む場合は分かるのですが たとえば範囲が1＜ｘ＜３のように等号が含まれていない場合範囲の中に頂点があれば、頂点以外に最大値・最小値をとることはないのでしょうか？
- ベストアンサー
- 数学・算数
- 関数の最大値・最小値
関数f(x)の最大値や最小値を求める際、まずf'(x)を求め f'(x)=0となるようなxと定義域の端のx等から増減表を作りますが、 場合によってはf(x)のx→∞のときの極限等を考えなければならない 、と参考書に書いてありました。 そこで何故だろうと自分で考えてみたのですが、おそらく関数の 一番右端や左端、つまりx→∞やx→-∞のとき最大値や最小値を取る可能性があるため、それを考慮する必要があるのではないかと思いました。 しかし、この自分の考えに基づけばx→∞やx→-∞の極限を考えなければならないのに、問題によってはそれを考慮せずに終わる解答がありました。自分の考えが間違っているのか、それとも考慮しなくても解答できるのかどちらかご教授いただきたいと思います。 下の(1)がx→∞やx→-∞の極限を考慮した解答の載っていた問題で、(2)、(3)は考慮しない解答の載っていた問題です。問題はともに最大値・最小値を求めよです。 (1)y=(x-1)/(x^2+1) 最大値:(√2-1)/2 x=1+√2 最小値:(-√2-1)/2 x=1-√2 (2)y=x-√(x^2-1) 最大値:1 x=1 最小値:なし (3)y=√(x^2+1)+√{(x-3)^2+4} 最大値:なし 最小値:3√2 x=1
- ベストアンサー
- 数学・算数
お礼
うーむ確かにあまり変わらないかもしれないですね。 n/2も確かにそうならないです。もうちょっといろいろ調べてみます。 ご回答ありがとうございました。