21:00 (IPUSIRON) じゃ始めます。
21:00 *Defolos join #akademeia (~anonymous@eaoska124254.adsl.ppp.infoweb.ne.jp)
21:00 (IPUSIRON) こんばんは
21:00 (Defolos) こんばんはー
21:00 (kirfth_) こんばんは。
21:00 (IPUSIRON) 今始めるところでした。では始めます（笑）
21:00 (Defolos) おねがいします
21:01 (IPUSIRON) では資料のPDF開いてください
21:01 (IPUSIRON) 今日は双対グラフと彩色数について発表します
21:01 (Defolos) はい
21:01 (IPUSIRON) スライド２に無限グラフと書いてありますが、これは直しておきます
21:01 (IPUSIRON) スライド3
21:02 (IPUSIRON) まず双対グラフとは、与えられた平面グラフに対して、作られるグラフの一種です
21:02 (IPUSIRON) 平面グラフというのは前回やったものですが、簡単に述べると
21:03 (IPUSIRON) 平面上で辺が交差しないようなグラフのことです
21:03 (IPUSIRON) 与えられたグラフに対応して双対グラフというものが作れるのですが、その作り方はスライド4に書いてあります。
21:04 (IPUSIRON) 作り方の前に、双対グラフで考えると何がうれしいのかということについて述べると、カットセット問題や彩色問題に応用できるということが挙げられます
21:04 (IPUSIRON) カットセット問題や彩色問題は後ほどのスライドでやりますが、ネットワークの理論などにもかかわってきます
21:04 (IPUSIRON) スライド4
21:04 (Defolos) 双対グラフはどんなグラフでも必ずかけるんでしょうか？
21:05 (IPUSIRON) 書けます
21:05 (IPUSIRON) 与えられたグラフに対して
21:05 (IPUSIRON) 必ずひとつの双対グラフが書けます
21:05 (Defolos) なるほど
21:05 (Defolos) 了解しました
21:05 (IPUSIRON) その書き方はスライド4に書いてあります
21:06 (IPUSIRON) 図ではグラフGという実線のグラフがあります
21:06 (IPUSIRON) そのとき、それぞれの内側の面に1つの白点を打ちます
21:06 (IPUSIRON) また、外部もある種面なので、1つ打ちます
21:07 (IPUSIRON) つまりGの場合は、内側に3つ、外部に1つの点が打たれます
21:07 (IPUSIRON) これらの4つの点が双対グラフの点となります。
21:07 (IPUSIRON) 次に、グラフなので辺が引かれるわけですがこれはつぎのように引かれます
21:07 (IPUSIRON) Gの各辺と1回だけ交わるようにして、白点同士を結びます
21:08 (IPUSIRON) これが図の青の線です
21:08 (Defolos) ということは、木グラフだと点がひとつの、辺の数だけループを含むグラフになるのですね
21:08 (IPUSIRON) 青線と白点で構成されるグラフのことをGの双対グラフといい、G^*と表記することにします
21:08 (IPUSIRON) そうです
21:08 (Defolos) なるほろ
21:08 (IPUSIRON) 単に枝みたいなのがちょろっと出ていたとしても
21:08 (IPUSIRON) それと交わるようにしなければなりません
21:09 (Defolos) わかりましたー
21:09 (IPUSIRON) 元資料の図124だと辺beがそれですね
21:09 (IPUSIRON) それで次に例題8.7に入ります
21:10 (IPUSIRON) 完全グラフK4の双対グラフは、完全グラフK4であることを示せという問題です
21:10 (IPUSIRON) 問題を解くアプローチとしては、具体的なK4が与えられているので、その双対グラフを書いて、K4と比較して同形かどうか見ればよいことになります
21:11 (IPUSIRON) 完全グラフの復習ですが、完全グラフとはどの異なる2頂点も隣接している単純グラフのことです
21:11 (IPUSIRON) スライド5の右図が4つの点をもつ完全グラフです
21:11 (IPUSIRON) このK4の双対グラフですが、それはスライド6の上のようになります。
21:11 (Defolos) k4はこの形以外なかったですよね、確か・・・
21:11 (IPUSIRON) ちなみに質問あれば随時どうぞ
21:12 (IPUSIRON) ないですね＜K4のグラフ
21:12 (IPUSIRON) 基本的に完全グラフも一意的です
21:12 (Defolos) なるほろ
21:12 (IPUSIRON) 定義的に全部点と点が繋がっているグラフですから
21:13 (IPUSIRON) K4の双対グラフですが、内側の3つの面にそれぞれ点をうって、外側に1点うちます
21:14 (IPUSIRON) 後は、先ほどの規則の通り辺を引くと、スライド6の上図の青線になります
21:14 (Defolos) スライド６の最後の□は何なんですか？
21:14 (IPUSIRON) この双対グラフの見た目をかえれば、下図のようになって、最初のK4と一致していることがわかります
21:14 (IPUSIRON) □は証明終わりというマークです
21:15 (Defolos) あ、そんなマークがあるのですか
21:15 (IPUSIRON) (Q.E.D.)とかも見ますが、□もよく使われますよ
21:15 (Defolos) なるほど、了解しました
21:15 (IPUSIRON) ここまでで質問などありませんか？
21:15 (IPUSIRON) 素朴な疑問でも結構です
21:15 (Defolos) 大丈夫です〜。たぶん
21:15 (kirfth_) 今のところは特にないです。
21:16 (IPUSIRON) それではスライド7に入ります
21:16 (IPUSIRON) 補題15.1です
21:16 (IPUSIRON) 平面連結グラフGの点をn、辺をm、面をfと記号で表すことにします
21:17 (IPUSIRON) また、同様にその双対グラフG^*の点をn^*、辺をm^*、面をf^*と記号で表すことにします
21:18 (IPUSIRON) これら6つの記号たちはn^*=m、m^*=m、f^*=nという関係式を満たします
21:18 (IPUSIRON) これを証明しろという問題です
21:18 (IPUSIRON) まず、証明の前に具体例で確認してみました
21:18 (IPUSIRON) 先ほどと同じグラフGと双対グラフG^*を考えました
21:19 (IPUSIRON) グラフGとG^*の点・辺・面をスライド8の左側に列挙しました
21:19 (IPUSIRON) ここから見ると、辺は共通の７
21:19 (IPUSIRON) 点は双対グラフの面と一致していて
21:19 (IPUSIRON) 面は双対グラフの点と一致していることがわかります
21:19 (IPUSIRON) 少なくとも、この例ではこの補題15.1が正しいことがわかります
21:20 (IPUSIRON) それで証明ですが、方針としてはオイラーの公式が使えそうです
21:20 (IPUSIRON) また、双対グラフの定義（作り方の手順）が参考になるはずです
21:21 (IPUSIRON) このことに留意して証明を付けます
21:21 (IPUSIRON) まず、双対グラフの作り方として、点の打ちかたをやりましたが、双対グラフの点は元のグラフの面に対応していました
21:21 (IPUSIRON) このことから自動的にn^*=fが成り立ちます。
21:22 (IPUSIRON) また、辺の描き方ですが、元のグラフの各辺に交差するようにしていたので、数は同じです
21:22 (IPUSIRON) つまり、m=m^*もいえます
21:23 (IPUSIRON) 最後に、示したいのは「f^*=n」ですが
21:23 (IPUSIRON) まずグラフGに関してオイラーの公式を考えるとn-m+f=2が成り立ちます。
21:23 (IPUSIRON) またG^*に対しても成り立ち、n^* - m^* + f^* =2が成り立ちます
21:24 (IPUSIRON) このオイラーの公式はどんなグラフにも成り立つものですから
21:24 (IPUSIRON) この2つのオイラーの公式とすでに得られた結果から、最後のf^*=mもいえます
21:24 (IPUSIRON) これで証明終わりです
21:24 (Defolos) オイラーの公式っていろんなところで使えますねぇ
21:24 (IPUSIRON) ですね
21:25 (IPUSIRON) どのグラフであっても、この単純な式で表すことができるというのはすごいですね
21:25 (IPUSIRON) 先ほど双対グラフは一意的に決まるといいましたが
21:26 (IPUSIRON) この補題からもそれが示唆されます
21:26 (Defolos) ほむ
21:26 (IPUSIRON) つまり、Gが決定したら、その具体的なGに対応してG^*の辺・点・面が決まる。
21:26 (IPUSIRON) よって、G^*も決定するということになります
21:26 (Defolos) あー。なるほど
21:26 (kirfth_) なるほど。
21:27 (IPUSIRON) ある種双対グラフと普通のグラフは表裏一体という感じです
21:27 (IPUSIRON) ということで双対グラフの双対グラフというのも自然に考えられます
21:27 (IPUSIRON) 直観的に双対グラフの双対グラフは元に戻ると思われます。それが美しいですから
21:28 (IPUSIRON) でも実はそうではなく、
21:28 (IPUSIRON) あるグラフでは元に戻るし、あるグラフでは元に戻りません
21:28 (IPUSIRON) その定理がスライド10です
21:29 (IPUSIRON) ポイントはGが連結平面でないとダメということです
21:29 (IPUSIRON) 連結というのは全部の辺がくっついているということです
21:30 (IPUSIRON) またこれに対して非連結というのがありますが、それはくっついていないグラフ同士をまとめて見たようなグラフです
21:30 (IPUSIRON) ここまで大丈夫ですか？
21:30 (kirfth_) 多分大丈夫です。
21:31 (Defolos) ＯＫです
21:31 (IPUSIRON) ではスライド11に入ります
21:31 (IPUSIRON) 定理15.3
21:31 (IPUSIRON) Gとその双対グラフG^*があったとする。このときに、次が成り立ちます。
21:32 (IPUSIRON) Gの辺を含む変集合が閉路　⇔　辺集合がG^*においてカットセットである
21:32 (IPUSIRON) ちなみにカットセットというのは、英単語で考えるとわかりやすく
21:33 (IPUSIRON) cutするようなset（集合）のことです
21:33 (IPUSIRON) どんな集合かというと辺の集合です
21:33 (IPUSIRON) cutというのは元々連結していたグラフを非連結にしてしまうことです
21:34 (IPUSIRON) つまり、1本で削除でcutできることもあれば、3本まとめて辺を削除しないとcutできないこともあります
21:34 (IPUSIRON) 例えば、スライド8の図では
21:34 (IPUSIRON) 四角の上に△になってますよね
21:35 (IPUSIRON) その屋根である2本の辺を取り除けば、四角と屋根の天辺の点だけが残ります
21:35 (IPUSIRON) つまりこの2本の集合はカットセットになります
21:35 (IPUSIRON) 点もある意味グラフですから
21:35 (IPUSIRON) 定理の証明の前に具体的に見ていきます
21:35 (IPUSIRON) スライド12
21:36 (IPUSIRON) まず⇒から確認します
21:36 (IPUSIRON) スライド8とかで登場したGとG^*をそのまま使います
21:37 (IPUSIRON) このとき、□の部分（中央図の赤）が閉路になってますから、これを考えます
21:37 (IPUSIRON) つまり4本の辺で構成されていますね
21:38 (IPUSIRON) この4本に対応するG^*の辺を、G^*から取り除くとします（下図の赤線）
21:38 (IPUSIRON) 4本あるので、G^*から4本除去です
21:39 (IPUSIRON) すると、元々のG^*は外側のぐるっとした青のところと、内側の青線の2つに分断されました
21:39 (IPUSIRON) つまり、非連結になってます
21:39 (IPUSIRON) 納得できましたか？
21:40 (Defolos) なんとなく納得できた気がします＾＾；
21:40 (IPUSIRON) 具体例でわからないと証明ももちろんわからないはずなので
21:40 (IPUSIRON) 極端にいえば証明よりも具体例でわかるより重要かも
21:41 (IPUSIRON) 一言でいうと、Gの閉路を考え、その閉路を構成する辺に対応するG^*の辺を、G^*から取り除くと非連結になってしまった　ということです
21:41 (IPUSIRON) 対応する＝交差する　です
21:41 (kirfth_) なるほど。
21:42 (IPUSIRON) 次に、逆の←を確認します
21:42 (IPUSIRON) G^*のカットセットとなるものを適当に考えます
21:42 (IPUSIRON) スライド13では中央図の赤の4つの線ですね
21:42 (IPUSIRON) あくまでこれは一例です
21:43 (IPUSIRON) これらG^*のカットセット（辺の集合）に含まれる辺に対応するGの辺を今度考えます
21:43 (IPUSIRON) それが下図の緑の4つの線です
21:43 (IPUSIRON) 赤と緑が交差しているのは対応しているという意味です
21:44 (IPUSIRON) 赤と交差するGの線を緑に塗ったというイメージです
21:44 (IPUSIRON) この緑の線はよくみると、ぐるっと閉路になっていますよね
21:44 (Defolos) こっちのほうはイメージがしやすいですね
21:44 (IPUSIRON) まとめると、Gの閉路とG^*のカットセットは対応しているってことですね
21:45 (IPUSIRON) これがこの定理です
21:45 (IPUSIRON) 証明ですが、今やった具体例を一般的に書き下しただけです
21:46 (IPUSIRON) ⇒を示してみると
21:46 (IPUSIRON) まずGの閉路を任意に選びます
21:46 (IPUSIRON) この閉路Cには面が1つ以上はありますよね
21:46 (IPUSIRON) 1つあれば閉路として十分ですし、別に2つ以上あってもよい
21:47 (IPUSIRON) 実は閉路の中に面が1つだけならば
21:47 (IPUSIRON) 双対グラフは1点と適当なグラフに分割されます
21:47 (Defolos) 閉路の外は面とは考えないのですか？
21:47 (IPUSIRON) ここでは考えていません。
21:47 (IPUSIRON) あくまで内側というところが重要です
21:47 (Defolos) わかりましたー
21:48 (IPUSIRON) もちろん外にも面はありますが、内側にもあるってことが重要という意味です
21:48 (IPUSIRON) ここで気付くかもしれませんが、内側と外側の2つあるから
21:48 (IPUSIRON) 結局そこで分離されるんです
21:49 (IPUSIRON) 閉路Cの中に2つの面があれば、分離後のG^*は内側に2つの点とそれを結ぶ線、外側に適当なグラフがあります
21:50 (IPUSIRON) 閉路と交差しているG^*の辺は除去されるので、内側と外側に分離されるわけです
21:50 (IPUSIRON) これで証明終わりました。
21:50 (IPUSIRON) 逆も同様にやればOKです
21:50 (Defolos) ほむ
21:51 (IPUSIRON) この定理15.3から系15.4がいえます
21:51 (IPUSIRON) これは単にGとG^*を入れ替えただけです
21:52 (IPUSIRON) ここまで大丈夫ですか？
21:52 (Defolos) はい
21:52 (kirfth_) 多分、大丈夫です
21:52 (IPUSIRON) では例題8.8に入ります
21:52 (IPUSIRON) (1)車輪の双対は車輪であることを示せという問題です
21:53 (IPUSIRON) まずn個の点を持つ車輪というのは、n-1個の点を持つ閉路に、1つの点からそれらのn-1個の点を結んだような点のことです
21:54 (IPUSIRON) スライド16の右図の実線は車輪W5です
21:54 (IPUSIRON) これ見れば車輪の定義は明らかだと思います。点が増えれば単に輪の部分の点が増えるだけですね
21:54 (IPUSIRON) 具体的にW5の双対グラフを考えてみると、青色になっていて
21:54 (IPUSIRON) これをよくみてみるとW5と一致しています
21:55 (Defolos) 外の点をぐにゃっと真ん中にもってくるわけですね
21:55 (IPUSIRON) 下側の１点を中央にもってくれば、元のW5の逆向きですから
21:55 (IPUSIRON) はい
21:55 (IPUSIRON) 証明では閉路ということに注意して考えていきます
21:56 (IPUSIRON) Wnの面は外側の１つと内側のn-1個になります
21:56 (IPUSIRON) まず内側のn-1個の面それぞれに白点を打ちます。そして、線をひくと、n-1個の点を持つ閉路C_n-1になります
21:57 (IPUSIRON) 後、外側の１点を考えないとダメなので、それを打って、C_n-1と結ぶと、車輪Wnの定義そのものですよね
21:57 (IPUSIRON) よって、車輪の双対は車輪になります
21:58 (IPUSIRON) 次に(2)
21:58 (IPUSIRON) 平面グラフGが非連結ならば、G^**（G）は
21:58 (IPUSIRON) みす
21:58 (IPUSIRON) Gの双対の双対は同形にならないことを例で示せという問題です
21:58 (IPUSIRON) スライド10で出てきた定理15.2に関連した問題です
21:59 (IPUSIRON) 定理の条件としてGは連結平面じゃないと、元に戻らないと主張していました
21:59 (IPUSIRON) なので条件を緩めたら、元に戻らないはずだが、その例を答えよといっているわけです
21:59 (IPUSIRON) まず具体的にスライド19の上図の実線のような非連結グラフを考えます
22:00 (IPUSIRON) □と△をまとめてひとつのグラフなわけです
22:00 (IPUSIRON) そして、Gの双対グラフを書くと上図の青線と白点のグラフになります
22:00 (IPUSIRON) さらに、その双対グラフの双対グラフを描いたのが下図です
22:01 (IPUSIRON) すると、上の実線と下の実線のグラフは明らかに異なります
22:01 (IPUSIRON) そもそも最初は非連結だったのに、最後は連結になってしまっています
22:01 (IPUSIRON) これが同形であるわけがないです。
22:01 (Defolos) そもそも双対グラフにすると連結グラフになってしまうような気がするのですが
22:02 (IPUSIRON) そこがポイントですね
22:02 (Defolos) これだと明らかに非連結グラフではないですよね＾＾；
22:02 (IPUSIRON) そのポイントによって、一般的に定理が得られますね
22:02 (IPUSIRON) はい
22:03 (IPUSIRON) 次に(3)です
22:03 (IPUSIRON) Gが連結平面グラフであるとき、Gの全域木はG^*のある全域木の補グラフに対応することの例を示せ
22:03 (IPUSIRON) 複雑でぱっとみわけわかりません
22:03 (Defolos) はい＾＾；
22:03 (IPUSIRON) なのでまずそれぞれの言葉の定義をしっかり把握していきます
22:04 (IPUSIRON) まず全域木とは、グラフの点をすべて含むような部分木のことです
22:04 (IPUSIRON) 直観的にいえば
22:04 (IPUSIRON) Gから辺をどんどん除去していけば、いつかは木になりますよね（ただし、全部つながっているとする）
22:05 (IPUSIRON) それが全域木です
22:05 (IPUSIRON) そして、Gno
22:06 (IPUSIRON) Gの補グラフというのは
22:06 (IPUSIRON) 頂点はそのまま、辺があるところは除去、辺がないところは追加として考えたグラフのことです
22:06 (IPUSIRON) イメージとしては、G-G1がG1の補グラフといったところです
22:07 (IPUSIRON) 反転するというべきか
22:07 (IPUSIRON) ここまでの定義は大丈夫ですか？
22:07 (Defolos) はい
22:07 (kirfth_) 大丈夫です
22:08 (IPUSIRON) それではスライド21
22:08 (IPUSIRON) 上図のようなGと双対グラフG^*を考えます
22:08 (IPUSIRON) このとき、Gの全域木として中央図のG1を考えます
22:09 (IPUSIRON) このG1は全部の点（５点）を取ってますよね。
22:09 (IPUSIRON) さらに木になってますから定義は満たしています
22:10 (IPUSIRON) また、双対グラフG^*はGから自動的に生成されるので、そのG^*でも全域木を考えます
22:10 (IPUSIRON) その全域木G2を下図の赤色です
22:10 (IPUSIRON) そうすると、G2の補グラフとは緑のグラフになります
22:11 (IPUSIRON) この緑のグラフとG1は実は一致しているのです
22:11 (IPUSIRON) 何がいいたいかというと
22:11 (IPUSIRON) Gの全域木と、G^*の全域木の補グラフが同形になることがある
22:12 (IPUSIRON) なることがあるでは弱すぎますね。必ずなるということです。
22:12 (Defolos) ほむ
22:12 (IPUSIRON) ただし、うまくG^*の全域木をとったときだけですが
22:13 (IPUSIRON) 少なくともうまくG^*の全域木を考えれば、その補グラフは、元のグラフGの全域木と一致という意味です
22:14 (IPUSIRON) この(3)はGの全域木とG^*の全域木の関係を意味しています。
22:14 (IPUSIRON) 全域木が決まればその補グラフは確定しますからね
22:15 (IPUSIRON) 抽象的双対については資料にほとんど書いてないので飛ばします
22:15 (IPUSIRON) ここまでで半分きました。質問はないですか？
22:15 (Defolos) はい
22:15 (kirfth_) 特にないです
22:15 (IPUSIRON) ではグラフの彩色に入ります
22:16 (IPUSIRON) スライド２４のタイトル間違えてますね
22:16 (IPUSIRON) k-彩色可能です＜タイトル
22:16 (Defolos) 了解ー
22:17 (IPUSIRON) これの定義ですが、グラフの点に色を考えることを考えます
22:17 (IPUSIRON) そして、辺で隣同士は同じ色にならないとします
22:17 (Defolos) あ！　白黒で印刷したから色が分からない！
22:17 (IPUSIRON) （笑）
22:17 (IPUSIRON) そのときに
22:18 (IPUSIRON) 塗り分けできる色の数がkになって
22:18 (IPUSIRON) そのグラフはk-彩色可能といいます
22:18 (IPUSIRON) 右図の家みたいなグラフでは3色で塗りわけできます
22:19 (IPUSIRON) 実際に隣同士も同一色になってないからルールを破ってません
22:19 (IPUSIRON) もちろん4色以上でもOKです
22:19 (IPUSIRON) 次スライド25
22:20 (IPUSIRON) 最初の文章の「k-彩色可能」というところは「k-彩色的」の間違いでした
22:20 (IPUSIRON) これはk-彩色可能を満たすようなkの最小値のときを意味します
22:21 (IPUSIRON) k-1で彩色不可能で、kで彩色可能なときに、k-彩色的というわけです
22:21 (Defolos) 彩色不可能と間違えてませんか？
22:21 (IPUSIRON) ああ
22:21 (IPUSIRON) k-1のほうそうですね
22:21 (Defolos) 誤字なだけですね＾＾；
22:21 (IPUSIRON) 先ほどの図でいえば、２色では塗り分け不可能です
22:21 (IPUSIRON) 一方３色では可能でした
22:22 (IPUSIRON) よって、3-彩色的といいます
22:22 (IPUSIRON) χを使って表すときは彩色的の値、即ち彩色数を意味することとします
22:23 (IPUSIRON) 実際に具体例として完全グラフの彩色数を考えてみます
22:23 (IPUSIRON) スライド26の図は完全グラフK5です
22:23 (IPUSIRON) 完全グラフの定義としてすべての点が辺で結ばれてしまうので、
22:23 (IPUSIRON) 塗りわけを考えるとK5のときは5色ないとだめですね
22:23 (IPUSIRON) つまりχ（Kn）＝５になります
22:24 (IPUSIRON) 自分自身の色と、隣り合う点の数n-1で、合計1+(n-1)=n色です
22:24 (IPUSIRON) 次に極端な例として空グラフを考えます
22:24 (IPUSIRON) このときは辺が１本も存在しないで、点だけの世界なので
22:25 (IPUSIRON) １色あれば問題ありません。よって、彩色数は1です
22:25 (IPUSIRON) 完全グラフは辺が多い極端な例、空グラフは辺が少ない極端な例です
22:25 (IPUSIRON) つまり、彩色数は1〜nに収まることが示唆されます
22:26 (Defolos) おー
22:26 (IPUSIRON) 定義から当たり前ですけどね。
22:26 (IPUSIRON) 後の定理ではその彩色数のとりうる範囲がせばまっていくことを見ていきます
22:27 (IPUSIRON) 次に、特殊なグラフとして完全２部グラフを考えます
22:27 (IPUSIRON) これはスライド28の図を見てもらったほうが早いと思います
22:27 (IPUSIRON) 白と黒でマークされていますが
22:27 (IPUSIRON) それは本来グループを意味するんですが、色分けだと思ってもいいですね
22:27 (IPUSIRON) そうすると２色で十分で明日
22:28 (IPUSIRON) 十分です
22:28 (IPUSIRON) ２部グラフならば彩色数2、３部グラフならば彩色数3と推測できます
22:28 (IPUSIRON) 次にスライド29
22:28 (IPUSIRON) 定理17.1
22:29 (IPUSIRON) 単純グラフGの最大次数がΔならば、Gは(Δ+1)-彩色可能である
22:29 (IPUSIRON) まず具体例で見てみます
22:29 (IPUSIRON) 右図を見てみると、Gの最大次数は4です
22:29 (IPUSIRON) 次数というのは点につながる辺の数です
22:30 (IPUSIRON) 一番下の黄色の部分とかをみると、１点に４本繋がっていますね
22:30 (IPUSIRON) あと他のところも同様に見てみると、どうやら４が最大次数とわかります
22:31 (IPUSIRON) また、このGの彩色数は4です
22:31 (IPUSIRON) つまり、４以上で彩色的ということです
22:31 (IPUSIRON) Δ+1で彩色的であるという結論の定理なので、
22:32 (IPUSIRON) ５彩色的は満たされていることがわかります。
22:32 (IPUSIRON) 要するにこの定理は、精密性がかけている定理とも考えられますね
22:32 (Defolos) なるほろ
22:32 (IPUSIRON) なぜ精密性が欠けているのかというと、定理では単純グラフとしかいってないので
22:33 (IPUSIRON) 非連結も連結でもどっちでもいいわけです
22:33 (IPUSIRON) 実は連結の場合は「最大次数＝Δ」⇒「Δで彩色可能」がいえるんですが
22:34 (IPUSIRON) 非連結では「最大次数＝Δ」⇒「Δ＋１で彩色可能」になります。
22:34 (IPUSIRON) 分けて考えれば精密になりますが、この定理は単にまとめてしまっているので、精密じゃない方にぶれてしまっているわけです
22:34 (IPUSIRON) 値がぶれている
22:34 (kirfth_) なるほど
22:34 (IPUSIRON) この定理の証明では数学的帰納法を使います
22:35 (IPUSIRON) この証明はあまり面白くないので飛ばします（笑）
22:35 (IPUSIRON) それで精密バージョンとして、スライド31の定理17.2があります
22:36 (IPUSIRON) ただし、完全グラフでないとするという条件があるので、じゃ完全グラフのときどんな不都合が出るかということを調べてみました
22:36 (IPUSIRON) 完全グラフの彩色数がnであることはすでに確認しました。
22:37 (IPUSIRON) つまり、もちろんn以上で彩色可能です。
22:37 (IPUSIRON) 一方、完全グラフの定義より、Knの最大次数はn-1になります。
22:38 (IPUSIRON) 定理17.2は「最大次数＝Δ」⇒「Δで彩色可能」ということをいっていました。
22:38 (IPUSIRON) しかし、今調べた結果では、「Knの最大次数＝n-1」、「Knはnで彩色可能」ということになります。
22:39 (IPUSIRON) これは定理17.2と矛盾していますね。
22:39 (IPUSIRON) なぜなら
22:39 (IPUSIRON) △のところにn-1を代入してみると、
22:39 (IPUSIRON) n-1で彩色可能でなければならないのに、調べた結果ではn彩色的なわけなので
22:39 (IPUSIRON) n-1では彩色不可能ですから
22:40 (IPUSIRON) そういう意味で、完全グラフだけは連結グラフから除外しているようです。
22:40 (IPUSIRON) 証明は元資料にも省略されていましたので飛ばします。
22:40 (IPUSIRON) ここまで大丈夫ですか？
22:40 (kirfth_) 大丈夫です
22:40 (Defolos) ＯＫです
22:41 (IPUSIRON) スライド32
22:41 (IPUSIRON) 定理17.3
22:41 (IPUSIRON) すべての単純平面グラフは６彩色可能である
22:41 (IPUSIRON) すべての　というが強力です
22:42 (IPUSIRON) 証明は数学的帰納法を使います
22:42 (IPUSIRON) 数学的帰納法の最初の段階として最小値のほうをチェックします
22:42 (IPUSIRON) 6彩色可能といっているので、点の数は６より大きいとして話を進めます
22:43 (IPUSIRON) よって点が一番小さいときというのは7つのときです。これが[1]です
22:43 (IPUSIRON) これを具体的に書いてみると、右上図になりました
22:43 (IPUSIRON) 平面グラフの中ではこれ以上複雑にかけません
22:44 (IPUSIRON) このとき、実際に色分けすると６色でOKであることがわかりました。これは定理を満たしていているので安心です
22:44 (IPUSIRON) 次に、n=k個の場合、題意が成り立つと仮定します。
22:44 (IPUSIRON) このとき、n=k+1の場合、題意が成り立つことを主張したい。
22:45 (IPUSIRON) 前にやった定理13.6というのがあって、「すべての単純平面グラフには次数5以下の点がある」が成り立っていました。
22:46 (IPUSIRON) n=k+1のときのグラフももちろん単純平面グラフなので、この定理の結果が成り立ちます
22:46 (IPUSIRON) つまり、次数5以下の点を必ず含むわけです
22:46 (IPUSIRON) その点をvとしておきます
22:47 (IPUSIRON) このとき、vとそれに接続されている辺を除去すると、k個の点だけになります。
22:47 (IPUSIRON) k+1個からvの１点取り除くからk個になるのは自明ですね
22:47 (IPUSIRON) ところで、n=kのときは題意が成り立つと仮定していたので、これが使えそうです
22:48 (IPUSIRON) つまり、n=k+1からvと繋がっている辺を取り除いた結果のグラフは、６彩色可能です
22:48 (IPUSIRON) 後は逆に考えて
22:48 (IPUSIRON) vというものは次数5以下なので、
22:49 (IPUSIRON) 6色のうち少なくとも１つは繋がらなくて済む点があります
22:49 (IPUSIRON) その点の色をvに塗っておけば、n=k+1の塗りわけが完了して、６彩色可能になっているわけです
22:49 (Defolos) なるほろ
22:49 (IPUSIRON) 以上のことから、題意が成り立ちます
22:50 (IPUSIRON) ポイントは点を除去して、n=kの場合にわざとしてから仮定を適用してから、またvを打つことを考察するという点ですかね
22:50 (Defolos) 「全ての」という記述の証明に対して数学的帰納法って良く使われますね
22:50 (IPUSIRON) はい
22:50 (IPUSIRON) 無限のものを対象にする時は数学的帰納法が有効です
22:51 (Defolos) ほほー
22:51 (IPUSIRON) 後は選択公理というのも効果的ですが、詳しく知りません
22:51 (Defolos) なるほど＾＾；
22:51 (IPUSIRON) 人間が無限にアプローチする手法は数学的帰納法と選択公理ぐらいですよ
22:51 (IPUSIRON) といってもここでいう無限は整数と同じ数の無限で
22:51 (IPUSIRON) 一番小さい無限ですが
22:52 (Defolos) 無限にも種類があるのですね
22:52 (IPUSIRON) あります
22:52 (IPUSIRON) 実数と同じ濃度を持つ無限とか、色々
22:52 (Defolos) ほむ
22:52 (Defolos) 横道にそらしてしまって申し訳ありませんでした＾＾；
22:52 (IPUSIRON) 実数と同じ濃度を持つ無限＝0と1の間にある濃度の無限
22:53 (IPUSIRON) はい
22:53 (IPUSIRON) 次はスライド34
22:53 (IPUSIRON) 定理17.4
22:53 (IPUSIRON) すべての単純平面グラフは5彩色可能である
22:54 (IPUSIRON) 先ほどより1個分精密になっています
22:54 (IPUSIRON) 精密になるということは証明が少し難しくなると想像できます
22:54 (IPUSIRON) 証明は先ほど同様に数学的帰納法を使います
22:54 (IPUSIRON) [1]のところは先ほどと同様に考えて、n=6空スタートです
22:54 (IPUSIRON) から
22:55 (IPUSIRON) n=6のときはスライド34のグラフのときが一番複雑であり、実際に色の塗りわけをすると５色でいけました
22:55 (IPUSIRON) よって定理は満たされる。
22:55 (IPUSIRON) 次にn=kのときに題意が成り立つと仮定します
22:55 (IPUSIRON) このときn=k+1のときに題意が成り立つことを主張したい
22:56 (IPUSIRON) 先ほど紹介した定理13.6より、5次以下の点が存在することになります
22:57 (IPUSIRON) 今彩色数5で考えているので、4次以下の点しかないグラフならば問題ありません
22:57 (IPUSIRON) そこでちょうど5次の点を持つグラフだけを考えていきます
22:57 (IPUSIRON) ５次なので、ｖの周りに５つの点v1〜v5があるとします
22:58 (IPUSIRON) 上図を見てください
22:59 (IPUSIRON) vv1とvv3を縮約すると、v3がv1に来ることになり点が１個へります
22:59 (IPUSIRON) つまり合計k個のグラフになりました
22:59 (IPUSIRON) ここで仮定を使います
22:59 (IPUSIRON) 右側のグラフは仮定より5彩色可能です。後は縮約を戻したときにどうなるかかんが得ます
22:59 (IPUSIRON) 考えます
23:00 (IPUSIRON) つまりv3の色をどうするのかということです
23:01 (IPUSIRON) ここでvの色をv1とv3に与えて、vにはv1の色を塗ります
23:01 (IPUSIRON) すると美味い具合に５彩色可能を維持したまま、k+1のほうに戻すことができるのです
23:01 (IPUSIRON) 納得できますか？
23:02 (Defolos) ＯＫ・・・だと・・思います＾＾；
23:02 (IPUSIRON) テクニカルな塗り分けだと思いますね　最後は
23:02 (IPUSIRON) vを挟んだv1,v3を同一にすることで余裕を持たせるわけですね
23:03 (Defolos) vの色を譲渡するというのはなかなか賢いですね
23:03 (IPUSIRON) はい
23:03 (IPUSIRON) 6彩色可能、5彩色可能ときたら、4彩色可能か？ということが気になります
23:03 (IPUSIRON) それは定理17.5ですが、実際これも成り立ちます
23:04 (IPUSIRON) これは４色問題と同等の定理であって、
23:04 (IPUSIRON) 証明は難しいので省きます
23:04 (Defolos) 地図の塗りわけ問題そのままですね
23:04 (IPUSIRON) １５０年ぐらいたって解かれたようです
23:04 (IPUSIRON) 地図そのものは双対グラフとみなせるので、地図からグラフを自動的に生成できますからね
23:05 (IPUSIRON) 例題9.1,9.2は飛ばすことにします
23:05 (IPUSIRON) 9.3は面白そうなので見てみました
23:05 (IPUSIRON) (1)各プラトングラフの彩色数を求めよ
23:06 (IPUSIRON) プラトングラフとは正○面体というやつです
23:06 (IPUSIRON) これは５種類しかないことが証明されています
23:06 (Defolos) 今回は立体的なグラフにおける彩色ですね
23:06 (IPUSIRON) はい
23:06 (Defolos) なるほろ
23:06 (IPUSIRON) でもプラトングラフは実際平面に描画可能なのです
23:07 (Defolos) ほほー
23:07 (IPUSIRON) よって今日やった道具をいろいろ使えそうですね
23:07 (IPUSIRON) 今日は平面グラフで考えていたので
23:07 (IPUSIRON) とりあえず定理17.5よりどんなグラフも４彩色可能なので、プラトングラフの彩色数であっても4以下の値になることは当然です
23:08 (IPUSIRON) これの具体的な色分けはスライド40の通りです。結果はスライド39に書いてあります
23:08 (IPUSIRON) 微妙に対象になっているようななっていないような、特に正12面体の塗りわけは面白いです
23:08 (IPUSIRON) δだけポツンとひとつ使います
23:09 (IPUSIRON) (2)完全3部グラフの彩色数は？
23:09 (IPUSIRON) これは先ほどの考察どおり3で決定されます
23:09 (IPUSIRON) ３部＝３グループという意味なので
23:09 (IPUSIRON) グループに共通の色をもたせればOKです
23:10 (IPUSIRON) 共通グループは絶対に隣接しないので
23:10 (IPUSIRON) (3)k-立方体の彩色数は？
23:10 (IPUSIRON) k-立方体の定義ですが正直よくわかりませんので、上の図を見てください
23:10 (IPUSIRON) これは3-立方体ですね
23:10 (Defolos) 確かにちょっと分かりにくかったですよね＞k-立方体
23:10 (IPUSIRON) 白黒が交互に出てくるというのが定義らしく、
23:11 (IPUSIRON) これは２分グラフの立体版みたいなもんだと思えば、彩色数は２で確定します
23:11 (IPUSIRON) 少し早いですが以上で終わりました。質問などありますか？
23:12 (Defolos) とくにないです
23:12 (IPUSIRON) 全体木のところなど複雑だったかなと思いました
23:12 (IPUSIRON) 対応というところに気付くのと、具体的にやっていけば理解が深まると思います
23:13 (IPUSIRON) ではとりあえず終了ですかね
23:13 (Defolos) おつかれさまでしたー
23:13 (kirfth_) お疲れ様でした。