21:00 (nesys) 始めますか
21:00 (IPUSIRON) はい。宜しくお願いします
21:00 *carbon0 join #akademeia (~nanashi@softbank219057130001.bbtec.net)
21:00 (nesys) ぉ
21:00 (nesys) こんばんわ
21:00 (IPUSIRON) こんばんは
21:01 (nesys) とりあえず始めますか
21:01 (carbon0) こんばんは
21:01 (IPUSIRON) どぞ
21:01 (nesys) 2p
21:01 (nesys) 今回の目的です
21:01 (nesys) 平面性について学びます
21:01 (IPUSIRON) ページ番号ないから、修正版でよろしくです（笑）
21:01 (nesys) あ
21:02 (nesys) すみませｎ
21:02 (nesys) パワポをpdfに変換しただけで、いじってませんでした
21:02 (IPUSIRON) Acrobatのほうの番号で見ます
21:02 (nesys) まぁ”目的”の項ｗ
21:03 (nesys) 平面性について学びます
21:03 (nesys) グラフが平面内にどの辺も交差することなく、描くことのできる条件とは
21:03 (nesys) つまり、平面グラフができる条件について
21:03 (nesys) 平面グラフの性質について
21:03 (nesys) グラフの平面の描き”やすさ”について
21:03 (nesys) 交差点や暑さの概念を用いて表します
21:04 (nesys) 以上が今回の目的です
21:04 (nesys) 次のページ
21:04 (nesys) 3pかな？
21:04 (IPUSIRON) はい
21:04 (nesys) 平面グラフとオライリーの公式
21:04 (nesys) 4p
21:04 (nesys) 平面グラフとは
21:04 (nesys) グラフを見たら分かりやすいですが
21:05 (nesys) 要するに辺が重なることのないグラフのことです
21:05 (nesys) 図の右側が平面グラフになりますね
21:05 (nesys) 5p
21:05 (nesys) 面とは
21:06 (IPUSIRON) あ
21:06 (nesys) ん？
21:06 (IPUSIRON) ４Pの左の図だけど
21:06 (nesys) はい
21:06 (IPUSIRON) これは平面グラフだけど、一目見て平面グラフとわからないというだけじゃないかな？
21:06 (nesys) あー厚さのことですか？
21:07 (IPUSIRON) 厚さの定義まだわからないけど
21:07 (IPUSIRON) 元資料見てみると
21:07 (IPUSIRON) 「右のようにかけば平面グラフとわかる」と書いてあって
21:07 (nesys) ほんとだ
21:07 (IPUSIRON) 左が平面グラフではないといってないから
21:08 (IPUSIRON) 位相同型だから多分平面グラフになってるはずかな
21:08 (nesys) じゃあすべてのグラフが平面グラフということになるんですかね？
21:08 (nesys) あ
21:08 (IPUSIRON) いや
21:08 (nesys) 分かりました
21:08 (IPUSIRON) それは定理を適用しないとわかんないんじゃないかな
21:08 (IPUSIRON) その後のオイラー公式とかでね
21:08 (nesys) そうですね
21:08 (nesys) 分かりました。直しておきます
21:08 (IPUSIRON) はい
21:09 (nesys) では5p
21:09 (nesys) 面とは
21:09 (nesys) 辺によって分割された領域のことです
21:10 (nesys) 図でいう　f数字　が割り当てられているところですね。
21:10 (nesys) f4も面に含まれていて、辺で囲まれていないこの面のことを、無限面と言います。
21:11 (nesys) グラフは必ず最低限1つの無限面がある、ということですね
21:11 (nesys) 6p
21:11 (nesys) オイラーの公式について
21:11 (nesys) 連結平面グラフいおいて、n-m+f=2という公式が成り立ちます。
21:12 (nesys) 連結であることがポイントですね
21:12 (IPUSIRON) n,m,fの定義は？
21:12 (nesys) nが点数。mが辺数。fが面数。とを表します
21:12 (IPUSIRON) はい
21:12 (nesys) p7
21:12 (nesys) 確認してみましょう。
21:13 (nesys) この図の点数は4、辺数は6、面数は4になります。
21:13 (nesys) 公式に入れると
21:13 (nesys) 4-6+4=2と
21:13 (nesys) 成り立ちました
21:13 (nesys) p8
21:14 (nesys) 非平面グラフで試してみましょう。
21:14 (nesys) 非平面グラフというんですかね？
21:15 (nesys) まぁ、点数は4、辺数は6、面数が5になって
21:15 (nesys) 公式に入れると
21:15 (nesys) 4-6-5=3で
21:15 (nesys) 成り立ちませんでした
21:15 (nesys) やっぱりこれは平面グラフではない。ということですかね？
21:15 (IPUSIRON) 空中配線で考えれば、面数変化しないとおもうんだけど
21:15 (nesys) あぁ
21:15 (nesys) なるほど
21:15 (IPUSIRON) 空中でも面はできるからね
21:16 (nesys) でも、平面で考えるときに、空中の面は考えていいんですか？
21:16 (IPUSIRON) どうやっても面と面が重なってしまうグラフが、非平面なんじゃないかな
21:16 (IPUSIRON) 定義では別にだめといってないからいいと思うよ
21:16 (nesys) なるほど
21:16 (IPUSIRON) 平面といってるのは
21:17 (IPUSIRON) 平面で考えるとわかりやすいことに由来してるんじゃないかな
21:17 (nesys) なるほど
21:18 (IPUSIRON) だからP8は平面グラフという解釈でいきましょうか
21:18 (nesys) ではこの交差しているグラフにおいても、面は4つになるということですね
21:18 (nesys) 見方が３D描写になっていないと難しいですあｇ
21:18 (IPUSIRON) グラフ自体の定義は
21:18 (IPUSIRON) 別にクロテンがなければ交差してないからね
21:19 (nesys) ｆｍ
21:19 (IPUSIRON) だから面との重なり具合で本来平面・非平面を区別するんだけど
21:19 (IPUSIRON) あくまで平面に書くということにこだわると
21:19 (IPUSIRON) 平面状でどうやっても交差してしまうのが非平面ということになるんだと思う
21:19 (IPUSIRON) 平面上
21:20 (nesys) なるほど
21:20 (nesys) 分かりました。直しておきます
21:20 (nesys) ではp9
21:20 (nesys) オイラーの公式を証明しましょう
21:20 (nesys) 辺数mに対する数学的帰納法を用います
21:21 (nesys) まずm=0のとき
21:21 (nesys) 辺が0ですから、点が1つしかなく、面は無限面1つだけです。
21:21 (nesys) m=0, n=1, f=1
21:22 (nesys) これらをオイラーの公式に代入すると
21:22 (nesys) n-m+f=1-0+1=2
21:22 (nesys) と、成り立ちます
21:22 (nesys) p10
21:22 (IPUSIRON) オイラーの公式に代入するというか、オイラーの公式の左辺ね
21:22 (nesys) あぁ
21:22 (nesys) そうですね
21:22 (IPUSIRON) どぞ
21:23 (nesys) また、「m-1本以下の辺を持つ全てのグラフGは成り立つ」と仮定します
21:23 *Defolos join #akademeia (~anonymous@eaoska121085.adsl.ppp.infoweb.ne.jp)
21:23 (IPUSIRON) こんばんは
21:23 (nesys) こんばんわ
21:23 (Defolos) こんばんは
21:23 (nesys) 資料ぎりぎりになってすみませんでした
21:23 (Defolos) 遅くなって申し訳ありません
21:23 (IPUSIRON) 「グラフGは成り立つ」という部分なんだけど
21:23 (nesys) ん？
21:23 (IPUSIRON) 「グラフGでは、関係式が成り立つ」じゃないかな？
21:23 (nesys) あぁ。そうですね
21:24 (IPUSIRON) 日本語の問題ね
21:24 (IPUSIRON) 意味はわかるけど（笑）。どぞ
21:24 (nesys) 今、資料のp10のところです
21:24 (Defolos) ありがとうございます
21:24 (nesys) 「m-1本以下の辺を持つ全てのグラフGでは、関係式が成り立つ」と仮定します
21:25 (nesys) グラフGが木の場合、m本の辺があるとすると、
21:25 (nesys) 辺数は点数-1で、m=n-1
21:25 (nesys) 無限面1つより、f=1であるから
21:26 (nesys) 関係式はn-m+f=n-(n-1)+1=2で
21:26 (nesys) オイラーの公式が成り立ちました
21:26 (nesys) m=0の場合と、今回の仮定が成り立つことより、
21:27 (nesys) 辺数mに対して、オイラーの公式は成り立ちます
21:27 (IPUSIRON) 木じゃない場合は？
21:27 (nesys) あ
21:27 (nesys) 忘れてましたｗ
21:27 (nesys) p11
21:27 (nesys) グラフG
21:27 (nesys) が木でない場合
21:27 (IPUSIRON) 辺mのときで木or木でないで場合わけしてるからね
21:28 (nesys) グラフGの任意の辺を消してみます
21:28 (nesys) 実際にノートなどに小さなグラフを描いて
21:28 (nesys) １つ消してみたら分かりやすいです
21:28 (nesys) 点数は変わらず
21:28 (nesys) 辺数は1つ減り
21:28 (nesys) 面数も1つ減ります
21:29 (nesys) p12
21:29 (nesys) n=n, m=m-1, f=f-1をオイラーの公式の左辺に代入しましょう
21:29 (nesys) n-(m-1)+f-1=n-m+f=2
21:29 (nesys) と、元の形に戻りました
21:30 (IPUSIRON) 代入してOKなのは、「辺m-1以下でオイラーの公式が成り立つ」という仮定が効いてるからね
21:30 (nesys) あ。はい
21:30 (IPUSIRON) 仮定があるから、どこかで仮定使わないとダメで、ここで使って
21:30 (IPUSIRON) 式変形して、きれいになおすと、mの場合でもなりたっちゃったってことね
21:31 (nesys) 書き足しておきます
21:31 (IPUSIRON) ここで初めて辺mかつ木でないときでオイラーの公式が成り立つことが示せたわけです
21:31 (IPUSIRON) はい
21:32 (nesys) 以上、オイラーの公式が成り立つことが証明されました
21:32 (nesys) p13
21:32 (nesys) 次は非連結グラフにおけるオイラーの公式を見てみましょう
21:32 (nesys) 非連結であるため、成分数をkと定義します
21:33 (nesys) そのとき、
21:33 (nesys) n-m+f=k+1
21:33 (nesys) が成り立ちます
21:33 (nesys) 確認してみましょう
21:33 (nesys) p14
21:33 (nesys) 図では
21:33 (nesys) n=6, m=6, f=3, k=2となっています
21:33 (nesys) それを先ほどの公式に代入すると
21:34 (nesys) 6-6+3=2+1  3=3
21:34 (nesys) と、あってました。
21:34 (IPUSIRON) ここだけど
21:34 (nesys) はい
21:34 (IPUSIRON) （左辺）＝・・・、（右辺）＝・・・　で（左辺）＝（右辺）となって確認されたというほうが正しいかな
21:34 (nesys) あぁ
21:35 (nesys) なるほど
21:35 (IPUSIRON) 関係式の確認というのは
21:35 (IPUSIRON) 左辺に代入した結果と右辺に代入した結果が一致することだから
21:35 (nesys) はい
21:35 (IPUSIRON) 先どうぞ
21:36 (nesys) 直しておきます
21:36 (nesys) p15
21:36 (nesys) これは非連結グラフにつもりの図でしたが
21:36 (nesys) あ
21:36 (nesys) これは非平面グラフのつもりの図でしたが
21:36 (nesys) この左のグラフも平面グラフということでしたので
21:37 (nesys) 飛ばします
21:37 (IPUSIRON) 平面グラフで考えると一致するね
21:37 (IPUSIRON) はい
21:37 (nesys) p16
21:37 (nesys) 証明してみましょう
21:37 (nesys) グラフGにk個の成分があるということは
21:38 (nesys) 無限面をk-1個余分に数えられているので
21:38 (nesys) 面数はf-(k-1)になり
21:38 (nesys) オイラーの公式に入れてみます
21:38 (nesys) n-m+{f-(k-1)
21:38 (nesys) miss
21:39 (nesys)  n-m+{f-(k-1)}=2
21:39 (nesys) これを整理すると
21:39 (nesys) n-m+f=k+1
21:39 (nesys) となるので、この式は成り立ちます
21:39 (nesys) p17
21:39 (nesys) 軽い例題をやってみましょう
21:40 (nesys) 問題は元資料見る感じでいいですか？
21:40 (IPUSIRON) はい
21:40 (nesys) 完全グラフK4が平面的であるかどうかです
21:40 (nesys) まぁ描いて、ちょっと辺をずらしてみたら
21:40 (nesys) あっさりと平面的であることが分かりました
21:41 (nesys) ちなみに、例題8.1（１）です
21:41 (nesys) 次、（２）　p18
21:41 (nesys) 完全グラフK5が平面的であるかどうか
21:42 (nesys) 書いてみたら、こう六ぼう聖のような形になりました
21:42 (nesys) なんとか辺が重ならないように出してみます
21:42 (nesys) どうしても1か所だけ重なってしまいました
21:42 (nesys) よってこれは平面的ではありません
21:43 (nesys) (3) p19
21:43 (IPUSIRON) 試行錯誤の結果に平面的じゃなさそうだということで
21:43 (nesys) ｎ
21:43 (IPUSIRON) まだ平面的でないとは断言できないよね（あくまで）
21:43 (nesys) あー
21:43 (IPUSIRON) 断言するには証明必要ということで
21:43 (nesys) 数学的に断言する必要がありますかね？
21:43 (IPUSIRON) ここでは直観的に考えている平面的じゃないということでOKだけど
21:43 (IPUSIRON) いやここではやらなくてもいいけど
21:44 (IPUSIRON) 文章を直せばいいだけだと思う
21:44 (nesys) 了解です
21:44 (IPUSIRON) 断言じゃなくて、期待できるという漢字で
21:44 (IPUSIRON) 感じ
21:44 (nesys) (3) p19
21:44 (nesys) 完全二部グラフK3,3が平面的であるかどうかです
21:45 (nesys) K3,3は右上の図のようなグラフのことですね
21:45 (nesys) 上と下がそれぞれグループでわかれています
21:45 (nesys) さて、頑張って交差しないようにしてみましょう
21:45 (nesys) 今回もどれだけ頑張ってもできませんでした
21:46 (nesys) よって、K3,3は平面的ではないはずです
21:46 (nesys) p20
21:46 (IPUSIRON) 完全グラフK5で平面的じゃないと期待できるわけだから、完全グラフK6も平面的じゃないのかなあ
21:46 (nesys) あ
21:46 (nesys) 確認してみるかな
21:46 (nesys) 少し時間かかりますがいいですか？
21:46 (IPUSIRON) はい
21:47 (IPUSIRON) K6の中にK5が存在したら平面的じゃないね
21:48 (nesys) どこか、画像をすぐにはれる場所があれば楽なんですけどね
21:48 (IPUSIRON) うん
21:48 (IPUSIRON) 開発してくださいよ（笑）
21:48 (IPUSIRON) でもいまやってみたら
21:48 (Defolos) やってみた限りでは平面的じゃないような気がしますね
21:48 (IPUSIRON) K5が中に存在するね
21:49 (IPUSIRON) 五角形＋星方
21:49 (IPUSIRON) 型がある
21:49 (nesys) そうですね
21:49 (nesys) こうなってくると
21:49 (IPUSIRON) となると完全グラフで平面的なのはK4以下の３つだけぽいね
21:49 (nesys) K7も確認してみたいですねｗ
21:49 (nesys) だけなんですか？
21:50 (IPUSIRON) K3もあきらかに平面的
21:50 (IPUSIRON) K2,K1,K0?もそうだね
21:50 (IPUSIRON) じゃ4つだ
21:50 (IPUSIRON) 完全グラフに関していえば
21:50 (nesys) なるほど
21:50 (IPUSIRON) 直観的であって証明はしてないからなんともいえないけど、
21:51 (nesys) まぁそうですね
21:51 (IPUSIRON) ここで新しい定理を発見できてよかった（笑）
21:51 (nesys) 2部や3部においてもどうなのか確認してみたくなりましたｗ
21:51 (IPUSIRON) 次OKです
21:51 (nesys) まぁ次行きますか
21:51 (nesys) p20
21:52 (nesys) 系13.4
21:52 (nesys) 連結単純平面グラフGが、n(≧3)個の点とm本の辺を持つとき、m<=3n-6が成り立つ。
21:52 (IPUSIRON) 単純グラフって何だっけ…？
21:52 (nesys) さらに、Gに三角形がなければ、m<=2n-4が成り立つ
21:52 (nesys) とのことです
21:52 (nesys) えっと
21:53 (nesys) んーなんだっけｗ
21:53 (Defolos) ループと多重辺がないグラフですね
21:53 (nesys) あ
21:53 (nesys) そうそう
21:53 (nesys) それですね
21:53 (IPUSIRON) ループとかなしだっけ
21:53 (IPUSIRON) 多重辺とか
21:53 (Defolos) だったはずです
21:53 (IPUSIRON) つまり普通？のグラフだね
21:53 (Defolos) まぁ、普通ですね＾＾；
21:53 (nesys) ですねｗ
21:54 (nesys) １つめの証明をしましょう
21:54 (nesys) p21
21:54 (nesys) 最少の点数が3とあったので
21:55 (nesys) 閉路長3からなる三角形のことですね
21:55 (nesys) よって、3<=d(F)となり
21:55 (nesys) あ
21:55 (nesys) d(F)とは
21:55 (nesys) グラフGにおける面Fに含まれる点の次数和のことです
21:56 (nesys) したがって
21:56 (IPUSIRON) ちょっとまって
21:56 (nesys) はい
21:56 (IPUSIRON) 最少の点数が3とあったので　⇒　閉路長3からなる三角形のことですね　ということ？
21:56 (nesys) ですね
21:57 (IPUSIRON) うーん
21:58 (nesys) 最少な面を考えた場合
21:58 (IPUSIRON) 点の個数と、Gに含まれる最小の面の関係は、こういいきれないようなきがする
21:58 (IPUSIRON) 点の個数というより、一般にGに含まれる最小の面は三角形ということじゃないかな？
21:58 (nesys) そうですね
21:58 (nesys) 説明し忘れてました
21:58 (IPUSIRON) 一般にといったけど、3以上の点という意味
21:59 (IPUSIRON) ここで単純が効いて来るんだと思う
21:59 (IPUSIRON) 単純かつ点が3以上⇒最小の面は三角形　だと思った
21:59 (Defolos) 非単純グラフだとループで面ひとつと数えられますからね
21:59 (nesys) ああ。なるほど
21:59 (IPUSIRON) 単純じゃなく、多重辺があったら2角形？の面が存在しちゃう
21:59 (IPUSIRON) そそ
22:00 (IPUSIRON) 単純かつ点が3以上⇒最小の面は三角⇒3≦d(F)　とくるわけだね
22:00 (nesys) はい
22:00 (IPUSIRON) 次に握手の補題を使うわけね。続きどうぞ
22:01 (nesys) 握手補題を使って
22:01 (nesys) ……書きづらいｗ
22:01 (IPUSIRON) 直観的にいうと、
22:01 (IPUSIRON) ｎ人いたら、握手（＝辺）は2n個というのが握手の補題だっけ？
22:02 (IPUSIRON) 人間一人に2本の手があるから2回カウントだからね
22:02 (nesys) お互いいなきゃ成り立たないような話だった記がします
22:02 (Defolos) ひとつの握手に2つの手が関与するというものでしたね
22:02 (nesys) 辺が1つあれば、点が2つあるという
22:02 (IPUSIRON) 式96はf人いると考えてるぽい
22:03 (nesys) ｆｍ
22:03 (IPUSIRON) すると、ちょうどすべての人間の数と一致する
22:03 (IPUSIRON) から＝２ｍ
22:03 (IPUSIRON) Σのところの意味
22:04 (IPUSIRON) ラージFって何だろ…
22:04 (IPUSIRON) ラージというか太文字
22:04 (nesys) そこよく分からなかったんですよね…
22:04 (IPUSIRON) サッカーボールみたいな想像してるんだけど
22:04 (IPUSIRON) 六角形と五角形の組み合わせでできてるよね
22:04 (nesys) あ
22:05 (nesys) F(G)はグラフGに含まれる面の集合
22:05 (IPUSIRON) そうするとすべての点が2回触れてる
22:05 (nesys) らしいです
22:05 (IPUSIRON) 点じゃなくて辺
22:05 (IPUSIRON) その五角形とかひとつひとつを全部集めたのが、Σ（）だと思う
22:05 (IPUSIRON) mって辺の数だし
22:06 (nesys) すべての面の次数和ってことですね？
22:06 (IPUSIRON) そうだね
22:06 (nesys) 分かりやすい説明ありがとうございます
22:06 (IPUSIRON) これで96成り立つね
22:07 (nesys) はい
22:07 (nesys) そして、先ほどのオイラーの公式と連立させて、fを消去するように計算すると
22:07 (nesys) m<=3n-6が得られました
22:07 (nesys) よって（１）は成り立ちます
22:08 (nesys) 次、ｐ２２
22:08 (nesys) （２）の証明
22:08 (nesys) （１）と同様に考えます
22:09 (nesys) 三角形がない場合ですから、最少の面は4点からなる閉路であり
22:09 (nesys) ４＜＝ｄ（F）となります
22:09 (nesys) 先ほどと同様に、握手補題から
22:10 (nesys) 元資料の（９９）の式が得られ
22:10 (nesys) オイラーの公式と連立してｆを消去するように計算すると
22:10 (nesys) ｍ＜＝２nー４になり、（２）が成り立ちました
22:11 (nesys) p23
22:11 (nesys) 今回似たようなことを2度やってきたので汎用的にしてみましょう
22:11 (nesys) 最短の閉路長をｋと置き換えて
22:11 (nesys) 色々と計算すると
22:12 (nesys) m<=k(n-2)/(k-1)
22:12 (nesys) となります
22:12 (nesys) 色々な場面で使えるので、この式は便利です
22:12 (nesys) 次。p24
22:13 (nesys) 系13.6
22:13 (nesys) すべての単純平面グラフには次数5以下の点がある
22:13 (nesys) なんか。5以上のものしかないようなグラフが想像できないので、なんとなく正しいのだろうなと思いますね
22:14 (nesys) 証明してみましょう
22:14 (nesys) p25
22:14 (nesys) グラフGの任意の頂点ｖに対して
22:14 (nesys) ところで、このギリシャ文字なんて読むんですかｗ
22:15 (Defolos) でるた？
22:15 (nesys) おー
22:15 (IPUSIRON) デルタのこと？
22:15 (nesys) そうです。ありがとうございます
22:16 (nesys) δ＜＝deg(v)となり
22:16 (nesys) 先ほどの同様に握手補題で考えると
22:16 (IPUSIRON) (102)のところの左辺まちがってる？
22:16 (nesys) ｎ
22:17 (nesys) あ
22:17 (IPUSIRON) 元資料ではδnなんだけど
22:17 (nesys) ですね
22:17 (nesys) 書き間違えました
22:17 (IPUSIRON) n倍するんだよね
22:17 (nesys) はい
22:18 (nesys) δn<=��(v含V(G)) def(v)となり
22:18 (IPUSIRON) きごうで出るよ＜∈
22:18 (nesys) なんて変換されます？
22:19 (IPUSIRON) 「きごう」
22:19 (nesys) ああ。なるほど
22:19 (IPUSIRON) 大抵読みのわからないのは「きごう」で出る
22:19 (Defolos) ちなみに、ギリシャ文字は「ぎりしゃ」で出ますね
22:19 (nesys) へぇー
22:19 (nesys) まぁつづけて、＝2m<=2(3n-6)=6n-12となり
22:19 (nesys) 整理すると
22:20 (nesys) δ＜＝６−１２/ｎ　となり
22:21 (nesys) δ＜＝５であることが示されますね
22:21 (IPUSIRON) δは整数でなければならないから、6-（何か）は5以下ということなんだね
22:21 (IPUSIRON) 普通握手の補題は点と辺の関係だけど、ここでは面と辺の関係でみてるのがポイントなんだね
22:21 (IPUSIRON) さっきと同様に
22:21 (nesys) ああ。なるほど
22:21 (IPUSIRON) ここで確認だけど
22:21 (nesys) はい
22:21 (IPUSIRON) さっき直観的に完全グラフかつ平面的なのはK4までしかないとやったよね
22:22 (nesys) あぁ
22:22 (IPUSIRON) ちょうどこの系に当てはまる
22:22 (nesys) おお！
22:22 (nesys) なるほど
22:22 (IPUSIRON) K4は次数3だし
22:22 (IPUSIRON) 次数って1点につながる辺のことだったよね？
22:23 (nesys) はい
22:23 (IPUSIRON) それとも辺全体の数だっけ？
22:23 (nesys) ん
22:23 (IPUSIRON) ごめん。点に対して次数だったね。
22:23 (nesys) 1点につながるすべての辺の数ですえｎ
22:23 (IPUSIRON) 完全というところを取れば、次数が4,5でも平面的なやつがあるってことだね
22:23 (IPUSIRON) どんなグラフかはすぐにでないけど
22:24 (nesys) ｆｍ
22:24 (IPUSIRON) ということで圧倒的に平面なグラフは少ないってことだ
22:24 (nesys) ちなみに、先ほど出た便利な式は、例題8.1で用いることではっきりします
22:24 (nesys) のようですね
22:25 (IPUSIRON) 次どうぞ
22:25 (nesys) p26
22:25 (nesys) 交差数と厚さ
22:25 (nesys) グラフが平面的か否かは分かりましたが
22:26 (nesys) では、どの程度平面的にする作業は難しいのかを交差数と厚さという概念で表します
22:26 (nesys) p27
22:26 (nesys) 交差数とは
22:26 (nesys) グラフGを平面描写した際に生じる、辺の最少交差の数です
22:27 (nesys) cr(G)のようにして、グラフGの交差数が表されます
22:27 (nesys) つまり、平面グラフの交差数は0です
22:27 (nesys) p28
22:27 (nesys) 厚さとは
22:27 (nesys) いくつかの平面グラフを重ね合わせてグラフGを作るときに必要な平面グラフの数。だとありましたが
22:27 (nesys) これ理解できなかったんですよね…
22:28 (nesys) グラフを重ね合わせるって何ですか？
22:28 (IPUSIRON) うーん
22:29 (IPUSIRON) 非平面グラフを2次元平面に埋め込もうとすると
22:29 (IPUSIRON) 重なるよね
22:29 (IPUSIRON) 面が
22:29 (IPUSIRON) 線じゃなくて
22:29 (nesys) 面が？
22:29 (IPUSIRON) うん
22:29 (IPUSIRON) 折りたたむ必要ある
22:29 (IPUSIRON) 3次元の非平面グラフを強制的に平面に置くとしたら
22:29 (nesys) あー
22:30 (IPUSIRON) この非平面グラフを分解すれば2次元平面にもきちんと置けるでしょ
22:30 (nesys) でも、元に戻るのは難しくないですか？
22:30 (IPUSIRON) 平面グラフ＋平面グラフ＝非平面グラフみたいなかんじ
22:30 (nesys) あれ
22:30 (nesys) 点はどうなるんですか？
22:30 (nesys) 繋がるんですか？
22:31 (IPUSIRON) 共有する点とか辺はありうるよ
22:31 (nesys) そうしたら、グラフで描かれても、分からないですよね
22:31 (nesys) このグラフには何個の点があるのか。と
22:31 (IPUSIRON) 強制的に折りたたんだときに生じる面の数が厚さじゃないかな？
22:31 (nesys) グラフがイメージできないんですよね
22:32 (IPUSIRON) 非平面グラフひとつ思い浮かべると
22:32 (IPUSIRON) K5でいいよ
22:32 (nesys) ぉ？
22:32 (IPUSIRON) それを強制的に平面に置くと、
22:32 (IPUSIRON) 面が重なるところあるでしょ？
22:33 (IPUSIRON) 3次元の面を維持したまま置くことをイメージ
22:33 (nesys) ありますね
22:33 (IPUSIRON) その重なる面の数が暑さになるんじゃないかな？
22:33 (IPUSIRON) 厚さ
22:33 (nesys) じゃあK5の厚さは2ということですか？
22:33 (IPUSIRON) 多分
22:33 (nesys) ふーむ…
22:34 (nesys) 例えば点4の2つの平面グラフを重ねたグラフというのは
22:34 (IPUSIRON) この厚さの定義を忠実に考えた方がわかりやすいかもしれないけど
22:34 (nesys) 全くぴったりに重ねた場合
22:34 (nesys) 点数とかどうなるんですかね
22:34 (IPUSIRON) このときは単に平面グラフと確定しているものを重ねてる（点と線をいくつか共有させる）
22:34 (IPUSIRON) ピッタリ重なると
22:34 (IPUSIRON) ４のまま
22:35 (nesys) へぇー
22:35 (nesys) 厚さはどうなります？
22:35 (IPUSIRON) 一個ずらすと５じゃない？
22:35 (IPUSIRON) 厚さは２になるね
22:35 (nesys) なるほど
22:35 (IPUSIRON) 構成する平面グラフの数だから
22:35 (IPUSIRON) グラフGって別に平面グラフとか非平面とかいってないからね
22:35 (nesys) はい
22:36 (IPUSIRON) K4はK2を3つ使えば作れるでしょ
22:36 (IPUSIRON) みすK3とK2を２つ
22:36 (nesys) ああ
22:36 (IPUSIRON) いやK3を３つだ（笑）
22:36 (nesys) ん？
22:36 (IPUSIRON) K4は三角形３つで構成される
22:36 (IPUSIRON) 三角形はもちろん平面グラフ
22:37 (nesys) あれ
22:37 (nesys) K3　２つと　K2　１つじゃないんですか？
22:37 (IPUSIRON) 構成方法はひとつじゃないけど
22:37 (IPUSIRON) いやぐるっていうやつは辺3つあるよ
22:38 (nesys) あれ？
22:38 (IPUSIRON) ああ
22:38 (IPUSIRON) 対角線を通過してるのを考えてるのかな
22:38 (IPUSIRON) 極端にいえばK3を２つだけでも構成できる
22:38 (IPUSIRON) 点を2つだけ共有させる（辺は共有させない）
22:39 (nesys) うーん
22:39 (nesys) ああ
22:39 (nesys) あれ
22:39 (nesys) でも辺を共有させなければ
22:40 (IPUSIRON) 17ページの図を使うと
22:40 (nesys) 多重辺になりますよ？
22:40 (IPUSIRON) いやなることもあるけどうまくやればならないよ
22:40 (nesys) うまくやれば…
22:40 (IPUSIRON) あごめん
22:41 (nesys) ｎ
22:41 (IPUSIRON) K3を2つだけではだめだね
22:41 (IPUSIRON) 図間違えてた
22:41 (nesys) あ
22:41 (nesys) K33つというのがわかったかもしれません
22:41 (IPUSIRON) K3を3つとかでいける
22:42 (nesys) K3　２つ　K2　１つでもいけますよね？
22:42 (IPUSIRON) 四角の中に2つの△、ぐるっという曲線と2辺で凹んだ△ひとつだからね
22:42 (nesys) はい
22:43 (IPUSIRON) K3　２つ　K2　１つでもいける
22:43 (IPUSIRON) K2は単なる直線だからね
22:43 (nesys) 極端にいえば、K2　6つでもいけるわけですかｗ
22:43 (IPUSIRON) ｙ
22:43 (nesys) なるほどー
22:43 (nesys) 理解しました
22:43 (IPUSIRON) 多分定理とかでは最小値とか最大値とかを評価するんでしょう
22:44 (nesys) ｆｍ
22:44 (IPUSIRON) K2使えばなんでも構成できるからあなり最大値は意味なさそうだし
22:44 (IPUSIRON) あまり
22:44 (nesys) ですね
22:45 (nesys) まぁグラフGの厚さはｔ（G)によって表わされます
22:45 (nesys) thicknessのtですね
22:45 (nesys) 先ほどのcr(G)はcrossingのcrかな。と
22:45 (nesys) p29
22:45 (nesys) 途中まで行って分からなくなりました
22:46 (nesys) 完全二部グラフを最も交差の少ない形で配置すると
22:46 (nesys) この図のようになります
22:46 (nesys) 原点位置からｙ軸方向、−ｘ軸方向へとそれぞれラベリングします
22:47 (nesys) ここまではいいんですが
22:47 (nesys) 元資料のq1などがどこのことを指しているのかが分かりませんでした
22:47 (IPUSIRON) 証明の式がすごい。目が痛くなりそうだ
22:47 (nesys) ですねｗ
22:47 (IPUSIRON) q1というのは
22:48 (IPUSIRON) 105式の1行上のところに定義されてるよ
22:48 (IPUSIRON) v_s/2-1と〜〜を結ぶ線分の交点
22:49 (IPUSIRON) 図118のy軸上の白点v_s/2に着目
22:49 (IPUSIRON) 一番上の白点ね
22:49 (nesys) んーはい
22:49 (nesys) はい
22:49 (IPUSIRON) これとX軸の一番左のクロテン
22:50 (IPUSIRON) の線の交点は0か
22:50 (nesys) はい
22:50 (IPUSIRON) 次に2番目の黒点と白点の直線の交点は
22:50 (nesys) 2
22:50 (IPUSIRON) s/2-1個？
22:50 (nesys) ん？
22:51 (nesys) 白点全部ですか？
22:51 (IPUSIRON) かなあ
22:51 (IPUSIRON) その数値出てきた理由は
22:51 (IPUSIRON) 一番左のクロテンと、一番上以外のシロテンをむすぶ線がちょうど交差してるとおもったから
22:52 (nesys) あ。資料p29のラベル間違ってますね（白点のほう
22:53 (IPUSIRON) 線を境界線として左右にそれぞれ点が存在すれば交差を意味するからね
22:53 (IPUSIRON) 間違ってるのかな？
22:53 (nesys) rじゃなくてsです
22:54 (IPUSIRON) 式でrでてるから？
22:54 (IPUSIRON) そもそも元資料のq1の定義が、同じこと重複してるけどね
22:54 (nesys) それにしても、この解答、説明の省略が多くてよく分からないです…
22:54 (IPUSIRON) 「すると」以降
22:55 (IPUSIRON) まあカウントはこのようにしてやっていくと、q1はも止まる
22:55 (IPUSIRON) 元丸
22:55 (IPUSIRON) 求まる
22:55 (nesys) q1はどこのくくりのことを指しているんですかね？
22:55 (IPUSIRON) 後は全部のq出して、足しあわせて、式の展開
22:56 (IPUSIRON) q1＝v_s/2とw1,…,w_r/2を結ぶ線分の交点の数　だよね
22:56 (IPUSIRON) 105の式の上の行だけど
22:57 (nesys) はい
22:57 (IPUSIRON) そのq1の説明だけど、そこから上の行の「すると」のところの間が
22:57 (IPUSIRON) 同じことをそのまま書いてる（誤植）ってこと
22:58 (IPUSIRON) 105の式の上2行のすると以降を読むと、わかるよ
22:58 (IPUSIRON) ああ
22:58 (IPUSIRON) みす
22:58 (IPUSIRON) v_s/2だった
22:58 (IPUSIRON) から問題なかった　ごめん
22:58 (nesys) ん
22:59 (nesys) えっと
22:59 (nesys) p1は
22:59 (nesys) 一番上の白玉と1つしたの白玉の2つと
22:59 (nesys) 黒玉すべてに
22:59 (nesys) 辺がひかれた交差の総数ですかね？
23:00 (IPUSIRON) そうだね
23:00 (nesys) なるほど
23:00 (IPUSIRON) 白点は２つで考えてるんだね
23:01 (IPUSIRON) 白点2つとクロテンすべてのグラフの交差数＝p1ということだね
23:01 (nesys) q2は…
23:01 (IPUSIRON) 後は白点ずらして
23:01 (nesys) それ＋3つめの白玉？
23:01 (nesys) ずらしてますか？
23:01 (IPUSIRON) 2個目と3個目の白点だね
23:02 (nesys) でも、同様にして、vs/2とあるんですけど
23:02 (IPUSIRON) ああ
23:03 (IPUSIRON) 3つだね
23:03 (IPUSIRON) 白点は
23:03 (nesys) ｆｍ
23:04 (nesys) でもこれ結局、q s/2-1で、白玉すべてと黒玉すべての交差を出すと思うんですが
23:04 (IPUSIRON) そうだね
23:04 (nesys) なんでq1なども足す必要あるんですかね？
23:04 (nesys) 重複するじゃないですか？
23:04 (IPUSIRON) その通りです
23:05 (IPUSIRON) 謎（笑）
23:05 (nesys) あぅ
23:05 (IPUSIRON) ということだとこの証明怪しいから飛ばそう
23:05 (nesys) おｋｗ
23:05 (nesys) ではp31
23:06 (nesys) 厚さの意味が分からなかったので、例題8.3と8.4は飛ばしました
23:06 (nesys) 後でやっておきます
23:06 (IPUSIRON) はい
23:06 (nesys) とりあえずガウス記号について
23:06 (nesys) [x]と記述されているのはガウス記号です
23:06 (nesys) プログラミングでいうfloor関数です
23:06 (nesys) 例であるように、引数？以下の最大値の整数を返します
23:07 (IPUSIRON) 小数点切り捨てのことだね（正の数では）
23:07 (nesys) そうですね
23:07 (IPUSIRON) ちなみに、上かっこみたいなやつは
23:07 (IPUSIRON) ceiling functionで切り上げね
23:07 (nesys) うえカッコ？
23:07 (IPUSIRON) 「○¬というガウス記号もあるでしょ
23:08 (IPUSIRON) 例えば137式
23:08 (nesys) ああ！
23:08 (nesys) 気づきませんでした
23:08 (nesys) これ、下にカッコ閉じる？がなかったりするんですね
23:08 (nesys) てっきり。[]なのかと思いました
23:09 (IPUSIRON) 下括弧はfloor functionだよ
23:09 (Defolos) 私も気づきませんでした
23:09 (IPUSIRON) ガウス記号の場合は普通floor
23:09 (nesys) なるほど
23:09 (IPUSIRON) 厳密に書くときは下とか上とか使い分けて書きます
23:09 (nesys) このカッコ、変換ででます？
23:10 (IPUSIRON) 多分出せない（笑）
23:10 (nesys) おｋｗ
23:10 (IPUSIRON) 出したとしても変な形だよ
23:10 (IPUSIRON) ¬　きごう
23:10 (nesys) ああ。なるほど
23:10 (nesys) では、例題8.5に移ります
23:10 (nesys) p33
23:10 (IPUSIRON) じゃ��x¬とかいたらなんだかわかる？
23:11 (nesys) ｎ
23:11 (IPUSIRON) 下括弧と上括弧同時に使うの
23:11 (nesys) そんな書き方もできるんですね・・・
23:11 (nesys) 何もしない？ｗ
23:11 (IPUSIRON) これはxの四捨五入
23:11 (nesys) おお
23:11 (nesys) なるほど！
23:11 (IPUSIRON) 覚えておいても多分使う場面ほとんどないとおもう（笑）
23:11 (nesys) ぁｗ
23:11 (IPUSIRON) 雑学としてどうぞ
23:12 (nesys) 関数名覚えたほうが実用性ありますねｗ
23:12 (IPUSIRON) 今まで数学で使ったことないよ。使っても多分知ってる人少ないから
23:12 (nesys) へぇー
23:12 (Defolos) なにそれ？誤字？っていわれるわけですね＾＾；
23:12 (carbon0) その記号は初めて見たｗ
23:13 (nesys) では、例題8.5（1）行きますね
23:13 (IPUSIRON) はい
23:13 (nesys) まず閉路行列について
23:13 (nesys) 前回やりましたが
23:13 (nesys) とりあえず実際見たほうが早いです
23:13 (nesys) p34
23:14 (nesys) K4を書いて、それの閉路行列は以下のようになります
23:14 (nesys) それぞれの閉路の辺が重なる数を表していますね
23:14 (nesys) 向きが関係して、逆向きの場合はー1になります
23:15 (nesys) p35
23:15 (nesys) この閉路行列を使って計算しましょう
23:15 (nesys) だいたい行列の計算でばーっとやると16になります
23:15 (nesys) 16個の全域木があることが分かります
23:16 (nesys) （2）　p36
23:16 (nesys) ピータースングラフの平面性についてです
23:16 (nesys) まずこの奇怪なグラフの形を思い出しましょう
23:16 (nesys) この図のようなやつです
23:16 (nesys) p37
23:17 (nesys) それぞれの点数、辺数、内周とを数えましょう
23:17 (nesys) n=10, m=15, k=5でした
23:17 (nesys) 内周とはグラフGの最短の閉路長のことです
23:18 (nesys) 先ほど出したあの便利な式に代入してみましょう
23:18 (nesys) p38
23:18 (nesys) 計算すると答えが13.333．。。
23:18 (nesys) 15以上ではないため
23:18 (nesys) ピータースングラフは平面的ではありません
23:19 (nesys) 問（３）（１）　p39
23:19 (nesys) さきほどの系の証明の続きみたいな問題ですが
23:19 (nesys) ３，４，５角形がない場合
23:20 (nesys) 内周kは6となります
23:20 (nesys) 便利な式に入れましょう
23:20 (nesys) m<=3/2(n-2)となります
23:20 (nesys) 問（３）（２）　p40
23:21 (nesys) K角形までない場合
23:21 (nesys) 内周はK−１になります
23:21 (nesys) 便利な式に入れて同様に計算すると
23:22 (nesys) m<=((k+1)/(k-1))(n-2)になります
23:22 (nesys) 問（3）（3）　p41
23:22 (nesys) K→∞の極限をとった場合です
23:23 (nesys) しかし、Kは飽くまでも閉路長であるため
23:23 (nesys) 点数を超えることはできません
23:23 (nesys) K<=nとなるわけで
23:23 (nesys) この場合はK=nという条件下で考えましょう
23:23 (nesys) （Kの最大値＝ｎ
23:24 (nesys) （２）で出された式に代入しましょう
23:24 (nesys) ばーっと計算すると、m<=nとなります
23:24 (nesys) p42
23:24 (nesys) つまり、K角形まで無いということは、グラフGはｎ角形1個からなるグラフである。ということです
23:25 (nesys) ｎ角形にしろ、無限角形に変わりありませんがね
23:25 (nesys) 例題8.6（１）　p43
23:25 (nesys) ここの言葉の意味がよく分かりませんでした
23:25 (nesys) 「平面グラフにおいては隣り合う5つ以下の隣接面しかもたない面が存在する」ようなグラフ
23:26 (nesys) 以下の図のようなグラフらしいですが、何でなんですかね？
23:27 (IPUSIRON) 地図上のどの国も５つ以下としか接触していないということだね
23:27 (Defolos) これって地図の彩色問題かな？
23:27 (IPUSIRON) 地図の4色問題の一歩手前の5色問題だね
23:27 (nesys) まずここでは地図と言っているんですが
23:27 (Defolos) なるほど
23:27 (nesys) 地図の定義が分からないです
23:27 (IPUSIRON) 5色問題はこんなに簡単に出来て、4色問題はあんなに何百年もかかったわけだ
23:28 (IPUSIRON) 地図というのは図121のように
23:28 (nesys) 彩色問題については次の章でやるみたいです
23:28 (IPUSIRON) 3叉だけで考えるってこと
23:28 (nesys) へぇ？
23:28 (nesys) どこにそう書いているんですかね？
23:28 (IPUSIRON) 図121のキャプション
23:29 (IPUSIRON) いやミス
23:29 (IPUSIRON) 以上って書いてあるね
23:29 (IPUSIRON) 定義わからないから飛ばそうか。次の章でやるならそこで定義でそうだし
23:29 (nesys) ですね
23:30 (nesys) まぁ3辺以上のことを言うらしいので
23:30 (nesys) p44
23:30 (nesys) グラフGには点がｎ個あり
23:30 (nesys) すべての辺数は3×ｎ以上になりそうですが
23:30 (IPUSIRON) 今例題8.6の(2)?
23:31 (nesys) 辺の両端には必ず点が2つあるため
23:31 (nesys) それらの分を減らして
23:31 (nesys) m>=3n/2となります
23:31 (nesys) 整理すると
23:31 (nesys) n<=2m/3　が成り立つことが示されるわけです
23:31 (nesys) （２）　p45
23:31 (nesys) 「どの面も少なくとも6つの隣接面に囲まれている」ようなグラフ
23:32 (IPUSIRON) 定義わからないから飛ばすってことになんなかったっけ？
23:32 (nesys) ん？
23:32 (nesys) あれ。
23:32 (nesys) 問題全体飛ばすんですか？
23:32 (IPUSIRON) 定義わらかないと問題解けないはずだよ（笑）
23:32 (nesys) まぁそうですねｗ
23:33 (IPUSIRON) 解いててもなぞってるだけでわかったようでわからないってことだから、問題も飛ばそう
23:33 (nesys) 了解です
23:33 (nesys) ではそろそろ終わります
23:33 (nesys) p48
23:33 (nesys) 演習問題を各自でやってみましょう
23:33 (nesys) 便利な式を使えばできそうです
23:33 (nesys) （楽に
23:33 (nesys) p49
23:34 (nesys) ありがとうございました！
23:34 (nesys) 終わりです
23:34 (Defolos) おつかれさまでしたー
23:34 (IPUSIRON) お疲れ様でした
23:34 (carbon0) お疲れ様でした