21:00 (IPUSIRON) 21時なので、お願いします 21:00 (dotdister) お願いします。 21:00 (nesys) よろしくお願いしまーす。 21:00 (Defolos) それではよろしくお願いします 21:00 (Defolos) まず資料をご覧ください 21:01 (Defolos) 今回の目的は木の数え上げ手法を学ぶことです 21:01 (Defolos) その中でもケーリーの定理と行列木定理を主に学びます 21:02 (Defolos) 次に前提知識の確認として、2に挙げたように余因子展開を確認します 21:02 (Defolos) n次行列|A| = a[ij]について 21:03 (Defolos) αを余因子とすると画像のような式が成り立ちます 21:03 (Defolos) 余因子展開は後のところで出てくるのですが 21:03 (Defolos) 皆さんご存知ですか? 21:03 (IPUSIRON) >n次行列|A| = a[ij]について 21:04 (IPUSIRON) ここの部分ちょっとおかしいような気がします。 21:04 (Defolos) え? 21:04 (IPUSIRON) A=a[ij]が行列で、| |が付くと行列式 21:04 (Defolos) あ、そうか。Aを行列式としたもの と書かないとダメなのかな 21:05 (IPUSIRON) 確か、余因子展開を使うと、一般の大きさの行列式が求めることが出来るんだけど 21:05 (IPUSIRON) 下の2×2の行列式の場合は、余因子展開を用いなくても明らかにad-bcがなりたつ 21:06 (Defolos) ほむ 21:07 (IPUSIRON) 日本語の部分がちょっと変なだけで式のほうはあってます 21:07 (Defolos) 了解しました 21:07 (IPUSIRON) はい 21:07 (Defolos) それでは続けますね 21:07 (IPUSIRON) どうぞ 21:08 (Defolos) 3ページに行きます 21:08 (Defolos) グラフの点にラベルをつけたものをラベル付木と言います 21:09 (Defolos) ラベルをつけた木において、ラベルのつけ方の総数がいくつあるのかという問題が出てきます 21:09 (Defolos) これは同形となるものを除いてということです 21:09 (Defolos) この問題を解決する定理がケーリーの定理です 21:09 (Defolos) 4ページをご覧ください 21:09 (nesys) ラベルの付け方の総数って、AのところがBだったりCだったり〜などとした場合全てのことですよね? 21:10 (Defolos) はい 21:10 (nesys) おk 21:10 (Defolos) その中で同形にならないものの総数です 21:10 (nesys) なるほど 21:10 (Defolos) n点の異なるラベル付の木はn^(n-2)個ある 21:10 (Defolos) というのがケーリーの定理です 21:10 (Defolos) これを証明します 21:11 (Defolos) 準備として次の3つを定義します 21:11 (Defolos) あ、この部分2つになってますが、誤字です 21:11 (Defolos) vの次数がk-1である点vを含むラベル付木をAと定義する 21:12 (Defolos) vの次数がkである点vを含むラベル付木をBと定義する 21:12 (Defolos) n個の点からなるラベル付木の、ある点の次数がkであるものの総数をT(n,k)と定義する 21:12 (Defolos) の3つを用意しておきます 21:13 (Defolos) 証明のスタンスとしてはAからBを作る連鎖の総数とBからAを作る連鎖の総数は等しいということ利用します 21:13 (Defolos) 次に5ページですが 21:13 (Defolos) 連鎖としてAからBを作る総数についてです 21:14 (Defolos) まずは図のようなグラフを考えてください 21:14 (Defolos) Aの中の点vにつながってない辺で切ります 21:14 (Defolos) この時点で点vの次数はk-1です 21:15 (Defolos) 点vと任意の点wを結ぶと、vの次数がkになるグラフBが得られます 21:16 (Defolos) で、このような操作のことを連鎖といいます 21:17 (Defolos) Aの選び方はT(n,k-1)通りあります 21:17 (Defolos) 点vに接続していない辺の選び方は木Aの辺の総数 - 点vの次数であり 21:18 (Defolos) (n-1) - (k-1)つまりn-k通りあることになります 21:18 (Defolos) 以上よりAからBを作る連鎖の総数はT(n,k-1)(n-k)だとわかりました 21:18 (Defolos) ここまでは大丈夫でしょうか 21:18 (IPUSIRON) OKです 21:19 (nesys) んーちょっと考え中 21:19 (Defolos) はい 21:19 (Defolos) 今回は雑な資料で申し訳ないです 21:19 (nesys) だいたいおkです。 21:20 (Defolos) それでは続けてもよろしいでしょうか 21:20 (nesys) はい 21:20 (Defolos) dotdisterさんは大丈夫ですか? 21:21 (dotdister) あー、はいとりあえず進んでください。 21:21 (Defolos) 次に6ページですが 21:21 (Defolos) AからBの木を作ったのとは逆の動作を行います 21:21 (Defolos) 図のようなグラフBを考えます 21:22 (Defolos) グラフBは点vを削除するといくつかの部分木が得られます 21:23 (Defolos) vを削除するときにできる部分木をT1,T2のように番号を振っていきます 21:23 (Defolos) 各部分木に含まれる点の総数はniで、n-1 = Σ[i=1;k] niを満たします 21:24 (Defolos) vを削除したときにできる部分木をTiとします 21:25 (Defolos) あ、違った 21:25 (Defolos) vにつながってる辺のひとつを削除したときにできる部分木をTiとします 21:26 (Defolos) Ti以外にもvとつながってる辺をひとつ削除されると独立してしまう部分木があるので 21:26 (Defolos) それをTjとします 21:26 (Defolos) Ti内の任意の点uとTj内の任意の点wを辺で結ぶと、vの次数がk-1のラベル付き木Aができます 21:27 (Defolos) これはvにつながってる辺をひとつ削除してるので 21:27 (Defolos) kから削除した辺の1を引いています 21:27 (Defolos) Bの選び方は点vの次数がkですのでT(n,k)通りあることになります 21:29 (Defolos) また、点wiと、Ti以外の部分木Tjの任意の点を結ぶ方法は 21:30 (Defolos) (点vをのぞく点の総数) - (部分木Tiに属する点の総数)個あることになります 21:31 (Defolos) これはつまり(n-1) - ni通りと言えます 21:31 (Defolos) で、以上からBからAを作る連鎖はT(n,k)Σ[i=1;k](n - 1 - ni)個あることになります 21:32 (Defolos) これをシグマを使わずに表すとこうなります T(n,k){(n - 1 - n1) + (n - 1 - n2) + ... + (n - 1 - nk)} 21:33 (Defolos) 変形してT(n,k){(n - 1)k - (n1 + n2 + ... + nk)}つまりT(n,k)(nk - k - n +1)が得られます 21:34 (Defolos) T(n,k)(nk - k - n +1)を因数分解するとT(n,k)(n - 1)(k - 1)になるので 21:34 (Defolos) 連鎖BからAはT(n,k)(n - 1)(k - 1)です 21:34 (Defolos) 修正:の総数が抜けてました 21:35 (Defolos) それでこの証明方法のスタンスとしてあげた 21:35 (Defolos) AからBを作る方法の数とBからAを作る方法の数は同じはずなので 21:35 (Defolos) (n - k)T(n,k-1) = (n - 1)(k - 1)T(n,k) という式が得られます 21:36 (Defolos) ここまで大丈夫でしょうか 21:36 (IPUSIRON) vを固定したときの連鎖の数が(n-1) - ni通りあって、vを変動させるからΣが付くということかな? 21:36 (Defolos) えと、どの部分でしょうか 21:37 (IPUSIRON) BからAを作る連鎖の数のところです 21:37 (IPUSIRON) >で、以上からBからAを作る連鎖はT(n,k)Σ[i=1;k](n - 1 - ni)個あることになります 21:37 (Defolos) ああ 21:38 (IPUSIRON) Σで総数求めて、さらにラベル付きグラフの取りかたの総数がT(n,k)だから掛けると 21:38 (Defolos) はい 21:38 (Defolos) vは任意に取れるので 21:38 (Defolos) 変動させるとk個あることになります 21:38 (IPUSIRON) はい 21:39 (IPUSIRON) 連鎖=あるグラフからあるグラフへの変換 ということですよね? 21:39 (Defolos) そうなりますね 21:39 (Defolos) 形を変える感じでしょうか 21:40 (IPUSIRON) 変換方法がA→Bでa回あるなら、戻すB→Aがb回なら、a=bということを使ってるんですよね 21:40 (Defolos) そのはずです^^; 21:40 (Defolos) これは教科書に書いてあるそうなんですが 21:40 (IPUSIRON) ちょっと複雑な証明なので、証明方針の確認でした 21:41 (Defolos) A→B=B→Aである証明とかは教科書をご覧くださいTT 21:41 (IPUSIRON) はい 21:41 (IPUSIRON) 操作の方法が変だとA→B=B→Aにならないだろうから 21:41 (Defolos) 続けても大丈夫かな? 21:41 (IPUSIRON) どうぞ 21:42 (dotdister) どーぞ。 21:42 (Defolos) あ、話割り込んでしまって申し訳ありません 21:42 (nesys) あ、どーぞー 21:43 (Defolos) 今までの手順で(n - k)T(n,k-1) = (n - 1)(k - 1)T(n,k)という式が得られました 21:43 (Defolos) 7ページをご覧ください 21:43 (Defolos) 実はここからよく分からなかったのですが 21:43 (Defolos) T(n,n-1) = 1になるようです 21:43 (Defolos) これがどうしてか分かる方いらっしゃいませんか? 21:44 (IPUSIRON) T(n,k)の定義に戻ると 21:45 (IPUSIRON) n個の点からなるラベル付木の、ある点の次数がn-1であるものの総数ということだから… 21:46 (IPUSIRON) 放射状みたくなってませんか? 21:46 (Defolos) 点1つだと変はないからn-1=0ということでしょうか 21:46 (IPUSIRON) 中心に1点あって、他の全部の点がその中心だけと繋がっている状況だから 21:46 (IPUSIRON) ラベルと付け替えても、全部同型 21:46 (IPUSIRON) じゃないや(苦笑 21:46 (Defolos) ^^; 21:47 (Defolos) 放射状になってるとうのは合ってそうですが 21:47 (IPUSIRON) こういうときは小さな値で考えて 21:47 (IPUSIRON) T(3,2)=1になることを見てみると 21:48 (IPUSIRON) ・−・−・のようになると思うんですが 21:48 (Defolos) はい 21:49 (IPUSIRON) これにラベルつけると1個だけじゃないですね… 21:49 (IPUSIRON) ラベルつける以前の個数なら1個ですが 21:49 (Defolos) ラベルを考えないなら1個ですね 21:49 (IPUSIRON) ああ 21:49 (IPUSIRON) ラベル自体は固定して考えているのかな 21:50 (Defolos) と言いますと? 21:50 (IPUSIRON) ラベルをつけて考えるときの計算がT(n)=ΣT(n,k)として計算するから 21:51 (IPUSIRON) 違うかもしれない… 21:51 (Defolos) ケーリーの定理ってかなり難しいですね・・・ 21:52 (Defolos) 他のWEBページを見てもここは定義上としか書かれていなかったので困ってました 21:53 (Defolos) ・−・−・ で、1,2,3とそれぞれの点をラベル付けするとすると 21:54 (Defolos) 2は確かにn-kの次数で1個しかありませんね 21:54 (Defolos) でもラベルを付け替えて1,3,2とすると 21:55 (Defolos) 3もn-1でしかも違う木になってるから 21:55 (IPUSIRON) 別の木になっているので、カウントすることになってしまいますね 21:55 (IPUSIRON) 計3個あると思うんだけどね… 21:55 (Defolos) 全部で3つの木ができてしまいますね 21:56 (Defolos) ここ、どうしましょう^^; 21:57 (IPUSIRON) とりあえずT(n,n-1)=1が成り立つという前提で進みましょうか 21:57 (Defolos) そうですねぇ・・・ 21:57 (Defolos) T(n,n-1)=1が成り立つとします 21:58 (Defolos) そうするとk=n-1の時はT(n,n-2) = (n-1)(n-2)T(n,n-1) = (n-1)(n-2)となります 21:58 (Defolos) で、kがn-1、n-2、n-3の時・・・と言う風に書き出していくと 21:59 (Defolos) 二項定理よりk=k+1のときにはT(n,k) = (n-1)^n-k+1(n-2) / (k-1)(k-2)... = n-2Ck-1(n-1)^n-k-1と書けます 22:00 (Defolos) T(n)はT(n,k)ににおいて、kが1の時からkがn-1の時までの総和なので 22:00 (Defolos) Σ[k=1;n-1] n-2Ck-1(n-1)^n-k-1です 22:01 (Defolos) で、これをちょこちょこっと変えてΣ[k=1;n-1] n-2Ck-11^k-1(n-1)^(n-2)-(k-1)にします 22:02 (Defolos) そすると{(n-1)+1}^n-2が得られますので、つまりn^(n-2)です 22:02 (Defolos) ケーリーの定理で言われてたことと同じになるので、証明されたと言えます 22:03 (Defolos) 実は後半、あまり理解してませんでした。申し訳ありません 22:03 (Defolos) ケーリーの定理は大丈夫でしょうか? 22:04 (nesys) うーん……出直して来ますw 22:04 (IPUSIRON) 事実だけはOKです(笑) 22:04 (Defolos) Σ 22:04 (IPUSIRON) 証明は難しいですね 22:04 (Defolos) 難しいですねぇ 22:04 (dotdister) きっついですねぇ。。。 22:04 (IPUSIRON) n=3のときでケーリーの定理が成り立つか確認してみましょうか 22:04 (Defolos) はい 22:05 (nesys) グラフ理論以前に、数学ができてないと全然ダメですね…… 22:05 (IPUSIRON) 3^(3-2)=3^1=3でさっきの議論のように数は一致しますね 22:05 (Defolos) ですね 22:06 (IPUSIRON) シグマがいっぱいでてくるのであれですが、多分この証明のキモは最初のAとBの定義と連鎖の操作の仕方かと思いますよ>nesysさん 22:06 (nesys) その図の表現では分かりましたが、数字に置き換えて分からなくなりましたねぇ 22:07 (IPUSIRON) AとBと変換操作がわかれば、極端にいえば後は数え上げの世界なので 22:07 (Defolos) 私はT(n,n-1) = 1でこけました T-T 22:08 (IPUSIRON) T(n,k)を定義したときに 22:08 (IPUSIRON) その意味をきちんと確認できていれば、=1になるかならないかはっきり付くと思うので 22:09 (IPUSIRON) そこを最初に確認すればよかったですね 22:09 (Defolos) はい 22:09 (IPUSIRON) 次は7.3かな 22:09 (Defolos) それでは、次に進みましょうか 22:09 (nesys) はい 22:09 (Defolos) これ以降はとりあえずケーリーの定理が成り立つものとして話を進めますね 22:10 (dotdister) お願いしまーす。 22:10 (Defolos) 次に8ページの例題7.3です 22:10 (Defolos) k点のラベル付き木とn-k点のラベル付き木の結び方の総数を計算することにより、次の関係式を示せ 22:10 (Defolos) とあります 22:10 (Defolos) まずは1を解きます 22:10 (Defolos) 次のページをご覧ください 22:11 (Defolos) ここでは2(n-1)T(n)というのは、実はn点からなる木の辺の1辺だけを切って2つのグラフA,Bを作る組み合わせの総数に等しい 22:11 (Defolos) とうのがミソになります 22:12 (Defolos) A,Bの木を作る方法は、まず一辺を切ります 22:12 (Defolos) そうすると木は多重辺とかがないので、AとBの二つの木ができます 22:12 (Defolos) 次にAとBとを結ぶ方法を考えます 22:13 (Defolos) 木Aの中の任意の点と 22:13 (Defolos) 木Bの中の任意の点を選びます 22:13 (Defolos) それで結んでみます 22:14 (Defolos) それで、グラフの絵の下の、Σとかから始まる数式を見てください 22:14 (Defolos) T(n)はn点からなる木の総数です 22:15 (Defolos) (n-1)はどの辺を切るかという自由度を表してます 22:15 (Defolos) nではなくてn-1になってるのは 22:15 (Defolos) 辺の数はn点のグラフの場合、n-1しか存在しないからです 22:16 (Defolos) 2はAとBを交換することによる自由度です 22:16 (IPUSIRON) 要するに、グラフを1回の切断で2つに分割できる総数は、(n-1)×T(n)個あって 22:16 (Defolos) k点のラベル付き木Aと(n-k)点のラベル付き木Bの結び方の総数はさっきの式で洗わせられます 22:16 (IPUSIRON) 後はその2つにAとBと名前をつけるから、2通りということですね 22:17 (Defolos) はい 22:17 (IPUSIRON) どぞ 22:17 (Defolos) あ、さっきの所の説明は2(n-1)T(n)についてです 22:18 (Defolos) で、まぁ、AとBの結び方の総数はさっき言った数式のとおりです 22:19 (Defolos) nこの点の中からk個の点を選んでABを作る組み合わせの数かける 22:19 (Defolos) k点のラベル付木の中から1点を選ぶ方法の数かける 22:19 (Defolos) n-k点のラベル付木の中から1点を選ぶ方法の数の 22:20 (Defolos) kが1〜n-1の総和です 22:21 (Defolos) これはΣ[k=1;n-1] nCkk(n-k)T(k)T(n-k)と等しい、と言うか並び替えたらこうなりますので 22:21 (Defolos) 2(n-1)T(n) = Σ[k=1;n-1] nCkk(n-k)T(k)T(n-k)と言うことになりますね 22:21 (Defolos) これが問い1の回答です 22:22 (Defolos) 問い2はケーリーの定理が証明されたとして話を進めます 22:22 (Defolos) ケーリーの定理よりT(n) = n^(n-2)なので、これを 22:23 (Defolos) Σ[k=1;n-1] nCkk^(k-1) (n-k)^(n-k-1) = 2(n-1)n^(n-2)に代入します 22:23 (Defolos) それでごにゃごにゃ変形させるとΣ[k=1;n-1] nCk k^(n-1) (n-k)^(n-k-1)が得られるので 22:24 (Defolos) 問い2で言ってることが正しいと分かります 22:24 (IPUSIRON) 問2の主張ね 22:25 (Defolos) ここまでは大丈夫でしょうか 22:25 (IPUSIRON) OKです 22:25 (nesys) はい 22:25 (dotdister) はい。 22:26 (Defolos) それでは次の11に行きます 22:26 (Defolos) 系として完全グラフの全域木の総数はn^(n-2)個である とあります 22:26 (Defolos) 系とは定理より簡単に導き出されるもののことです 22:27 (Defolos) 完全グラフknの辺を適宜に削除することで木が得られます 22:27 (Defolos) つまりn点のラベル付き全域木が得られることになります 22:28 (Defolos) これとは逆の操作を考えます 22:28 (Defolos) n点のラベル付き木の各点に、すべての点の次数がn-1になるように適切に辺を追加するとKnが得られます 22:28 (Defolos) で、n点のラベル付木とknとが1対1に対応するため 22:29 (Defolos) Cayleyの定理の対象となるラベル付き木とknが同一だといえます 22:29 (Defolos) そのため、knの全域木はケーリーの定理であるn^(n-2)が成り立ちます 22:30 (Defolos) では次に行きましょうか 22:30 (IPUSIRON) 一意に対応していることが 22:30 (IPUSIRON) まだちょっとわからないのですが 22:30 (Defolos) はい 22:31 (IPUSIRON) K5から図のような木に変換しましたが 22:31 (Defolos) はい 22:31 (IPUSIRON) 辺の除去の仕方によっては別の木になりますよね 22:31 (Defolos) なります 22:31 (Defolos) ただ、ここでは適切に辺を削除することでこうなる と言ってるので 22:32 (Defolos) だめになる切り方は考慮外なのかもしれません 22:32 (IPUSIRON) はい 22:33 (Defolos) ここのところは大丈夫でしょうか 22:33 (nesys) はい 22:33 (Defolos) (発表者自体が大丈夫ではなかったりしますが・・・^^;) 22:34 (dotdister) 完全グラフが全域木になるように辺を削除する仕方って、1通りですよね? 22:34 (Defolos) 着目する点につき1通りですね 22:35 (dotdister) ミス。完全グラフKnならn通りですよね。 22:35 (Defolos) はい 22:36 (dotdister) それなら、一意に対応するっていうのは問題ないんですよね。 22:36 (Defolos) そのはずです・・・ 22:37 (dotdister) ありがとうございます。確認したかっただけです。すみません、理解遅くて。。。 22:37 (Defolos) いえいえ、多分私よりよく理解してると思いますよ^^; 22:37 (Defolos) では次、12.点行列と行列木定理に行きます 22:38 (Defolos) 行列木定理を学ぶことが今回の目的の2本中のうちの1つです 22:38 (Defolos) 行列木定理は与えられたグラフGのラベル付全域木の個数を与える定理です 22:38 (Defolos) これを理解するには、まず点行列を知る必要があります 22:38 (Defolos) 次の13ページです 22:39 (Defolos) グラフGの点行列をDと表します 22:39 (Defolos) D[ij]は、対角成分には点viの次数が入ります 22:40 (Defolos) それ以外の成分には点viと点vjを結ぶ辺の数をマイナスした物が入ります 22:40 (Defolos) ですのでD[ij] = D[ji]になると思います 22:40 (Defolos) 実例は資料を見てもらうことにします 22:41 (Defolos) では次の14ページに行きます 22:41 (Defolos) グラフGの全域木の本数はτ(G)と書きます 22:41 (Defolos) τは(たう)というギリシャ文字です 22:42 (Defolos) で、このτ(G)は点行列Dの任意の余因子で与えられます 22:42 (Defolos) D 22:42 (Defolos) の 22:42 (Defolos) i行j列を削除して得られる行列をD(¬i,¬j)と表します 22:43 (Defolos) つまりτ() 22:43 (Defolos) ミス 22:44 (Defolos) つまり、τ(G)は(-1)^(i+j)|D(¬i,¬j)| です 22:44 (Defolos) これの実例は例題で見ていくことにします 22:44 (IPUSIRON) τじゃなくてγじゃないかな?これ 22:44 (Defolos) では例題に行きましょう 22:44 (Defolos) え 22:44 (IPUSIRON) どちらにも見えてしまうから 22:44 (IPUSIRON) どうだろうね 22:45 (Defolos) どっちもそれっぽいですね 22:45 (IPUSIRON) まあここではτと定義しましょうか 22:45 (Defolos) もしかしたらガンマかもしれないですが、ここではたうとしておきます 22:45 (Defolos) それで、次の15ページです 22:45 (Defolos) 例題7.3です 22:46 (Defolos) 問題は資料をご覧ください 22:46 (Defolos) これを解きますので、16ページをご覧ください 22:46 (Defolos) 隣接行列の復習ですが 22:47 (Defolos) 隣接行列はiとjを結ぶ辺の本数をA[ij]とする行列でした 22:47 (Defolos) ですので、このAを元にグラフを書くと、16ページ1つ目のグラフが得られます 22:47 (Defolos) 単純な三角形ですね 22:48 (Defolos) 点行列Dを求めてみます 22:48 (Defolos) まず対角成分にそれぞれの点の次数を入れます 22:48 (Defolos) 全部次数が2なので、2を対角成分にいれていきます 22:49 (Defolos) あとはそれぞれの点は他の点と1本の線で結ばれていますので、対角成分以外の成分には-1を入れます 22:49 (Defolos) 3行3列で余因子展開します 22:50 (Defolos) 余因子展開の前半部分が(-1)^(3+3)なので+となります 22:51 (Defolos) そうするとDは2*2の行列となり、これを2ページで挙げた方法で解きます 22:52 (Defolos) すると4-1がえられますので、答えは3となります 22:52 (Defolos) 実際にGの全域木は図に挙げたように3つだけです 22:52 (Defolos) ここまでは大丈夫ですか? 22:53 (IPUSIRON) 余因子展開というか、τ(G)が余因子で表されるということじゃないかな? 22:54 (IPUSIRON) 定義では 22:54 (IPUSIRON) 余因子展開というと、一般的に行列式を求めようとしているように聞こえるから 22:55 (Defolos) 確かに、言い方はまずかったかもしれません 22:55 (Defolos) あくまで余因子で与えられるという定義でしたので 22:55 (IPUSIRON) 「グラフGの全域木の本数τ(G)は点行列Dの任意の余因子で与えられる」というところからね 22:55 (IPUSIRON) そそ 22:55 (Defolos) 行列式を求めるのとは違いますね 22:56 (IPUSIRON) 後は問題ないです 22:56 (Defolos) はい 22:56 (Defolos) 次に進んでも大丈夫でしょうか? 22:57 (dotdister) ど、どぞー・・・ 22:57 (nesys) あれ?いまさらですが 22:57 (Defolos) はい 22:57 (nesys) 22:45 (Defolos) 例題7.3です といって 22:57 (nesys) 7.4やっているのは何故? 22:58 (Defolos) あああ 22:58 (Defolos) ミスです。ごめんなさい 22:58 (nesys) あぁ。おkです 22:58 (Defolos) 例題7.4です 22:58 (nesys) 了解。 22:58 (Defolos) に修正 22:58 (Defolos) では17.例題7.5 - 1行きますね 22:58 (nesys) はい 22:59 (Defolos) 問題は資料を見てもらうこととして、回答は19ページをご覧ください 23:00 (Defolos) n点からなる木の、点vの次数がkであるものの個数はCayleyの定理で使いました 23:00 (Defolos) T(n,1) = n-2Ck-1(n-1)^(n-k-1)で表すことができます 23:00 (Defolos) 点vが端点になっているものは、kが1の場合しかありえませんので、 23:01 (Defolos) 求める木の個数はT(n,k) = n-2C0(n-1)^(n-2)です 23:01 (Defolos) 組み合わせの定義ではpC0 = 1なので 23:02 (Defolos) 1*(n-1)^(n-2)つまり 23:02 (Defolos) (n-1)^(n-2)が得られます 23:02 (Defolos) これが端点になっているものの個数です 23:03 (Defolos) では解答その2に行きます 23:03 (Defolos) 確立は その事象の数 / 全ての事象 で表されますので 23:04 (Defolos) n点からなる木の総数を分母に入れ、解答その1で得られた点vの次数k=1である場合の個数を分子に入れます 23:04 (Defolos) P(n) = T(n,1) / n^(n-2) 23:05 (Defolos) つまり(1 - (1/n))^(n-2)です 23:05 (Defolos) これが端点である確立であり、その2が解答できました 23:05 (Defolos) 次の解答その3なのですが 23:06 (Defolos) 自然対数eの定理よりlim[n→∞]P(n) = lim[n→∞](1-(1/n))^(n-2)になるそうです 23:07 (Defolos) それで、さらにこれがim[n→∞](1-(1/n))^n になりますが 23:07 (Defolos) この部分はよくわかりませんでした 23:08 (IPUSIRON) どこだろ・・・ 23:08 (Defolos) lim[n→∞](1-(1/n))^(n-2) = lim[n→∞](1-(1/n))^n となるところなのですが 23:08 (IPUSIRON) 手で書いてみます 23:09 (Defolos) そもそも自然対数に対する知識が不足していたようで、しっかり理解できませんでした 23:09 (Defolos) 申し訳ありません 23:09 (IPUSIRON) 元資料の式の展開の(48)のところですか 23:09 (Defolos) はい 23:10 (IPUSIRON) 直観的にいえば、nは∞まで極限とっているから、n-2もnも同じと考えてよいということかな 23:11 (Defolos) 1- 1/∞ つまり1-0 ですか? 23:11 (IPUSIRON) 厳密にやれば、単に(1-A)^(n-2)={(1-A)^n}×{(1-A)^(-2)}と考える 23:11 (IPUSIRON) いえ 23:12 (IPUSIRON) 今いってるのは1/eとなるところじゃなくて、その前の部分ですよね? 23:12 (Defolos) はい 23:12 (IPUSIRON) lim(1-A)^(n-2)となっていますが 23:12 (IPUSIRON) Aは1/nとしてね 23:13 (Defolos) はい 23:13 (IPUSIRON) n-2乗というのはn乗したものから、2乗したものを割ったものですよね 23:13 (Defolos) はい 23:13 (IPUSIRON) 例えば、2^2というのは、2^4から2^2を割ったもの、即ち2^(4-2)ということ 23:14 (IPUSIRON) 一般の式で書くと、a^(b-c)=(a^b)/(a^c)です 23:14 (Defolos) はい 23:15 (IPUSIRON) lim[n→∞](1-(1/n))^(n-2) = lim[n→∞](1-(1/n))^n × lim[n→∞](1-(1/n))^(-2)になりますよね? 23:15 (IPUSIRON) lim[n→∞](1-(1/n))^(-2)=(1-0)^(-2)=1^(-2)=1 23:15 (Defolos) あ、はい\\ 23:16 (IPUSIRON) だから、lim[n→∞](1-(1/n))^(n-2) = lim[n→∞](1-(1/n))^n×1=lim[n→∞](1-(1/n))^nです 23:16 (Defolos) あ〜。なるほろ! 23:16 (Defolos) どうもありがとうございました 23:16 (IPUSIRON) そして、lim[n→∞](1-(1/n))^n = 1/e となるのは、元資料の参考というところに書いてある通りです 23:16 (IPUSIRON) はい 23:17 (Defolos) 発表者がこれではダメですよねぇ T-T 23:18 (Defolos) それで、参考のところにも書いてあるように、lim[n→∞](1-(1/n))^nは1/eとなりますので 23:18 (Defolos) lim[m→∞]P(n) = 1/e が示されます 23:19 (Defolos) ここまでOKでしょうか 23:20 (IPUSIRON) OKです 23:20 (nesys) おkです 23:21 (dotdister) ダ先どーぞ。 23:21 (dotdister) ミス。 23:21 (Defolos) ^^; 23:21 (Defolos) 次の問い2のほうですが 23:21 (Defolos) これは難しいところが特にないので省略します 23:22 (Defolos) 資料では余因子展開でとくとありますが 23:22 (Defolos) 表記上の誤りですので、その点にご注意ください 23:22 (Defolos) では次の25.行列δに行きたいと思います 23:22 (IPUSIRON) ちなみに 23:22 (Defolos) はい 23:23 (IPUSIRON) 問2の3行3列の行列式の計算で余因子展開で求めてますが、普通にサラスの方法使うのが一般的かな 23:23 (IPUSIRON) テストとか自分で手で計算するときには、 23:23 (IPUSIRON) http://ja.wikipedia.org/wiki/行列式#.E3.82.B5.E3.83.A9.E3.82.B9.E3.81.AE.E6.96.B9.E6.B3.95 23:23 (IPUSIRON) ↑サラスの方法 23:24 (IPUSIRON) 3行3列までの計算はこれでいけます 23:24 (Defolos) サラスの公式も考えたんですが、後の応用とかを考えると余因子展開のほうがいいかなーと思ってこれを載せました 23:24 (IPUSIRON) 4行4列以降からは余因子展開しかありませんが 23:24 (IPUSIRON) なるほど 23:25 (Defolos) では次に行ってよろしいでしょうか 23:25 (IPUSIRON) 2で書いてあった余因子展開での行列式の定理のところですが 23:25 (Defolos) あ、はい 23:25 (IPUSIRON) 式微妙に違うか、条件が足りないかなあ… 23:25 (Defolos) Σ 23:26 (IPUSIRON) (-1)^(i+j)みたいなやつも必要だったような 23:27 (Defolos) あ、何かいりそうです・・・ 23:27 (IPUSIRON) aij=(-1)^(i+j)と定義すればよさげですね 23:27 (IPUSIRON) http://ja.wikipedia.org/wiki/行列式#.E4.BD.99.E5.9B.A0.E5.AD.90.E5.B1.95.E9.96.8B 23:28 (Defolos) ちょっと2の余因子展開については後で修正しておきます 23:28 (IPUSIRON) はい 23:28 (Defolos) 行列δですが 23:28 (Defolos) 隣接行列と点行列の間にはちょっとした関係が存在します 23:29 (Defolos) まず行列δを次のように定義します 23:29 (Defolos) 対角成分のところにはviの次数をいれ、それ以外の成分には0を入れます 23:29 (Defolos) それで、D = δ - Aという関係が存在しています 23:30 (Defolos) 例題7.4のグラフGで確かめてみると、 23:30 (Defolos) δは対角成分に2がはいり、後は0がはいります 23:31 (Defolos) 隣接行列Aは対角成分が0、後は1が入っていますので、 23:31 (Defolos) δ-Aは対角成分に2、それ以外に-1が入った行列が得られます 23:31 (Defolos) これはDと同じなので、関係が確認できます 23:32 (Defolos) 次に閉路行列法についてです 23:32 (Defolos) 閉路行列法は点行列法と同じように、ラベル付木の全域木を数えます 23:33 (Defolos) 違いは点行列法が点行列を使っていたのに対して 23:33 (Defolos) 閉路行列法は閉路行列を使う点にあります 23:33 (Defolos) それでは26.閉路行列をご覧ください 23:34 (Defolos) R[ij]は、そこの数式に書いてあるとおりに記述します 23:34 (Defolos) 注意点は、非対角成分の符号はciとcjの共通な辺上で、2つの閉路の向きが同じであれば正を、逆であれば負を選ぶ というところです 23:35 (Defolos) それで、閉路行列法ではこの閉路行列を使って全域木を数えます 23:35 (Defolos) 定理はγ(G) = |R|で表されます 23:36 (Defolos) ここでは例を見てみることにします 23:36 (Defolos) 実例の下の行列をご覧ください 23:36 (Defolos) この行列Aについて考えます 23:37 (Defolos) 実はこれは、先ほど省略した例題7.5の問2の隣接行列です 23:37 (Defolos) これを元にグラフを書くと、2つの閉路c1,c2が存在するグラフがかけます 23:38 (Defolos) 行列の画像のしたのグラフ画像ですね 23:38 (Defolos) 点の順序で向きを指定するとc1=12431、c2=343です 23:38 (Defolos) c1をxとして、c2をyとします 23:39 (Defolos) ここから閉路行列を求めると 23:39 (Defolos) 11成分にはxの点の数である4が、22成分にはyの点の数である2が入ります 23:40 (Defolos) 他の成分にはxとyで共有している辺の数である1を入れます 23:40 (Defolos) これを2ページのやり方で解くと、8-1つまり7となり、点行列法による結果と一致します 23:41 (Defolos) それで、閉路行列法と点行列法とどっちでも結果は同じものが得られるのですが 23:41 (Defolos) どちらを使えばいいのかが問題になります 23:42 (Defolos) 一般的にグラフGに含まれる点の数が閉路の数より少ないときに点行列式法を使うといいらしいです 23:42 (Defolos) その逆は閉路行列法を使うと良いらしいです 23:42 (Defolos) ここまでは大丈夫でしょうか 23:42 (IPUSIRON) はい 23:43 (nesys) はい 23:43 (dotdister) はいー 23:43 (Defolos) それでは例題7.6に移ります 23:43 (Defolos) 行列木定理を用いてCayleyの定理を証明せよ という問題です 23:44 (Defolos) 実は前半がわけわかめだったので 23:44 (Defolos) 前半で作られた定理だけを資料に書いてます 23:45 (IPUSIRON) 「m*mの対称行列の行列式を求める公式を次のように定義する」というより 23:45 (IPUSIRON) 「m*mの対称行列の行列式をbmと定義すると、次のような関係式が成り立つ」という表現の方が正しいと思います 23:45 (Defolos) あ、確かに・・・ 23:46 (IPUSIRON) この関係式が成り立つのは天下りとして利用したとして考えるわけですね 23:46 (Defolos) はい 23:46 (IPUSIRON) そういうことで進めてみましょう 23:46 (Defolos) 定理の作り方を理解していないとダメなのでしょうが、理解できなくて申し訳ないです 23:47 (IPUSIRON) いえいえ、それでこれをどう利用するのかな 23:47 (Defolos) bm = (a+1)^(m-1)b1 + (m-1)(a+1)^(m-1)c1 がm*mの対称行列の行列式を求める公式となりますので 23:48 (Defolos) 完全グラフの点行列はn*nの行列であり、対角成分がn-1 23:48 (IPUSIRON) cも定義してるんですね 23:48 (Defolos) それ以外の成分は-1となる行列ですので 23:50 (Defolos) mはn-1であり 23:50 (Defolos) aは次数が入るはずなので、Knならn-1がはいります 23:51 (Defolos) b1はbが1*1の行列であった場合なので、aが入ります 23:52 (Defolos) c1は資料に定義されているのですが、これが1*1の行列であった場合には-1ですので、c1には-1が入ります 23:53 (Defolos) これを先ほどの公式に代入すると、bn-1 = n^(n-2) (n-1) -n(n-2)^(n-2)が得られます 23:53 (Defolos) これを変形させると、bn-1 = n^(n-2)という式になります 23:54 (Defolos) ここで求めたのは完全グラフにおける全域木の個数でしたが 23:55 (Defolos) 完全グラフの全域木の個数と、ケーリーの定理が対象とするラベル付木の個数は一対一に対応するので 23:55 (Defolos) 完全グラフの全域木を点行列法でn^(b-2)と求めたのでケーリーの定理が証明されました 23:56 (Defolos) これは大丈夫でしょうか 23:56 (IPUSIRON) はい 23:56 (nesys) はい 23:56 (dotdister) はい 23:56 (IPUSIRON) さっきの証明では連鎖とかでやっていたのに、行列木定理を使うとすっきりしますね 23:56 (Defolos) ですね 23:56 (Defolos) 問題は公式を作るところが・・・ 23:57 (IPUSIRON) 公式ってbm,cm-1の公式ですか? 23:57 (Defolos) はい 23:57 (Defolos) わけわかめだったので、もっと知識をつけないとダメだナーと思いました 23:58 (IPUSIRON) m×m行列は(m-1)×(m-1)行列の組合わせで表現できますよね 23:58 (IPUSIRON) それと行列式内の演算が分かれば、この公式は出ます 23:59 (Defolos) ほむ 23:59 (IPUSIRON) 行列式の場合は、ある行からある行の引いたりしていいから 23:59 (IPUSIRON) ここだと-1とか一杯同じのでてるから、引いたらうまく0がでてきて 00:00 (IPUSIRON) m×mより小さい行列式の足し算で表現できるということです 00:00 (Defolos) あー 00:00 (IPUSIRON) 流れはね 00:00 (Defolos) なんとなく流れは分かった気がします^^; 00:00 (IPUSIRON) 元資料(68)では1列目から2列目を引いてます 00:00 (Defolos) で、最後の演習問題なのですが 00:01 (Defolos) ごめんなさい、やる時間がなかったですTT 00:01 (IPUSIRON) ここはいいと思います 00:01 (IPUSIRON) お疲れ様でした。ちょうど3時間かかりましたね 00:01 (nesys) ふぅ 00:01 (Defolos) おつかれさまでしたー 00:01 (nesys) お疲れ様でしたー 00:01 (dotdister) お疲れ様ですー。