21:00 (IPUSIRON) 21時ですね
21:00 (clothoid) hai
21:00 (IPUSIRON) 始めてOKです
21:00 (clothoid) はい。それでははじめます。
21:00 (dotdister) よろしくお願いします。
21:00 (clothoid) よろしくお願いします。
21:00 (IPUSIRON) 宜しくお願いします
21:00 (carbon0) よろしくお願いします
21:00 *IPUSIRON mode +o carbon0 
21:00 (clothoid) 資料を開いてください。
21:01 (clothoid) 今回は，SAS第六回ということで，木とその数え上げ　についてです。
21:01 (clothoid) 2ページ目をご覧ください。
21:01 (clothoid) まず，林というものを定義します。
21:02 (clothoid) 林とは閉路を含まないグラフのことを指して言います。
21:02 (clothoid) 次に，木というものを定義します。
21:02 (clothoid) 木とは連結な（つながっている）林のことです。
21:02 (clothoid) 下の図を見てください。
21:03 (clothoid) グラフGは成分が3つあり，閉路が無いので，林です。
21:03 (clothoid) 各々の成分について考えると，連結ですから，木となります。
21:03 (clothoid) p3をご覧ください。
21:04 (clothoid) 木について，p3に挙げたような定理が成り立っています。
21:04 (clothoid) 同値というのは，「おんなじ」という意味でとりあえず大丈夫です。前，出てきたとおもいますが。
21:05 (clothoid) 同値であることの証明はしません。
21:05 (clothoid) 各自，元資料などの木を参考にして，各命題が成り立っていることを確認してください。
21:05 (IPUSIRON) 直観的に全部同値ぽいですね
21:06 (clothoid) そうですね。
21:06 (clothoid) 「明らか」とか書きたいですけど，この言葉，嫌いですｗ
21:06 (clothoid) 自分にとって明らかじゃないときも多々あるから・・・
21:06 (IPUSIRON) 複数の同値性を示すときは、1⇒2⇒…⇒6⇒1を示せばよいのかな
21:07 (clothoid) そうですね。
21:07 (clothoid) サイクリックに十分であることｗ
21:08 (clothoid) あることを証明できれば，OKっぽいですね。。。
21:08 (clothoid) もちろん，各々の命題について，必要十分であることを示しても良いと思いますが。
21:08 (clothoid) 次，p4
21:08 (clothoid) 系2　に書いたようなことが成り立っています。
21:09 (clothoid) 証明として，ダラダラと書きましたが，ここでは次のページ，p5をみてください。
21:09 (clothoid) ちょっと，線が細くて，醜かったですね。すみません。
21:09 (clothoid) 少し拡大して，見てください。
21:10 (clothoid) 例えば，一番左のグラフを考えます。
21:10 (clothoid) このグラフは木で，点の数がn，成分数が1（木だから），辺の数がn-1（木の性質）だとします。
21:11 (clothoid) いま，青で表した辺（＝橋）を切ったとします。
21:11 (clothoid) すると，真ん中に書いたグラフのようになります。
21:12 (clothoid) 辺を切りましたから，成分数が一つ増えて，2に。辺の数は一つ減ってn-2になります。点の数は変わりません。
21:12 (clothoid) このように，「橋」である辺を順次切っていくと，
21:12 (clothoid) 右の図のようになります。
21:13 (clothoid) 右の図は，k-1回ほど，この操作を繰り返した図です。
21:13 (clothoid) 点の数は変わらず，nです。
21:13 (clothoid) 成分数は，最初の状態よりk-1個増えて，k個です。
21:14 (clothoid) 辺の数は，k-1本減って，n-1-(k-1)=n-kとなります。
21:14 (clothoid) したがって，このことから，系2の命題が成り立つことが分かります。
21:15 (IPUSIRON) ですね
21:15 (clothoid) 特に質問が無ければ，次へ進みたいと思いますが。
21:15 (clothoid) p.6です。系3。
21:16 (clothoid) これの証明は，元資料に載ってるものでは納得できませんでした。
21:16 (clothoid) その理由はSNSに記したとおりです。
21:17 (clothoid) ここでは，自分なりに考えて，なっとくできた方法を説明たいと思います
21:17 (dotdister) 多分clothoidさんので正しいと思います。
21:17 (clothoid) 説明したい　の間違い。
21:17 (clothoid) 基本的に説明をそのまま読むことになりますが，お付き合いください。
21:18 (IPUSIRON) はい
21:18 (clothoid) まず，端点が無い場合。すなわち，0個の場合を考えます。
21:18 (clothoid) 了解しました。＜多分正しい＞IPUSIRONさん
21:19 (clothoid) 端点がゼロ個というのは，閉路があることに他なりません。
21:19 (clothoid) 木には閉路があってはいけませんから，
21:19 (clothoid) 端点が0個である木とは存在しません。
21:19 (clothoid) 次に，端点が1個の場合を考えます。
21:19 (IPUSIRON) ちょっと待って
21:19 (clothoid) はい。
21:19 (IPUSIRON) スライド6で
21:20 (IPUSIRON) 「まず端点が0の木を考える」といってるけど
21:20 (IPUSIRON) これが矛盾であることを示すわけだから、「まず端点が0のグラフを考える」とすべきかな
21:21 (IPUSIRON) そのグラフは結局木にならないことを示すわけだから
21:21 (clothoid) 「まず端点が0の木を考える」→「まず端点が0の木があると仮定する」ならOKですか？
21:21 (IPUSIRON) それならOKです
21:22 (clothoid) 了解です。そのように直しておきます。
21:22 (IPUSIRON) 「端点が0」かつ「木」の両方を考えると矛盾するわけですね
21:22 (clothoid) はい。そうです。
21:22 (IPUSIRON) 次OKです
21:22 (clothoid) 同様に，端点が1個の木を仮定してみます。
21:23 (clothoid) 仮定に「単点（＝点一個のみ）」ではないと書いていますから，
21:23 (clothoid) 端点が1個の木の次数は1であるはずです。
21:24 (clothoid) いま，この端点を除去する操作を考えて見ます。
21:24 (clothoid) みます。
21:24 (clothoid) すると，残ったグラフに端点があってはなりませんから（あったら，端点が1つという仮定に反する），
21:25 (clothoid) 残ったグラフの中は閉路となっているはずです。
21:25 (clothoid) 次ページの図を参照してください。
21:25 (dotdister) 質問いいですか？
21:25 (clothoid) はい。
21:26 (dotdister) 端点が1個の木の次数は1であるはずです。　　木の次数とは？
21:26 (clothoid) あ，すみません。
21:26 (clothoid) 端点の次数です。
21:27 (dotdister) 端点って次数が１の点のことですよね？
21:27 (clothoid) 次数とは点に繋がってる線の数ことです。
21:27 (clothoid) あれ。そうでしたっけ？
21:27 (dotdister) 端点の定義が・・・良く分からないのですが。
21:28 (IPUSIRON) 次数が1の点が端点かなあ
21:28 (IPUSIRON) ここには書いてないけど
21:28 (clothoid) 次数が0と1の点が端点だと思います。
21:29 (dotdister) ということは、単点も端点ですかね？
21:29 (clothoid) 単点も端点です。
21:29 (clothoid) はい。
21:29 (dotdister) 了解です。先にどーぞ。
21:29 (clothoid) おそらく。
21:29 (clothoid) えー，考えてる端点は単点じゃありませんから，次数が1で，p7のようなグラフが考えられます。
21:30 (clothoid) で，端点を除去して残るグラフについて考えると，
21:30 (clothoid) このグラフは端点をもっていてはいけないので，閉路を作ってるはずです。
21:30 (clothoid) しかし，閉路があると木とはなりません。
21:30 (clothoid) したがって，仮定が矛盾。
21:31 (clothoid) よって，端点は1じゃありません。
21:31 (clothoid) 以上のことから，端点が0，1，というのはありえないことが分かり，系3が理解できます。
21:31 (IPUSIRON) ここまではいいんですが、この説明で示せたのは「少なくとも2点の端点を含む可能性がある」ことだと思うんですが
21:32 (clothoid) はい。そう思います。
21:32 (IPUSIRON) 端点が2かつ木として、考えたら矛盾出るかもしれないですよ（でないけど）
21:32 (clothoid) はい。
21:32 (clothoid) んで，どーしよーと。。。よく分からなかったです。どういう風に証明を組み立てればいいのか。
21:33 (clothoid) なので，証明でなく「説明」になってます。。。
21:33 (IPUSIRON) なるほど
21:34 (IPUSIRON) 資料に書いてある証明がダメだと思う理由はなんだったんですか？
21:34 (IPUSIRON) pの代入のところですか
21:34 (clothoid) はい。
21:35 (dotdister) そこは私も納得いきませんでした。
21:35 (clothoid) 証明の最後で，pを0または1として代入するのですが，
21:35 (clothoid) pとは木の点の数のことで，
21:35 (clothoid) 端点の数ではありません。
21:35 (clothoid) したがって，これは，まったく見当違いの証明かと思いました。
21:36 (IPUSIRON) なるほど。でも「従って」の直前までは成り立つ性質なわけだから、これを利用して証明できないかな
21:37 (clothoid) なるほど。。。
21:37 (clothoid) 偶数とか？
21:38 (IPUSIRON) 難しいね
21:38 (IPUSIRON) 自分はちょっと今すぐは見当つかない
21:39 (clothoid) すみません。僕もちょっと分かりません。
21:39 (IPUSIRON) 飛ばして進みましょうか
21:39 (clothoid) しばらく宿題にさせてください。はい。
21:39 (IPUSIRON) 具体的に端点が2以上の木は簡単に作れますからね
21:40 (clothoid) ということで，とりあえず，端点は0個，または1個じゃないってことは分かりました。んで，あとは直感的に少なくても2個ぐらいあるだろう・・・という感じです。系3の説明。
21:40 (IPUSIRON) 1点打って、それに枝葉をつければ
21:40 (IPUSIRON) 端点が2でも3でも1万でも自由に作れるから
21:41 (clothoid) そうですね。。。。点2個と線一本が最も単純な木ですし。
21:41 (clothoid) （↑単点じゃない場合）
21:42 (clothoid) 次にいきます。。。p.8
21:42 (IPUSIRON) 「単点でない木の端点は、0や1個ではありえない」というところまで示せたので一応OKにしましょう
21:42 (clothoid) はい。
21:42 (clothoid) 全域木というのを定義します。
21:43 (clothoid) 定義はスライドに載せたとおりです。グラフから，どんどん辺をなくしていき，閉路が無くなったらストップしたものです。
21:43 (clothoid) 下の例を参考にしてみてください。
21:44 (clothoid) 次，p9です。
21:44 (clothoid) 全域「木」の「林」バージョンだと思えばOKです。
21:44 (clothoid) 次，p.10
21:44 (clothoid) 階数というのを定義します。
21:45 (clothoid) 閉路回数とは全域林を得るまでに削除した辺の数のことです。
21:45 (clothoid) カットセット階数とは全域林の辺の数です。
21:46 (clothoid) 元資料では「全域木」となっていますが，たぶん「全域林」だと思います。
21:47 (clothoid) その理由は，カットセットξ（Ｇ）＝n-kだと書いてあるから。これについては，次ページです。
21:48 (IPUSIRON) 林でないとk（成分数）出てくるわけないですからね
21:48 (clothoid) 次のページ，11です。
21:48 (clothoid) はい＜林でないと
21:48 (IPUSIRON) 出てくるわけがないというか、木ならk=1と一定だから
21:48 (IPUSIRON) 次どうぞ
21:48 (clothoid) 閉路階数とカットセット階数の関係を考えます。
21:49 (clothoid) n 個の点とm本の辺，k 個の成分があるグラフG を考えます
21:49 (clothoid) 閉路回数の定義から，
21:49 (clothoid) 閉路階数の定義から，
21:50 (clothoid) 閉路階数＝(G の辺の数)-(G から作られる全域林の辺の数)
21:50 (clothoid) であることが分かります。
21:50 (clothoid) Gの辺の数がm
21:50 (clothoid) Gから作られる全域林の辺の数は，系2を用いて，n-kだと分かります。
21:51 (clothoid) したがって，閉路階数＝m-(n-k)=m-n+kであるといえます。
21:51 (clothoid) 次に，カットセット階数を考えます。
21:52 (clothoid) カットセット階数は，系2より，n-kです。
21:52 (clothoid) したがって，閉路階数＋カットセット回数＝初めに考えたグラフGの辺の数m
21:52 (clothoid) であることが分かります。
21:53 (clothoid) 次に，p12
21:54 (clothoid) typoですかね。。。
21:54 (clothoid) 全域木じゃなくて，全域林です。。。
21:54 (clothoid) T がグラフG の全域林ならば
21:54 (clothoid) 以下の，1，2が成り立つ
21:55 (clothoid) です。
21:55 (clothoid) 1のGの全てのカットセットは〜というのは，
21:56 (clothoid) 全域林を得る過程で，カットセットは切りませんから，全域林Tの辺にはGの全てのカットセットが含まれることになります。
21:56 (clothoid) 2のGの全ての閉路は〜というのは，
21:58 (clothoid) GからTを得る仮定で，閉路が削除されていきますから，Tの補グラフ，すなわち，閉路を削除するために消された辺から成り立つグラフに，Gの全ての閉路が含まれます。
21:58 (clothoid) ×仮定　○過程
21:59 (clothoid) 証明は，元資料には教科書よめって書いてありますので，省略させてください。
21:59 (clothoid) 背理法とか使って証明するのかなぁ？とは考えましたが，
21:59 (clothoid) ちゃんと考えられていません。ぱっと思いつきませんでした。
21:59 (clothoid) すみません。
22:00 (clothoid) 定理を実感するには，具体例で確かめるといいとおもいます（後で例題で出てきます）
22:00 (clothoid) p.13
22:00 (clothoid) 基本閉路集合
22:02 (clothoid) Tに含まれないGの任意の辺を一つTに付加して，いろいろな閉路をつくり，集めたのが基本閉路集合です。
22:02 (IPUSIRON) これは多重辺は考えないのかな？
22:02 (clothoid) 考えてもいいと思います。
22:03 (IPUSIRON) 多重辺を考えるなら、点が2個で辺が2個のグラフも基本閉路集合に入りますよね
22:03 (clothoid) 下の例にですか？
22:04 (IPUSIRON) 後、図で三角の形のグラフが3つあるけど、点とかx,yとかが違うから別物として考えるのかな
22:04 (IPUSIRON) そそ＜下の例
22:04 (dotdister) 元資料に木Tに関連した基本閉路集合、と書いてありますが・・・
22:05 (clothoid) えっと・・・
22:05 (IPUSIRON) 木Tに関連したというのは、最初に木を考えるということだと思う
22:05 (clothoid) 下の例ですけど，グラフGはp.8の左図です。
22:05 (clothoid) Tはp.8右図です。
22:06 (IPUSIRON) はい
22:06 (IPUSIRON) わかりました
22:06 (clothoid) で，p,8のグラフG
22:06 (clothoid) あ，はい。
22:07 (IPUSIRON) まずGありきなんですね
22:07 (clothoid) 多重辺を考えるなら、点が2個で辺が2個のグラフも基本閉路集合に入りますよね＜これは，そうじゃないってことでOK?
22:07 (clothoid) そうです。Gありきです。
22:07 (IPUSIRON) G→全域木Tにしてから　考えているわけですね。わかりました
22:07 (clothoid) はい。
22:08 (clothoid) 元資料に木Tに関連した基本閉路集合、と書いてありますが・・・＜これはどういう意味かわからないんっすけども
22:09 (dotdister) 先ほどIPUSHIRONさんにお答えいただいたので大丈夫です。
22:09 (clothoid) はい。すみません。
22:09 (clothoid) 次に進みます。
22:09 (clothoid) p.14
22:09 (clothoid) 基本カットセット集合
22:10 (clothoid) GからつくられたTの各辺を除去して得られるカットセット集合3を基本カットセット集合といいます。
22:11 (clothoid) 下の例では，p.8のGからつくられたTのカットセット集合として，{e1，e5}を挙げています。
22:11 (clothoid) 次，p
22:11 (clothoid) p.15
22:12 (clothoid) 例題を解きます。
22:12 (clothoid) 新しい概念，「中心」というのが例題中に定義されているので，
22:12 (clothoid) スライドと同じですが，繰り返します。
22:13 (clothoid) 中心vとは，vとG の他点の間の距離の最大値ができるだけ小さい
22:13 (clothoid) もののことです。
22:14 (clothoid) 直感的には，真ん中にいるってやつです。どの端点へも一番近いやつ。
22:14 (clothoid) 例題を解きたいと思います。
22:14 (clothoid) まず，(1)
22:15 (clothoid) 端点を徐々に除去していくと，中心を求めることができます（できるそうです）
22:15 (clothoid) ×走査　○操作
22:15 (clothoid) 中心を求めるグラフはp.16
22:15 (clothoid) 解等は，p.17です。
22:16 (clothoid) まず，与えられたグラフから端点を取り除きます。
22:16 (clothoid) ここでは，
22:16 (clothoid) 1，２，４，５，８，９，１２，１３，１５，１６です
22:16 (clothoid) すると青で囲ったところのみがのこったグラフとなります。
22:17 (clothoid) 同様に端点を取り除く操作を繰り返すと，
22:17 (clothoid) 緑でくくったグラフ→赤でくくったグラフとなっていきます。
22:17 (clothoid) 最後に残った，点11がこのグラフの中心です。
22:18 (clothoid) 次の問題を解きたいと思います
22:18 (IPUSIRON) はい
22:18 (clothoid) どんな木でも中心が１個か２個であることを示せです。
22:19 (clothoid) 先ほどの問題でみたように，
22:19 (clothoid) 中心を求めるには端点を削っていけばOKです。
22:19 (clothoid) そして，最後にのこったものが，中心です。
22:19 (clothoid) この考え方を用いると，
22:20 (clothoid) 残りの点が，1つ，または2つの場合は，「端点を削る」ことができません。
22:20 (clothoid) なぜならば，点が残らないから。
22:20 (clothoid) それに対し，3つ以上，点があれば，端点を削る操作ができます。
22:21 (clothoid) 例えば，3つの場合，二つけずって，1個残るなど。
22:21 (clothoid) 以上から，中心は1つか2つであることが分かります。
22:22 (clothoid) この解答はオリジナルなので，ちょっと怪しいです・・・
22:22 (clothoid) 不安です。
22:22 (IPUSIRON) 大丈夫だと思いますが、その説明ですでに(3)も自明ぽいですね
22:23 (clothoid) 元資料の解答は中心が３つの場合しか考えてないので，駄目だと思います。
22:23 (IPUSIRON) うん
22:24 (clothoid) そうですね。考え方は同じです＜（３）
22:24 (clothoid) 続いて，（３）
22:24 (clothoid) p.19です。
22:24 (clothoid) 中心が2つあるばあい，隣接してるか，してないかです。
22:25 (clothoid) p.20をみてください。
22:25 (clothoid) 隣接して無いと仮定します。
22:25 (clothoid) すると，例えば，矢印の下のような場合が考えられますが，
22:26 (clothoid) これは，端点を除去する操作が可能であり，かつ，中心２つであったはずのc1とc2が，中心でなくなってしまいます。この場合Ｖが中心。
22:26 (clothoid) これは矛盾なので，中心c1とc2は隣接してます。
22:26 (clothoid) 基本的な考え方はこんな感じで，文章では，もう少しゴタゴタ書いています。
22:27 (clothoid) 読んでいただけば大丈夫だと思うので，次に行きます。
22:27 (clothoid) （４）です。p.21
22:27 (clothoid) 中心が1個，2個の例を挙げよ。
22:27 (clothoid) まぁ，色々書けば出てくるんですが，
22:28 (clothoid) 簡単に各方法は，
22:28 (clothoid) 中心一個の場合は，その中心１個を対称点にして書く，
22:29 (clothoid) 中心二個の場合は，この中心二個を結ぶ線の真ん中を対象点として書けば，そうなります。
22:29 (clothoid) 続いて，p22の例題を解きます。
22:29 (clothoid) 全域木を描き出す問題です。（１）
22:30 (clothoid) 考えるグラフはp23です。
22:30 (clothoid) 考え方は，p24に書きました。
22:31 (clothoid) チョウチョのような形から閉路を無くすことを考えますから，
22:31 (clothoid) 左の羽から，辺をひとつ，右の羽から辺を一つとれば，閉路がなくなります。
22:32 (clothoid) 辺は，右の羽に３つ，左の羽に３つありますから，閉路を無くす方法は，3*3の9とおりあることになります。
22:32 (clothoid) あとはせっせと書いていくだけです。
22:32 (clothoid) p.25が答え。
22:32 (clothoid) 次の問題です。
22:33 (clothoid) 定理4（元資料では9.3）の例を考える問題です
22:34 (clothoid) 例えば，p27の左図のようなグラフを考えます。
22:34 (clothoid) この場合，全域木は，右の図のようになります。
22:34 (clothoid) どの全域木にも辺eが含まれて居ます。
22:35 (clothoid) もともと考えてたグラフにおける辺eの役割は，カットセットです。
22:35 (clothoid) したがって，C^*=eとすれば，問題が解けたことになります。
22:35 (clothoid) p.28練習問題を解きます。
22:36 (clothoid) ここまで，みなさん，大丈夫でしょうか？
22:36 (IPUSIRON) おｋです
22:36 (dotdister) 一応は。
22:36 (clothoid) それでは，練習問題6
22:38 (clothoid) ×T1 の辺e 除去し　○T1 の辺e を除去し
22:38 (clothoid) (1)の解答はp.30を観てください。
22:39 (clothoid) ここでは，さきほど考えたチョウチョの全域木を3つほど書いています。
22:39 (clothoid) そして，図のように，T1，T2，T3と名前をつけています
22:39 (clothoid) 今，T1の辺eに注目し，
22:39 (clothoid) 辺eを削除し，
22:40 (clothoid) 変わりに，T2の辺fを，T1に書いたとします。
22:40 (clothoid) すると，T3ができあがりますが，
22:40 (clothoid) これはチョウチョの全域木の一つです。
22:40 (clothoid) したがって，問題が示されたことになります。
22:41 (clothoid) 次に，（２）
22:41 (clothoid) 今度は，T1→T3→T2の順で「変換」していきます。
22:41 (clothoid) T1→T3への変換は（１）でやったとおりです。
22:41 (clothoid) 辺eを除去して，辺fを加えます。
22:42 (clothoid) T3からT2への変換は，
22:42 (clothoid) 緑を除去して，オレンジを加える操作です。
22:42 (IPUSIRON) なるほど
22:42 (clothoid) こうすると，T1をT2へ変換でき，かつ，その変換過程で得られるグラフは全て全域木です。
22:43 (clothoid) 以上で，練習問題6が終わりです。
22:43 (clothoid) んでもって，第六回も以上ですが，
22:43 (clothoid) なにか質問はありますか？
22:43 (IPUSIRON) お疲れ様です
22:43 (dotdister) お疲れ様ですー。
22:44 (carbon0) お疲れ様でした
22:44 (clothoid) ありがとうございます。今回は，短くて助かりました^^；