21:00 (IPUSIRON) じゃ始めます 21:00 (dotdister) よろしくお願いします。 21:00 (Defolos) おねがいしますー 21:00 (IPUSIRON) まず今回はオイラーグラフとハミルトングラフというグラフ理論の中でも重要なものについて解説します 21:00 (IPUSIRON) まず4ページです 21:01 *clothoid join #akademeia (~cake@PPPbm2225.tokyo-ip.dti.ne.jp) 21:01 (IPUSIRON) こんばんは 21:01 (Defolos) こんばんはー 21:01 *IPUSIRON mode +o clothoid 21:01 (clothoid) こんばんわー 21:01 (dotdister) こんばんは。 21:01 (clothoid) 今日は資料無しですか？ 21:01 (Defolos) アップローダーにありますよ 21:01 (IPUSIRON) 1時間前にアップしました 21:02 (IPUSIRON) 元々グラフ理論とは、4ページに書いてあるケーニヒスベルクの橋渡りの問題から始まったようなものです 21:02 (clothoid) 了解です。探してきます＜アップローダ 21:02 (IPUSIRON) どういう問題かというと、橋を1回だけ渡って、すべての地区にいけるかというやつで 21:03 (IPUSIRON) 右下図のグラフにおいて、一筆書きができるかどうかということに帰着されます 21:03 (IPUSIRON) 当時この問題は難問とされてましたが、あの有名なオイラーが不可能であることを証明しました 21:04 (IPUSIRON) それ以降こうやって点と辺の数学の重要性が考え出されたわけです 21:04 (IPUSIRON) 5ページ 21:04 (IPUSIRON) まず周遊可能グラフというものを定義します。 21:04 (IPUSIRON) 周遊可能グラフとは周遊可能小道を持つ多重グラフのことです 21:05 (IPUSIRON) 多重グラフとは、2点の間に複数の辺があっていいようなグラフのことです 21:05 (Defolos) なるほど 21:05 (IPUSIRON) それで、周遊可能小道というのはすべての辺を1回だけ通るグラフのことです。 21:05 (IPUSIRON) つまり直観的には「周遊可能グラフ＝一筆書き可能なグラフ」とうことになります 21:06 (IPUSIRON) ここまでいいですか？ 21:06 (Defolos) はい 21:06 (clothoid) はい 21:06 (dotdister) はい。 21:06 (IPUSIRON) それで次にオイラーグラフに入ります。6ページ 21:06 (IPUSIRON) まずオイラー閉路とは閉じている周遊可能グラフのことです 21:07 (IPUSIRON) つまり始点と終点が一致するような一筆書きできる小道と思えばOKです 21:07 (IPUSIRON) すべての辺において、このオイラー閉路を持つようなグラフのことをオイラーグラフといいます 21:08 (IPUSIRON) 右上図を見てください。数値が移動順です 21:08 (IPUSIRON) こうやって移動すると全部de6辺 21:08 (IPUSIRON) 全部で6辺を移動できていますよね 21:08 (IPUSIRON) なおかつ始点と終点が一致してます 21:08 (IPUSIRON) あくまでオイラーグラフは辺だけに注目していて、点はだぶって通ってもOKです 21:10 (IPUSIRON) 次にどうやっても始点と終点が一致しないけど、一応すべての辺を通る小道が存在するようなグラフを半オイラーグラフといいます。 21:10 (IPUSIRON) これはあまり使わないので、オイラーグラフだけ理解しておけば十分だと思います 21:10 (IPUSIRON) ここまでで何かわからないところありますか？ 21:10 (Defolos) 今のところ大丈夫ですー 21:11 (clothoid) 大丈夫です。 21:11 (dotdister) ダイジョブです。 21:11 (IPUSIRON) では次に7ページの補題に入ります。 21:11 (IPUSIRON) これは配布資料にはなかったものですが、この補題を理解しておくとその後の定理の証明でつかえるので個別にやっておきます 21:12 (IPUSIRON) 補題とは、すべての点の次数が偶数である連結グラフは、任意の点を含む閉路が少なくともひとつ存在するという主張です 21:13 (IPUSIRON) これを証明しますが、まず「すべての点の次数が偶数である連結グラフ」をGとします 21:13 (IPUSIRON) Gから任意の点Aを選びます 21:13 (IPUSIRON) 「任意」＝「自由に」ということです 21:13 (IPUSIRON) ランダムに選んでいると思ってください 21:14 (IPUSIRON) すると、点Aと繋がっている辺（Eとする）にはもうひとつ点があります。それをBとします。 21:14 (IPUSIRON) このときGから辺Eを除いたグラフをG1とします 21:15 (IPUSIRON) このときG1においてAからBに行ける経路（Fとする）が存在すれば、Gには閉路があることはわかります 21:15 (Defolos) ＡからＢに回り道していけるかってことでしょうか 21:15 (IPUSIRON) そうですね 21:15 (Defolos) 了解です 21:16 (IPUSIRON) あくまでもうAとBは繋がっているというのは確定しているので 21:16 (IPUSIRON) もう1本のつながる経路があればよいということです 21:16 (Defolos) なるほど 21:16 (IPUSIRON) 次に、この経路Fが存在することを示します 21:17 (IPUSIRON) G1のはじっこの2つの点AとBの次数は奇数です 21:17 (IPUSIRON) もともとGのすべての点が偶数といっているので 21:17 (IPUSIRON) 偶数-1＝奇数ですね 21:18 (IPUSIRON) もともと偶数ということは2以上であって、そこから1をひいたら、1以上ですよね 21:18 (IPUSIRON) だからAとBの次数は1以上となります。即ち、少なくとも1つの辺と繋がっているとなります 21:19 (IPUSIRON) 今度はG1において、Aを始点とする任意の経路を選びます。 21:19 (IPUSIRON) 経路なので最終的に終点があって、それをB1とします 21:20 (IPUSIRON) もしB1とBが一致していれば、問題なし。G1においてAとBに経路があったとわかります。 21:20 (IPUSIRON) 問題はB1とBが一致していないときです 21:20 (IPUSIRON) このときAとB1の間の経路を取り除いて、また今やってきたようなことを繰り返します 21:20 (IPUSIRON) 再帰的にやるようなものです 21:21 (IPUSIRON) そうすると、結局Bが終点になるしかなくなり、まとめて考えると、G1のおいてAとBは経路で繋がったことになります。 21:21 (IPUSIRON) もともとAとBの定義は辺で繋がっているといっていたので、 21:22 (IPUSIRON) でかい経路ととなりあう辺をくっつければ、ぐるっと閉路になります。 21:22 (IPUSIRON) これで証明終わりです 21:22 (Defolos) なるほろ 21:22 (IPUSIRON) 図を見ながら考えるとわかると思いますが、わからないところありますか？ 21:22 (dotdister) 大丈夫です。 21:23 (Defolos) ＯＫですー 21:23 (IPUSIRON) では次にオイラーグラフ判定定理に入ります 21:23 (clothoid) ＯＫっす 21:23 (IPUSIRON) これはオイラーによって証明されたものですが、オイラーの定理とも呼ばれています 21:23 (Defolos) オイラーさん、賢いなぁ・・・ 21:23 (IPUSIRON) でもオイラーは色々活躍したので、オイラーの定理というと別のものと混乱するのでここでは名付けませんでした 21:24 (IPUSIRON) グラフGがオイラーグラフであることと、Gは連結かつ点の次数がすべて偶数であることは同値という定理です。 21:24 (IPUSIRON) ⇔の記号の意味大丈夫ですか？ 21:25 (Defolos) はい 21:25 (dotdister) 必要十分条件ですか？ 21:25 (clothoid) はいー 21:25 (IPUSIRON) そうです＜必要十分 21:25 (dotdister) わかりました。 21:25 (IPUSIRON) これを示すときには、右ならば左　と　左ならば右というのを示せばよいことになります 21:25 (IPUSIRON) まず⇒を示します 21:26 (IPUSIRON) 「Gはオイラーグラフである」と仮定して、「Gは連結かつ点の次数がすべて偶数である」という結論を証明するわけです 21:26 (IPUSIRON) オイラーグラフの定義により、Gにはオイラー閉路が存在します。 21:27 (IPUSIRON) これは複数ありえます。あくまで定義ではひとつでもオイラー閉路があればオイラーグラフと呼ぶので 21:27 (IPUSIRON) とりあえず複数あったとしても、そのうちのひとつをLとします 21:28 (IPUSIRON) Lはすべての点を含んでいて、オイラー閉路という定義よりそれらがつながっているということなので、全体でみると連結グラフです 21:28 (IPUSIRON) これで連結性は示せました。 21:28 (IPUSIRON) 次に点の次数がすべて偶数であることを示します 21:28 (IPUSIRON) Lに属するある点を考えます 21:29 (IPUSIRON) 点に辺がつながっているわけですが、経路で考えると入口と出口という2つのペアがなければ、その点で止まってしまいますよね 21:30 (IPUSIRON) つまりある点では入口と出口のペアで構成されるということです（ペアはいくつあってもよい） 21:30 (IPUSIRON) ペアの時点で2つの辺がつながっているので、偶数 21:31 (IPUSIRON) ペアが複数あったとしても、偶数×（何でも）＝偶数 21:31 (IPUSIRON) つまりその点の次数は偶数となります 21:31 (IPUSIRON) これは任意の点でも同じ議論ができるので、すべての点において偶数ということになります。 21:31 (Defolos) なるほど 21:31 (IPUSIRON) これで⇒は示せました 21:31 (IPUSIRON) 12ページでは具体的なグラフで考えています（資料のやり方） 21:32 *infog join #akademeia (~infog@58x158x45x213.ap58.ftth.ucom.ne.jp) 21:32 (IPUSIRON) 次に←を示します。13ページ 21:32 (IPUSIRON) こんばんは 21:32 (Defolos) こんばんは 21:32 (infog) 遅れました。お願いします 21:32 (clothoid) こんばんわ 21:32 (dotdister) こんばんは。 21:32 (IPUSIRON) 「連結グラフのGのすべての点の次数が偶数」ならば「Gはオイラーグラフ」ということを示します 21:33 (IPUSIRON) ここで補題を使います。 21:33 (IPUSIRON) 補題より、このGで任意の点を含む閉路が必ず存在します 21:33 (IPUSIRON) この閉路をLとします 21:34 (IPUSIRON) まずLがGのすべての辺を含んでいるときは、そもそもL自身がオイラー閉路になり、オイラー閉路のあるグラフがオイラーグラフなので、題意が成り立ったことになります 21:34 (IPUSIRON) 問題はLがGのすべての辺を含んでいないときに生ります 21:34 (IPUSIRON) なります 21:35 (IPUSIRON) ここでGの中でLに属する辺を除去します。そして得られるグラフをG1と新たにおきます 21:35 (IPUSIRON) このG1はいくつかの連結グラフで構成されます 21:35 (IPUSIRON) そのうちのひとつをG1'とします 21:36 (IPUSIRON) 14ページの図を見てください 21:36 (infog) すみません。資料の方は何処にありますか? 21:36 (Defolos) アップローダーにありますよ 21:36 (IPUSIRON) アップローダーにアップしてあります 21:36 (IPUSIRON) URLわかりますか？ 21:36 (Defolos) http://security2600.sakura.ne.jp/up/upload.php 21:37 (IPUSIRON) どうもです 21:37 (infog) ありがとうございます。見落としていました。 21:37 (IPUSIRON) ここではGからLを取り除くので、G1'とG2'という２つの連結グラフが存在します。 21:37 (IPUSIRON) まずLの適当な点を始点としてスタートします 21:37 (IPUSIRON) 図ではまずG1'と1点で繋がっており、そこにきたら 21:38 (IPUSIRON) G1'の中をとおります。 21:38 (IPUSIRON) そしてG1'を通り終わったら、またLにそって動きます 21:38 (IPUSIRON) 今度はG2'に出会うので、そこも同じくG2'の中をまわってきたら、Lに沿って動きます 21:38 (clothoid) （掲示板のほうにも書き込んだ方がいいかもしれませんね←今回の資料のありか） 21:39 (IPUSIRON) すると終点は始点と一致して、なおかつすべての辺を通す閉路が構成されます 21:39 (IPUSIRON) 了解です 21:39 (IPUSIRON) よってGはオイラーグラフとなりました 21:39 (IPUSIRON) これで証明終わりです 21:40 (IPUSIRON) わからないところありますか？　あったらその場でもよいので教えてください 21:40 (IPUSIRON) なければ次に例題11に入ります 21:40 (Defolos) たぶん大丈夫 21:40 (clothoid) 大丈夫です。 21:40 (dotdister) どぞー。 21:40 (IPUSIRON) 完全グラフK_nはオイラーグラフになるかという問題です 21:41 (IPUSIRON) 完全グラフというのはある点が他の点と必ずつながっているというグラフです 21:41 (infog) なんとか追いつきます 21:41 (IPUSIRON) 15ページの右上図はK5の完全グラフです 21:41 (IPUSIRON) 一般的にKnの点の次数はn-1となります。 21:42 (IPUSIRON) これは自分自身の点を除いたすべてと繋がるので、n-1ということになるわけです 21:42 (IPUSIRON) Knの点の総数はnです 21:42 (IPUSIRON) 先ほど証明したオイラーグラフ判定定理では、点の次数が偶数である必要があったので 21:43 (IPUSIRON) n-1=偶数のときにKnはオイラーグラフとなります 21:43 (IPUSIRON) つまりn=奇数のKnだけがオイラーグラフになれるということです 21:44 (IPUSIRON) 実際にK5はn=5=奇数なので、オイラーグラフであり、そのオイラー閉路は図にかいた数値の順番に移動すればわかります 21:44 *IPUSIRON mode +o infog 21:44 (IPUSIRON) 次に例題11です 21:44 (IPUSIRON) 例題11の（２）です 21:44 (IPUSIRON) 完全二部グラフがオイラーグラフになるときの条件を調べる問題です 21:45 (IPUSIRON) 二部グラフというのは2つのグループにわかれていて、同一グループ間には辺がないようなものです 21:45 (IPUSIRON) 完全と付いているので、すべての点と繋がるということです（ただし同一グループは無視） 21:46 (IPUSIRON) Ks,tといったとき、sは上のグループの点の数、tは下のグループの点の数です 21:46 (IPUSIRON) まずsとtの上下はどっちでもいいのですが、片方（ここではsとしておく）は2以上である必要があります 21:47 (IPUSIRON) もしs=1だと、どうやっても下→上→下となって、上に戻ってこれないからです 21:47 (IPUSIRON) 2つ目の条件は、tが偶数ということです。これも同様に考えて 21:48 (IPUSIRON) 上→下→上→…→上と戻ってこれるようにするためには、矢印の数が偶数個である必要あります 21:49 (IPUSIRON) これはtが偶数と対応していることになります。 21:49 (IPUSIRON) よってKs,tがオイラーグラフになるためには、sが2以上かつtが偶数ということになります 21:50 (IPUSIRON) 次に例題11(3)に入ります 21:50 (IPUSIRON) 車輪Wnがオイラーグラフになるか？という問題です。 21:51 (IPUSIRON) 車輪とは回りにでかい閉路があって、真中にポツンと1点があって、その点と周りの閉路の点が繋がっているようなグラフです 21:51 (IPUSIRON) 自転車の車輪みたいな感じです 21:51 (IPUSIRON) 周りのでかい閉路だけを考えると、任意の点で次数は必ず2になります 21:52 (IPUSIRON) それに中央の点と繋がるということは2+1で次数3になります 21:52 (IPUSIRON) オイラーグラフ判定定理ではすべての点の次数が偶数でなければならないので、車輪はオイラーグラフには絶対にならないことがわかります 21:52 (IPUSIRON) ここまででどうでしょう？ 21:52 (clothoid) おｋっす 21:53 (Defolos) ＯＫですー 21:53 (dotdister) だいじょぶ。。。 21:53 (IPUSIRON) それでは次に18ページ 21:53 (IPUSIRON) 一筆書きのことをきとんと定義しておきます 21:54 (Defolos) 反オイラーグラフって誤字ですか？ 21:54 (IPUSIRON) Gがオイラー閉路を持つときに、「連結グラフGが一筆書きができる」と呼ぶことにします。 21:54 (IPUSIRON) 何ページですか？ 21:54 (IPUSIRON) ああほんとだ 21:54 (Defolos) 18です 21:54 (IPUSIRON) 後オイラー小道とかいてますが、オイラー閉路にしておいてください 21:55 (IPUSIRON) 連結についてですが、そもそもつながっていなければ一筆書きはありえませんよね 21:55 (IPUSIRON) だから連結グラフが大前提です 21:55 (IPUSIRON) 4ページで出てきた問題のグラフは右下図のようなものです 21:56 (dotdister) 点1つでループっていうのは反則ですか？ 21:56 (IPUSIRON) その前に、一筆書き可能かどうかをチェックできる定理があります 21:56 (IPUSIRON) それはありです＞dotさん 21:56 (dotdister) わかりました。 21:56 (IPUSIRON) 多重グラフであっても、点にループがあってもOKです 21:57 (clothoid) オイラーグラフ⊂周遊可能グラフ　ですか？ 21:57 (IPUSIRON) その定理とは、奇数の次数を持つ点が0個あるいは2個のときだけ、一筆書きができるという主張です 21:57 (IPUSIRON) ちょっとミス 21:58 (IPUSIRON) オイラー閉路じゃなくてオイラー小道でOKです 21:58 (IPUSIRON) 一筆書きとは別に始点と終点が一致しなくてよいので 21:58 (IPUSIRON) オイラーグラフ⊂周遊可能グラフですね 21:59 (clothoid) なるほど。了解です 21:59 (IPUSIRON) で、さきほどの4ページのグラフは 21:59 (IPUSIRON) 4つの点すべてが奇数次なので、今の定理より、一筆書きができないということになります 22:00 (IPUSIRON) 実際に総当りでやってもわかると思います 22:00 (IPUSIRON) 圧倒的に一筆書き判定のほうが簡単ということです 22:00 (IPUSIRON) オイラーグラフ判定のときは一応全部の点をチェックして、偶数かどうかを見る必要ありますが 22:00 (IPUSIRON) 一筆書き判定のときは奇数次の点がもう3個でたらもうアウトということです 22:01 (clothoid) では，オイラーはオイラーグラフを考え付いてケーニヒスベルグの橋渡りの問題を解決したのではなく，周遊可能グラフの判定条件を考え付いてケーニヒスベルグの橋渡りの問題を解決したということっすね？ 22:01 (IPUSIRON) そうです 22:01 (clothoid) 了解っす。 22:01 (IPUSIRON) それで仮に一筆書きがあると判定できたとしても、実際の順路を調べるのは別問題です 22:01 (IPUSIRON) そこで一筆書きを求めるアルゴリズムがあります。 22:02 (IPUSIRON) ポイントは奇数次の点があれば、そこからスタートして奇数次の点で終わるようにするということです 22:02 (IPUSIRON) これで一筆書きは終わりです。オイラーグラフに戻ります 22:02 (IPUSIRON) 20ページの問題ですが 22:03 (IPUSIRON) これは各会場の道数＝次数がもうわかっているので、 22:03 (IPUSIRON) 実際にグラフを書かなくても判定定理よりわかります 22:04 (IPUSIRON) 全部偶数なので、一筆書きもできるし、オイラー閉路もあるということです 22:05 (IPUSIRON) 今度は実際のオイラー閉路を求めるという別問題があります。 22:05 (IPUSIRON) 21ページのオイラー小道となっているのはオイラー閉路の間違いですね。直しておきます 22:05 (Defolos) 、オイラー探すほうが難しい　になっちゃってます 22:05 (IPUSIRON) これを解くためのアルゴリズムとしてフラーリーのアルゴリズムというものがあります 22:06 (IPUSIRON) ですね 22:06 (IPUSIRON) オイラー閉路を探すのが難しいということです 22:06 (IPUSIRON) 直観的にいうと始点と終点を一致させない順路のほうが簡単にできるということです 22:06 (IPUSIRON) このアルゴリズムですが、正直いってよくわかりませんでした… 22:07 (IPUSIRON) 検索してもほとんどヒットしませんでした 22:07 (IPUSIRON) よく理解できないのでそのアルゴリズムだけ一応書いておきました 22:07 (Defolos) 前版の教科書にも載ってなかった気がします 22:07 (IPUSIRON) ほうほう 22:07 (Defolos) 学校に古いやつがありまして、それを読んだ限りでは、ですけれどもね 22:08 (clothoid) 前版の教科書ってなんですか？ 22:08 (IPUSIRON) 仕方ないので飛ばすことにします。すみません 22:08 (Defolos) この資料の教科書として使われている本の現行より前の版の本です 22:09 (IPUSIRON) 例題6.2.1に入ります。まず(1)はさっきの催し会場の問題のグラフを描けというものです。これは22ページのような図になります。 22:09 (Defolos) ややこしくてすいません 22:09 (clothoid) あ，了解です。ウィルソンの〜ってやつっすかね。 22:10 (IPUSIRON) (2)はこのグラフに対してフラーリーのアルゴリズムを使えという問題ですが、よくわからなかったので、試行錯誤して総当りでやりました 22:10 (Defolos) そそ＞うぃるそん 22:10 (IPUSIRON) その道順の答えが23ページの図です。 22:10 (IPUSIRON) 次にやっとハミルトングラフに入ります 22:11 (IPUSIRON) まずハミルトン閉路とは、各点をちょうど1度だけ通る閉じた小道です 22:11 (clothoid) 試行錯誤して〜とは，適当にアルゴリズムに従うようにやってもうまくいかないってことですか？ 22:12 (IPUSIRON) いえアルゴリズム自体がよく飲み込めていないというのがあります 22:12 (clothoid) オイラー小道をたくさん求めて選ぶところっすね＜試行錯誤 22:12 (clothoid) 了解です＜アルゴリズム自体が・・・ 22:13 (IPUSIRON) ちなみにこのアルゴリズムで解いても、多分オイラー閉路確定しないような気がします。 22:13 (IPUSIRON) あくまで絞込みなのかなと思ったんですが 22:13 (IPUSIRON) 21ページの最後の行に書いたのですが 22:14 (IPUSIRON) 一応アルゴリズムに従ってやってもうまくいかなったので、始点＝終点 22:15 (clothoid) そうっすか。。。了解です。 22:15 (IPUSIRON) ちょっと疑問があるんですが、25ページの右中図では黒点が残っているのですが、ここも通る必要あるのか 22:16 (clothoid) 各点をってからには，通らないといけないのではないんですか？ 22:16 (dotdister) 閉じた「小道」であればいいのですから、通る必要ないかと。。。 22:16 (Defolos) 各点だから全部通らないといけないのかも 22:17 (dotdister) あぁ、そうか。 22:17 (IPUSIRON) じゃその図を直しておきます 22:18 (IPUSIRON) 各点すべてをちょうど1度だけ通る閉じた小道のことをハミルトン閉路と呼びます 22:18 (IPUSIRON) このハミルトン閉路から成り立つグラフをハミルトングラフと呼びます。 22:18 (IPUSIRON) ちなみに閉じていないときは半ハミルトングラフと呼びます 22:18 (IPUSIRON) 26ページ 22:18 (clothoid) ハミルトンG⊂オイラーG っすかね？ 22:19 (IPUSIRON) そうとは限らないと思います 22:19 (clothoid) 違いますね。 22:19 (IPUSIRON) ハミルトンは点だけに注目しているので 22:19 (clothoid) はい。 22:19 (Defolos) 辺に注目するオイラーと、点に着目するハミルトンって感じなのかな 22:19 (IPUSIRON) そうですね 22:19 (clothoid) すみません。了解です。 22:20 (IPUSIRON) 与えられたグラフがハミルトン閉路を持つ、即ちハミルトングラフであるかどうかを効率的に調べるアルゴリズムはないと思われています 22:20 (IPUSIRON) 思われているというのは、今の数学者にとって思われているということです 22:20 (clothoid) おー。発見したら大発見っすか？ 22:20 (IPUSIRON) そうです 22:21 (IPUSIRON) 効率的にというのは 22:21 (IPUSIRON) 多項式時間で計算できるという意味なんですが 22:22 (IPUSIRON) なんていったらいいんだろ… 22:23 (Defolos) すごく難しそうなんですが・・・ 22:23 (IPUSIRON) あるアルゴリズムに入力を与えて、出力が出る時間が早いというかんじかな 22:24 (IPUSIRON) PCにソートやらせれば早いですよね 22:24 (clothoid) 了解っす＜時間が早い 22:25 (IPUSIRON) ソートするためのテキストファイルとかがでかければその分遅くなるけど、ちょっとだけですよね 22:25 (clothoid) はい 22:25 (IPUSIRON) でもPCにハミルトングラフを判定させようとすると、いつ終わるのかどうかわかならいというレベル 22:25 (IPUSIRON) 速さの効率が桁が違うという感じかな 22:25 (dotdister) ほぅ。 22:25 (clothoid) むぅ。 22:26 (Defolos) なるほど 22:26 (IPUSIRON) あと素因数分解を解くのは困難だと信じられていますよね 22:26 (IPUSIRON) 桁数が大きければ 22:26 (clothoid) そうなんですかー＜素因数分解 22:26 (IPUSIRON) 素因数分解を解くための効率のよいアルゴリズムとして数体ふるい法というのがあるんですが、それであっても多項式時間じゃないんです＝遅いということです 22:27 (IPUSIRON) もしかしたら数対ふるい法よりも早いものが将来発見できるかもしれませんけど、それでも効率的にはならないんじゃないかと広く知られてるわけです 22:27 (IPUSIRON) 信じられている 22:28 (Defolos) ほほー 22:28 (IPUSIRON) 話ずれましたが、巡回セールスマン問題というのはハミルトン閉路でなおかつ最短路を求めるような問題です 22:28 (clothoid) 多項式時間じゃない→指数関数的？とか言ってみたり・・・。 22:28 (IPUSIRON) 多項式時間＜準指数時間＜指数時間なんです 22:28 (Defolos) へぇ〜〜 22:28 (clothoid) おー。なんかあたった。嬉しいｗ 22:29 (IPUSIRON) 多項式時間はnに比例して、準指数時間はn log(n)とか、指数時間はn^2,n^5,…とかです 22:30 (IPUSIRON) RSA暗号を解読する＝素因数分解を解く＝解くのに準指数時間かかる 22:30 (IPUSIRON) 楕円曲線暗号を解読する＝指数時間かかる 22:30 (IPUSIRON) つまり同じ鍵の長さならば、楕円曲線暗号の方が強い暗号といえますね 22:30 (Defolos) なるほろ 22:31 (IPUSIRON) 巡回セールスマン問題（TSP）は色々な応用があってプリント基板の最適な経路とかを求めるときにかかわってきます 22:31 (clothoid) なる〜 22:31 (IPUSIRON) このTSPを解く効率的なアルゴリズムはまだ発見されてませんが、それでも近似を出すようなアルゴリズムはいくつかあります 22:32 (IPUSIRON) 26ページに書いてありますが、遺伝アルゴリズムを使うアプローチなどもあるそうです 22:32 (IPUSIRON) 興味ある人は挑戦してみてください（笑）もし解決したらものすごいことになります 22:33 (IPUSIRON) もしかしたら懸賞金かかってるかもしれません（笑） 22:33 (Defolos) ＾＾； 22:33 (IPUSIRON) 27ページに入ります。 22:33 (IPUSIRON) これはオーレの定理というもので、 22:33 (clothoid) 数学の未解決問題の懸賞金って，解いたら，一生食っていけるぐらいもらえるもんすか？ 22:34 (IPUSIRON) ハミルトングラフの判定のための定理ですが、必要十分条件のものではないです 22:34 (IPUSIRON) いえ賞金だけでは無理かな・・・ 22:34 (Defolos) ；； 22:34 (IPUSIRON) 例えばリーマン予想とかは1億円ですが、解いたことによって有名になって講演や仕事は増えると思います 22:34 (clothoid) そうですか。まぁ本とか書いたり，講演とかするから，いっか・・・。 22:35 (clothoid) 了解。すみません。中断して。どうぞ〜 22:35 (IPUSIRON) はい 22:35 (IPUSIRON) まず記号の意味から説明します 22:35 (IPUSIRON) 「s.t. 〜」というのは「〜を満たす」という意味です 22:35 (IPUSIRON) such that〜 22:35 (IPUSIRON) (55)のところは 22:36 (IPUSIRON) 「dev(v)+dev(w)≧nを満たすようなv,wが存在する」 22:36 (IPUSIRON) という意味です 22:36 (IPUSIRON) (55)が成り立つならば、そのGはハミルトングラフという主張です 22:37 (IPUSIRON) 直観的な意味も下の行に書いてあります。 22:37 (IPUSIRON) この定理の問題点は→はいえるけど、←がいえないということです 22:37 (IPUSIRON) Oreの定理のA→BのAの部分が満たすことがわかれば、問題ないのですが 22:38 (IPUSIRON) Aが成り立たなくてもハミルトングラフである場合があるので、ハミルトングラフの判定はそういうときに難しくなります 22:38 (IPUSIRON) それでは証明に入ります 22:39 (IPUSIRON) グラフGが条件(55)を満たすならば、ハミルトングラフではないと仮定します。 22:39 (IPUSIRON) 背理法です 22:39 (IPUSIRON) そこで28ページの図を考えます 22:39 (IPUSIRON) ワッカの1辺が取れた形のグラフです 22:39 (IPUSIRON) ぎりぎりハミルトングラフではないがわかると思います 22:40 (IPUSIRON) 次にそのワッカの両端をv1,vnとしておきます 22:40 (IPUSIRON) この2点において(55)を適用させます。 22:41 (IPUSIRON) 今deg(v1)=1,deg(v2)=1です 22:41 (IPUSIRON) また点の総数はn 22:41 (IPUSIRON) なので(55)より、deg(v1)+deg(v2)=1+1=2≧nが必ず成り立ちます 22:42 (IPUSIRON) 29ページの考察は省きますが、このことより、n≧4である必要があります 22:42 (IPUSIRON) このままでは2≧n≧4でおかしくなってしまうので 22:43 (IPUSIRON) さっきのワッカにさらに辺を追加したグラフを考える必要があります。少なくとも、それぞれから1本追加して計2本増やします 22:43 (IPUSIRON) それが30ページの右上図です 22:43 (IPUSIRON) v1が繋がるところにviとしていますが、別にどこでもいいです 22:43 (IPUSIRON) 同様にvnと繋がるところもどこでもよいです 22:44 (IPUSIRON) でも図のようにつなげると、うまく右下図のような経路ができてハミルトングラフ閉路が存在してしてしまいます。 22:44 (IPUSIRON) これは仮定に反します。 22:44 (IPUSIRON) みす 22:44 (IPUSIRON) ああ、「みす」がみすです（笑） 22:45 (Defolos) ＾＾； 22:45 (IPUSIRON) うまく仮定に反することができたので、仮定が間違いということがわかり 22:45 (IPUSIRON) 背理法が精巧S知恵、主張が成り立ちます。 22:46 (IPUSIRON) 背理法がうまく成功して 22:46 (IPUSIRON) ここまでどうですか？ 22:46 (IPUSIRON) 駆け足でしたが 22:46 (Defolos) んー。たぶん大丈夫です 22:46 (IPUSIRON) 大丈夫なら次いきます 22:46 (dotdister) 何とか。 22:46 (IPUSIRON) 例題6.1に入ります。 22:47 (clothoid) わかりましたー。viとvi-1はviとvpとかにした方が分かりいいと思います。なんか隣じゃないといけないきがするので・・・。iとi-1だと。 22:47 (IPUSIRON) そうですね 22:47 (IPUSIRON) i-2でもいいわけですからね 22:47 (clothoid) はい。 22:47 (IPUSIRON) p,qとして、p