• 締切済み

離散数学の「K(G)≦λ(G) を証明せよ」を教えてください。

一応、途中までは、 「G=K'のとき、　K(G)=λ(G)=0 G:非連結のとき　K(G)=λ(G)=0 よって、　G:連結　|V|≧2 　このとき　|V|≧|E|＋1 ｌ=λ(G)とし、F≦E |F|=l G-F:非連結とする 　HをV(H)の１つの連結成分とし A=V(H) B=V(G)-Aとおく F={e1,e2,・・・ei}と書く 各iに対し、ei=eiyi (xi∈A,yi∈B)とおく」 ここからどう続くのかわからないので教えてください。 ちなみに帰納法使うみたいです。 もしかしたら上でも間違ってるとこあるかもしれませんが・・・ よろしくお願いします。

noname#90957
noname#90957

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

えっと.... 「K(G)」とか「λ(G)」って, どんな定義でしたっけ?

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • この数学的帰納法を用いた証明問題がわかりません。

    この数学的帰納法を用いた証明問題がわかりません。 （２）n 回微分可能な関数f(x) のn 次導関数をf^(n)(x) で表しf^(0)(x) = f(x) と定 義するとき，次の公式(Ｐ) が成立する．以下の問(ａ), (ｂ) に答えなさい． (Ｐ)d^n/dx^n ( e^xf(x) ) =Σ(r=0からn)ｔ(n r)e＾xf＾(r)(x) （ n ≧ 1, t(n r)=n!/( r!(n - r)! ) ） (ａ) g(x) = x^2e^x のn 次導関数g^(n)(x) を求めなさい． (ｂ) 数学的帰納法を用いて公式(Ｐ) を証明しなさい．ただし，必要であれ ば次の性質を用いてよい． t(n ,r - 1)+t(n,r)=t(n + 1,r) （r ≧ 1; n ≧ r） -------------------------------------------------------------- 画像が見づらくて申し訳ありません。 (a)はh(x)=x^2と置くと、 g^(n)=d^n/dx^n( e^xh(x) )=Σ(rからn)e^x h^(r) (x) これで合っていますか？ (b)は n=1のときは明らかに成り立つ。 n=k(kは自然数)のとき成り立つと仮定し、n=k+1のときの式変形がどうもうまくいきません。 (n≧3のときh^(n)=0であるのはわかります。) どなたか解説をよろしくお願いします。

  • 常微分方程式の解き方について

    常微分方程式の解き方について質問です。 Fickの第2法則の式を4次のルンゲ・クッタ法で解きたいと考えています。 4次のルンゲ・クッタ法は、 k1=f(xi,yi) k2=f(xi+h/2,yi+h/2*k1) k3=f(xi+h/2,yi+h/2*k2) k4=f(xi+h,yi+h*k3) として、 yi+1=yi+h/6*(k1+2k2+2*k3+k4)で解いています。 そこで、Fickの法則（dC/dt=D*d^2C/dx^2）を、以下の式ように変換しました。 dC/dt=D*（Cj+1+Cj）/dx^2　←これ(dC/dt)をf(xi,yi)としています。 f(xi,yi)のyiはCとして、hはdtとして解いてみました（xiはないものとして解いています） エクセルでは、 　 t0 ， t0+⊿t ， ・・・ x1: Cj,n ， Cj,n+1 ， ・・・ x2: Cj+1,n ，Cj+1,n+1， ・　　 ・ のようなセルを組み、t0+⊿tにCn+1=Cn+h/6*(k1+2k2+2*k3+k4)の式を入れています。 上記の方法で解いてみましたが、うまくいきませんでした。 説明が分かりにくく申し訳ないですが、上記のやり方で間違っているところ、アドバスなど ありましたら回答お願いします。

  • 大学の宿題ですが内容は高校の数学の問題です。期限が5/7なので急いでま

    大学の宿題ですが内容は高校の数学の問題です。期限が5/7なので急いでます。 証明問題なのですがうまく証明できません。 お願いします。 問題１、v,v'を平面ベクトル、AとA'を二次の正方行列とする。次のことを示しなさい。 １、すべてのvに対して、Av=A'v⇔A=A' 2、すべてのAに対して、Av=Av'⇔v=v' 問題2、零ベクトルではないxy平面ベクトルa=(a1,a2),b=(b1,b2)を考える。 このときka+Lb=0となるような(k,L)≠(0,0)が存在するための条件を考慮しなさい ただしk,Lは実数とします. 問題3、１、線分PQをk:(1-k)に内分する点をRとするある一次変数fによるP,Q,Rによる像を P',Q',R'とするときR'もまた線分P'Q'をk:(1-k) に内分することを示しなさい。 2、三角形ABCの一次変換fによる像を三角形A'B'C'とする このとき三角形A'B'C'の重心の現像が三角形ABCの重心であることを示しなさい。 問題4、e1,e2は互いに直交する単位ベクトルです。 １、次の関係式a=3e1-2e2,b=4e1+ke2によって定まるベクトルa,bが直交するようにkを定めなさい ２、一次変換fによるe1,e2のそれぞれの像が互いに直交する単位ベクトルe'1,e'2であるならば 一次変換fによるa,bのそれぞれの像a',b'もまた直交することを示しなさい。

  • ２行のセルの入れ替え。

    　初めまして、よろしくお願いします。 　セルに A B C D E F G H I J K L 1 a b c d e f 2 g h i j k l 3 m n o p q r 4 s t u v w x 5 " ・ " ・ " ・ " 100 " 　という表があります。これを A B C D E F G H I J K L 1 a b c d e f g h i j k l 2 m n o p q r s t u v w x 3 " 4 " 5 " ・ " ・ " ・ " 100 " 　という風に、偶数行のデーターを奇数行の後ろにつけるようにしたいと思います。無理ならば奇数行だけのデーター、偶数行だけのデーターとなるように、何かよい方法を教えて頂きたく、よろしくお願いします。

  • 帰納法の証明で後一歩

    帰納法というんでしょうか、証明する問題を解いていますが後一歩でどうすればよいのか分かりません。 というか自分のやったところも書き方とかあっているかどうか分かりません。 問題の"any graph"というのも引っ掛かります。 Cycleが含まれるグラフだとVよりも大きくなるような気が…。 これがその問題です。 Let G = (V, E) be any graph. Prove the following claim: If there is any walk between vi ∈ V and vj ∈ V, then there must be a path of length no larger than |V|-1 between these two vertices. G = (V, E)はどんなタイプのグラフでもよいとする。次の主張を証明せよ: もしvi ∈ Vとvj ∈ Vの間にいくらかの歩行距離があれば、それらの二つの頂点の間には|V|-1よりも大きくない(つまり|V|-1よりも小さいか等しい)長さの経路が存在するはずである。 ※ちなみに|V|はVの絶対値ではなく、Vの全体の長さです。例えばV={v1, v2, v3}であれば|V|=3です。 自分のやったところまで書きます。 証明: もしvi ∈ Vとvj ∈ Vの間にいくらかの歩行距離があれば、 |(vi, vj)| <= |V|-1 であることを証明したい。 根拠: P(1)は真である、なぜなら |(v1, v2)| <= |{v1, v2}|-1 1 <= 2-1 1 <= 1 帰納的仮定: P(K)が真だと仮定すると |(v1, v2)(v2, v3)(v3, v4), ... ,(v_K-1, v_K)| <= |K|-1 そしてP(K+1)が真であることも証明しないといけないので |(v1, v2)(v2, v3)(v3, v4), ... ,(v_K-1, v_K)(v_K, v_K+1)| <= |K+1|-1 …これからどうすればいいのか分かりません。 |K+1|-1の部分はそのまま1をプラスマイナスして0なので |K|でいいと思うんですが、それが私の出来る精一杯です。 これからどうすればいいのか教えてください。

  • VBA

    1 a;b;c;d; 2 e;f;g;h; 3 i;j;k;l; をVBAで 　　1 a; 　　2 e; 　　3 i; 　　1 b; 　　2 f; 　 　3 j; 　　1 c; 　　2 g; 　　3 k; 　　1 d; 　　2 h; 　　3 l; としたいのですが、どうしたらいいですか？

  • 急いでます。恒等式の証明お願いします。

    ｘ＾１０＝a(x-1)+b(x-1)+c(x-1)+d(x-1)+e(x-1)+f(x-1)+g(x-1)+h(x-1)+i(x-1)+j(x-1)+k は、組立除法でといたら a=1 b=10 c=45 d=120 e=210 f=252 g=210 h=120 i=45 j=10 k=1 となりました。見るからに規則性がありそうなんですけど、どうやって証明できますか？ 回答待ってますm(_ _)m .

  • 新たに挑戦。エジプトの分数問題

    エジプトの分数問題が、解けたような気がするので、再度挑戦します。 　e*P(e,f,g,h)=4*e*f*g*h - h - f (1) 　Q(a,b,c)=4*a*b*c - b - 4c (2) わかりやすくするため、式を変形する。P()＝Q()=24*n+1とする。 4*e*f*g - {(24*n+1)*e+f}/h=L=1 ? (4*b - 1)*a - {(6*n+b)/c｝=K=1 ? 適当に値を代入して、L=1またはK=1に になれば、等式が成り立ち、解が存在するだろう。 なので、L≠1の時に、K=1とすることができることを証明する。 それにより、(1)の式の解がないとき、(2)の式に必ず解が見つけることが できることを表す。 　4*e*f*g - {(24*n+1)*e+f}/h=L e=4*b - 1,f=1　とおくと 　4*(4*b - 1)*g - 1{(24*n+1)*(4*b - 1)+1}/h=L 　4*(4*b -1)*g={(24*n+1)*(4*b - 1)+1}/h+L h=4m　とおく 　4*(4*b - 1)*g={(24*n*b+b - 6*n)/m}+L ここで式を変形してKを代入する。 (4*b - 1)*a - (6*n+b)/c=K (4*b - 1)*a={(6*n+b)/c}+K a=4d　とおくと 　4*(4*b - 1)*d={(6*n+b)/c}+K 4*(4*b - 1)=[{(24*n*b+b - 6*n)/m}+L]/g =[{(6*n+b)/c}+K]/d nがどんなときにもK=1になることから、 　{(24*d*b)/(g*m)} - {(6*d)/(g*m)} - {6/c}=0 (3) 　{(d*b)/(g*m)}+{(d*L)/g} - {b/c}=K (4) (3)より 　{(4*d*b)/(g*m)}={d/(g*m)}+{1/c} {d/(g*m)}*(4*b - 1)={1/c} {d/(g*m)}=[1/{c*(4*b - 1)}] (4)より 　{d*(b+L*m)/(g*m)} - {b/c}=K [(b+L*m)/{c*(4*b - 1)}] - {b/c}=K ここで、Lが１以外の時にK=1となる数 ｂ、ｃが存在する、たとえば、 L*m=(b+c)*(4*b-1)-b とおけば {(b+c)/c}-{b/c}=1=K となり、K=1とすることができる。 少し厳密性がありません。いい加減な証明です。

  • 随伴写像の存在性の証明は?

    随伴写像についての質問です。 [随伴写像とは] A∈L(V)({=f∈Map(V,V);f is linear}),∃1C∈L(V')(V'はF線形空間Vの双対空間);∀(x,y)∈V×V',y(Ax)=(Cy)(x)(∈F) (i.e. [Ax,y]=[x,Cy]) (⇔def) C をAのadjoint(随伴写像)と言い、adjA:=Cと示す。 ここで 「A∈L(V)({=f∈Map(V,V);f is linear})に対して∀(x,y)∈V×V',y(Ax)=(Cy)(x)(∈F) (i.e. [Ax,y]=[x,Cy]) を満たすようなC∈L(V')(V'はF線形空間Vの双対空間)が一意的に存在する」 を示したいのですが どうやって存在性を示せばいいかわかりません。 Cをどのように採ればいいのでしょうか?

  • JavaScriptの配列について

    var old_array = Array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '<', '#', '/', '>', '%', '.', '*', '0', '!', '?', ':', '=', '|'); var new_array = Array('b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '<', '#', '/', '>', '%', '.', '*', '0', '!', '?', ':', '=', '|'); のような配列があり、 abcと入力するとbcd DEFと入力するとEFG 012と入力すると!23 というようなものを作りたいのですがどうすればいいでしょうか。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する