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) 次に前提知識の確認として、２に挙げたように余因子展開を確認します
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) あ、そうか。Ａを行列式としたもの　と書かないとダメなのかな
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) ３ページに行きます
21:08 (Defolos) グラフの点にラベルをつけたものをラベル付木と言います
21:09 (Defolos) ラベルをつけた木において、ラベルのつけ方の総数がいくつあるのかという問題が出てきます
21:09 (Defolos) これは同形となるものを除いてということです
21:09 (Defolos) この問題を解決する定理がケーリーの定理です
21:09 (Defolos) ４ページをご覧ください
21:09 (nesys) ラベルの付け方の総数って、AのところがBだったりCだったり〜などとした場合全てのことですよね？
21:10 (Defolos) はい
21:10 (nesys) おｋ
21:10 (Defolos) その中で同形にならないものの総数です
21:10 (nesys) なるほど
21:10 (Defolos) n点の異なるラベル付の木はn^(n-2)個ある
21:10 (Defolos) というのがケーリーの定理です
21:10 (Defolos) これを証明します
21:11 (Defolos) 準備として次の３つを定義します
21:11 (Defolos) あ、この部分２つになってますが、誤字です
21:11 (Defolos) vの次数がk-1である点vを含むラベル付木をAと定義する
21:12 (Defolos) vの次数がkである点vを含むラベル付木をＢと定義する
21:12 (Defolos) n個の点からなるラベル付木の、ある点の次数がkであるものの総数をT(n,k)と定義する
21:12 (Defolos) の３つを用意しておきます
21:13 (Defolos) 証明のスタンスとしてはAからBを作る連鎖の総数とBからAを作る連鎖の総数は等しいということ利用します
21:13 (Defolos) 次に５ページですが
21:13 (Defolos) 連鎖としてAからBを作る総数についてです
21:14 (Defolos) まずは図のようなグラフを考えてください
21:14 (Defolos) Ａの中の点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) 以上よりＡからＢを作る連鎖の総数は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) だいたいおｋです。
21:20 (Defolos) それでは続けてもよろしいでしょうか
21:20 (nesys) はい
21:20 (Defolos) dotdisterさんは大丈夫ですか？
21:21 (dotdister) あー、はいとりあえず進んでください。
21:21 (Defolos) 次に６ページですが
21:21 (Defolos) ＡからＢの木を作ったのとは逆の動作を行います
21:21 (Defolos) 図のようなグラフＢを考えます
21:22 (Defolos) グラフＢは点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) で、以上からＢからＡを作る連鎖は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) 連鎖ＢからＡはT(n,k)(n - 1)(k - 1)です
21:34 (Defolos) 修正：の総数が抜けてました
21:35 (Defolos) それでこの証明方法のスタンスとしてあげた
21:35 (Defolos) ＡからＢを作る方法の数とＢからＡを作る方法の数は同じはずなので
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) >で、以上からＢからＡを作る連鎖はT(n,k)Σ[i=1;k](n - 1 - ni)個あることになります
21:37 (Defolos) ああ
21:38 (IPUSIRON) Σで総数求めて、さらにラベル付きグラフの取りかたの総数がT(n,k)だから掛けると
21:38 (Defolos) はい
21:38 (Defolos) ｖは任意に取れるので
21:38 (Defolos) 変動させるとｋ個あることになります
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) Ａ→Ｂ＝Ｂ→Ａである証明とかは教科書をご覧くださいＴＴ
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) ７ページをご覧ください
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) 点１つだと変はないから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) ラベルを考えないなら１個ですね
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) 他のＷＥＢページを見てもここは定義上としか書かれていなかったので困ってました
21:53 (Defolos) ・−・−・　で、1,2,3とそれぞれの点をラベル付けするとすると
21:54 (Defolos) 2は確かにn-kの次数で１個しかありませんね
21:54 (Defolos) でもラベルを付け替えて1,3,2とすると
21:55 (Defolos) ３もn-1でしかも違う木になってるから
21:55 (IPUSIRON) 別の木になっているので、カウントすることになってしまいますね
21:55 (IPUSIRON) 計3個あると思うんだけどね…
21:55 (Defolos) 全部で３つの木ができてしまいますね
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) うーん……出直して来ますｗ
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) その意味をきちんと確認できていれば、＝１になるかならないかはっきり付くと思うので
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) 次に８ページの例題７．３です
22:10 (Defolos) k点のラベル付き木とn-k点のラベル付き木の結び方の総数を計算することにより、次の関係式を示せ
22:10 (Defolos) とあります
22:10 (Defolos) まずは１を解きます
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) そうすると木は多重辺とかがないので、ＡとＢの二つの木ができます
22:12 (Defolos) 次にAとBとを結ぶ方法を考えます
22:13 (Defolos) 木Ａの中の任意の点と
22:13 (Defolos) 木Ｂの中の任意の点を選びます
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) で、まぁ、ＡとＢの結び方の総数はさっき言った数式のとおりです
22:19 (Defolos) nこの点の中からk個の点を選んでＡＢを作る組み合わせの数かける
22:19 (Defolos) k点のラベル付木の中から1点を選ぶ方法の数かける
22:19 (Defolos) n-k点のラベル付木の中から1点を選ぶ方法の数の
22:20 (Defolos) kが１〜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) これが問い１の回答です
22:22 (Defolos) 問い２はケーリーの定理が証明されたとして話を進めます
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) 問い２で言ってることが正しいと分かります
22:24 (IPUSIRON) 問2の主張ね
22:25 (Defolos) ここまでは大丈夫でしょうか
22:25 (IPUSIRON) OKです
22:25 (nesys) はい
22:25 (dotdister) はい。
22:26 (Defolos) それでは次の１１に行きます
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とが１対１に対応するため
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) 完全グラフが全域木になるように辺を削除する仕方って、１通りですよね？
22:34 (Defolos) 着目する点につき１通りですね
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) 行列木定理を学ぶことが今回の目的の２本中のうちの１つです
22:38 (Defolos) 行列木定理は与えられたグラフGのラベル付全域木の個数を与える定理です
22:38 (Defolos) これを理解するには、まず点行列を知る必要があります
22:38 (Defolos) 次の１３ページです
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) では次の１４ページに行きます
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) それで、次の１５ページです
22:45 (Defolos) 例題７．３です
22:46 (Defolos) 問題は資料をご覧ください
22:46 (Defolos) これを解きますので、１６ページをご覧ください
22:46 (Defolos) 隣接行列の復習ですが
22:47 (Defolos) 隣接行列はiとjを結ぶ辺の本数をA[ij]とする行列でした
22:47 (Defolos) ですので、このＡを元にグラフを書くと、１６ページ１つ目のグラフが得られます
22:47 (Defolos) 単純な三角形ですね
22:48 (Defolos) 点行列Dを求めてみます
22:48 (Defolos) まず対角成分にそれぞれの点の次数を入れます
22:48 (Defolos) 全部次数が２なので、２を対角成分にいれていきます
22:49 (Defolos) あとはそれぞれの点は他の点と１本の線で結ばれていますので、対角成分以外の成分には-1を入れます
22:49 (Defolos) ３行３列で余因子展開します
22:50 (Defolos) 余因子展開の前半部分が(-1)^(3+3)なので＋となります
22:51 (Defolos) そうするとＤは２＊２の行列となり、これを２ページで挙げた方法で解きます
22:52 (Defolos) すると4-1がえられますので、答えは３となります
22:52 (Defolos) 実際にＧの全域木は図に挙げたように３つだけです
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) 例題７．３です　といって
22:57 (nesys) 7.4やっているのは何故？
22:58 (Defolos) あああ
22:58 (Defolos) ミスです。ごめんなさい
22:58 (nesys) あぁ。おｋです
22:58 (Defolos) 例題７．４です
22:58 (nesys) 了解。
22:58 (Defolos) に修正
22:58 (Defolos) では17.例題7.5 - 1行きますね
22:58 (nesys) はい
22:59 (Defolos) 問題は資料を見てもらうこととして、回答は１９ページをご覧ください
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) では解答その２に行きます
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) これが端点である確立であり、その２が解答できました
23:05 (Defolos) 次の解答その３なのですが
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) ここまでＯＫでしょうか
23:20 (IPUSIRON) OKです
23:20 (nesys) おｋです
23:21 (dotdister) ダ先どーぞ。
23:21 (dotdister) ミス。
23:21 (Defolos) ＾＾；
23:21 (Defolos) 次の問い２のほうですが
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) ちょっと２の余因子展開については後で修正しておきます
23:28 (IPUSIRON) はい
23:28 (Defolos) 行列δですが
23:28 (Defolos) 隣接行列と点行列の間にはちょっとした関係が存在します
23:29 (Defolos) まず行列δを次のように定義します
23:29 (Defolos) 対角成分のところにはviの次数をいれ、それ以外の成分には０を入れます
23:29 (Defolos) それで、D = δ - Aという関係が存在しています
23:30 (Defolos) 例題7.4のグラフGで確かめてみると、
23:30 (Defolos) δは対角成分に２がはいり、後は０がはいります
23:31 (Defolos) 隣接行列Ａは対角成分が０、後は１が入っていますので、
23:31 (Defolos) δ-Ａは対角成分に２、それ以外に-1が入った行列が得られます
23:31 (Defolos) これはＤと同じなので、関係が確認できます
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) この行列Ａについて考えます
23:37 (Defolos) 実はこれは、先ほど省略した例題７．５の問２の隣接行列です
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の点の数である４が、22成分にはyの点の数である２が入ります
23:40 (Defolos) 他の成分にはxとyで共有している辺の数である１を入れます
23:40 (Defolos) これを２ページのやり方で解くと、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) それでは例題７．６に移ります
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) ごめんなさい、やる時間がなかったですＴＴ
00:01 (IPUSIRON) ここはいいと思います
00:01 (IPUSIRON) お疲れ様でした。ちょうど3時間かかりましたね
00:01 (nesys) ふぅ
00:01 (Defolos) おつかれさまでしたー
00:01 (nesys) お疲れ様でしたー
00:01 (dotdister) お疲れ様ですー。