（ゼミ前後の雑談はカットしました）

21:00 (IPUSIRON) 雑談はゼミの後にして、そろそろ恥まま巣か
21:00 (IPUSIRON) 始めますか
21:00 (nesys) おｋ
21:00 (mudai) うい
21:00 (Defolos) はい
21:00 (clothoid) うい
21:00 (FreeSeven) Y
21:00 (piro-_-) ｋ
21:00 (dotdister) はい。
21:00 (carbon0) はい
21:01 (IPUSIRON) それではPowerPointの資料を使ってやります
21:01 (IPUSIRON) 今回は初回で言葉の定義とかばかりなので、あまり難しくありませんが、何か疑問点あればその場で解決していってください
21:02 (IPUSIRON) まずスライド3
21:02 (IPUSIRON) そもそもグラフ理論と何の分野が関連するのかを列挙してみました
21:03 (IPUSIRON) ネットワークの場合、コンピュータを点、回線を線で単純化することで
21:03 (IPUSIRON) そのネットワークの性能をグラフ理論であらわすことができたりします。
21:03 (nesys) グラフ理論って要するにそれぞれのオブジェクトの関係を表す図ということですよね
21:04 (IPUSIRON) 色々な図を表すことができますね
21:04 (IPUSIRON) プログラムならデータ構造とかも絡んできます
21:05 (IPUSIRON) 私も最近知ったのですが、暗号理論のゼロ知識とグラフ理論の3色問題は密接に絡んでくるようです
21:05 (IPUSIRON) 3色問題というのは、3色に塗り分けるという問題のことです
21:05 (nesys) ゼロ知識…？
21:05 (IPUSIRON) ゼロ知識というのは、
21:06 (IPUSIRON) 最初にパスワード認証とか考えてもらいたいのですが
21:06 (IPUSIRON) 私がパスワードを入力したとしますよね
21:06 (nesys) はい
21:06 (IPUSIRON) そしてそのパスワードを知っているのは私だけという前提で向うのコンピュータは私を認証します
21:07 (IPUSIRON) しかし、向うが私のパスワードを勝手に使う可能性も考えられますよね？
21:07 (IPUSIRON) なりすましとか
21:07 (nesys) 相手側にパスワードが暗号化された状態であればいいのでは？
21:07 (IPUSIRON) それはアタッカーが侵入したという話ですが、むこうの管理者がなりすましたという話です
21:08 *kujaku join #akademeia (~sakura982@z220.211-132-145.ppp.wakwak.ne.jp)
21:08 (IPUSIRON) こんばんは＞孔雀さん
21:08 (nesys) こんばんわー
21:08 (FreeSeven) こんばんわ
21:08 (carbon0) こんばんは
21:08 (Defolos) こんばんわー
21:08 (piro-_-) こんばんは
21:09 (IPUSIRON) 一方、ゼロ知識（認証）は
21:09 (asuno) こんばんは
21:09 (clothoid) ばんわ
21:09 (IPUSIRON) 相手にパスワードそのものを教えないで、相手に私がパスワードを知っているということだけを教える方法なのです
21:09 *clothoid mode +o kujaku 
21:09 (nesys) ほぅそんなことが可能なんですね？
21:09 (IPUSIRON) はい
21:10 (IPUSIRON) 暗号でよく登場する概念で、不思議ですが、数学的にできちゃうのです
21:10 (IPUSIRON) 乱数とか色々使って可能にするわけですが。
21:10 (IPUSIRON) そのゼロ知識証明をもっと数学的に表記すると、グラフ理論が使われます
21:11 (mudai) 確立を低くするために使用すると言うことですか？
21:11 (IPUSIRON) つまり、あるグラフが与えられてそのグラフの3色問題の答えを相手に教えずに、答えを知っていることだけを相手に教えるのです
21:11 (nesys) なるほど
21:12 (IPUSIRON) 偶然アタッカーがゼロ知識を破る可能性もあるので、何度も繰り返してすべてOKなら正しい人だと認識するように運用されるので、確率は関連しますね
21:12 (mudai) 了解です。
21:12 (IPUSIRON) 次スライド6に入ります。
21:13 (nesys) 面白い仕組みですね。ゼミ的に進行の妨げになりそうなので、調べてみます
21:13 (IPUSIRON) ゼミの後にでも（笑）
21:13 (IPUSIRON) まずグラフ理論のグラフですが、これは一般の人が認識しているようなグラフ、円グラフとか棒グラフのことではなく
21:13 (IPUSIRON) 単なる点と線で構成される図形のことです
21:14 (IPUSIRON) スライド７で点と線の定義がされています
21:14 (IPUSIRON) 線＝辺
21:14 (IPUSIRON) スライド7の図の例では、点というのは黒点のことで、辺というのはそれを結ぶ線のことですね
21:15 (IPUSIRON) 次に次数という概念があって
21:15 (IPUSIRON) これは点に何個の辺がくっついているのかということです
21:15 (IPUSIRON) これは図から点の次数を述べていますが、
21:16 (IPUSIRON) 逆に次数の式だけが書いてあって、そこからグラフを書くときとかにも使われます
21:16 (clothoid) 質問
21:16 (IPUSIRON) どぞ
21:16 (clothoid) 次数は行列とか？
21:16 (clothoid) なんか数学勉強するときに
21:16 (clothoid) いろいろ出てきますが，
21:16 (IPUSIRON) 数学の場面ではよく出てきますね＜次数という言葉
21:17 (clothoid) はい。ここでいう次数と何か関係があると思っていて良いですか？
21:17 (IPUSIRON) 例えば、x^3+x+3とかいう多項式の場合、これは3次（つまり、次数は3）とか
21:17 (IPUSIRON) 関係はないと思ってもらったほうがよいと思います
21:17 (clothoid) 了解しました。
21:18 (IPUSIRON) スライド9に入りますが、
21:18 (IPUSIRON) ここで述べているように、点がチーム名、辺がそれと対戦することを意味していたら、Pチームの次数が3といえば3チームと対戦するということになります
21:19 (nesys) このグラフ理論自体、離散数学の分野の1つなので、数学ABCなどで学ぶようなこととは全く関係がないと思っていいですよね？
21:19 (IPUSIRON) 数学ABCとは何でしょう？
21:19 (IPUSIRON) 高校数学のことかな？
21:19 (nesys) です
21:19 (IPUSIRON) 数学的には関連はしてくる可能性はありますよ
21:20 (IPUSIRON) 数学でまったく関係無いと思われていた分野が密接に関係していた例はたくさんあるので
21:20 (IPUSIRON) 多分今後のゼミで出てくるんではないでしょうか
21:20 (nesys) なるほど
21:20 (IPUSIRON) 例えば、指数関数と三角関数は密接ですし
21:21 (IPUSIRON) πと虚数が関係することもあります
21:21 (nesys) まだ資料1しか読んでいないので、このグラフ理論の数学的なところがよく分からないんですよね
21:21 (nesys) （数がある！以外でｗ
21:21 (IPUSIRON) そもそもグラフ理論は点と辺だけの世界であって、これをいかに応用するのかというところが問題かもしれませんが
21:21 (nesys) なるほど
21:21 (IPUSIRON) パズルみたいなもんですからね
21:22 (nesys) 了解です
21:22 (IPUSIRON) 次にスライド10。グラフが同形というのはまったく同じグラフのことを意味します
21:23 (IPUSIRON) 図の例のように単に線が曲線であっても、問題となるのは点に辺がつながっているかどうかという点なのです。
21:23 (kuroneko_) こんばんは。先ほど仕事から戻って、いまダッシュでログを読み終えて現在の位置にいます。続けてくださいm(__)m
21:23 (IPUSIRON) こんばんは
21:23 (IPUSIRON) 次にスライド12。グラフといっても色々あるので、代表的なものを紹介します。
21:24 (IPUSIRON) 多重辺というのは、単純に点と点の間が2つ以上の線があること
21:24 (IPUSIRON) ループは文字通り自らの点に戻ってくるような辺のこと
21:24 (IPUSIRON) そして、単純グラフというのは、こうした多重辺やループといったものがないグラフのことです
21:25 (IPUSIRON) これらは言葉の定義なので、後のゼミでわからない単語が出てきたら戻ってもらえるとよいかと思います
21:25 (IPUSIRON) 数学はほんと変な用語多いですからね…体とか虚数とか
21:26 (Defolos) ふむ
21:26 (clothoid) 不変量について質問
21:26 (IPUSIRON) ここで脱線話ですが、体という数学の分野がありますが、それに関する本が数学コーナーではなく、健康コーナーにあったというのを聞いたことがあります
21:26 (IPUSIRON) どぞ
21:27 (clothoid) スライドp.10で不変量の例がありますが，
21:27 (IPUSIRON) はい
21:27 (clothoid) この例で言うと，例えば　不変量＝点の数　ということですか？
21:27 (IPUSIRON) そうですね
21:27 (IPUSIRON) 辺の数も不変量ですね
21:28 (IPUSIRON) 不変量＝変わらない数のものということですから
21:28 (clothoid) それとも　「同形な2つのグラフに点の数という数を与える」という操作，写像という意味ではないのですね？
21:28 (clothoid) ×それとも　は余計
21:29 (IPUSIRON) ちょっと意味がわかりませんが、
21:29 (clothoid) あう。すみません。
21:29 (clothoid) 数の方のことってことで了解しました。
21:30 (piro-_-) 辺と点の数が変わらないということですよね？
21:30 (IPUSIRON) 2つの点を重ねるなどの操作をしないような写像ならば、写像する前のグラフと後のグラフは同形になってますね
21:31 (IPUSIRON) あくまでグラフ理論の中の同形の意味ですが
21:31 (clothoid) グラフ AとグラフBが同形だったとすると f(A)=f(B)=b　で bが不変量？fが不変量？
21:32 (clothoid) それとも全然違うっすか（--;
21:32 (IPUSIRON) A=f(A)のときに同形というわけですよね
21:33 (IPUSIRON) A：写像の前のグラフ、f（A）：ｆという写像をした後のグラフ　それが一致するとき、即ちA=f(A)のとき同形
21:33 (clothoid) それは f の定義によるのでは？＜A=f(A)のときに〜
21:33 (IPUSIRON) そうですね
21:33 (clothoid) f：グラフの点の数を教えよ　という定義だったら，
21:33 (IPUSIRON) はい
21:34 (IPUSIRON) それならあってます
21:34 (clothoid) AとBが同形のとき，f(A）=f(B)= c となりますよね
21:34 (IPUSIRON) bが不変量ですね
21:34 (IPUSIRON) はい
21:34 (clothoid) ｃga
21:34 (clothoid) cが不変量ですね
21:34 (IPUSIRON) cが不変量だと思います
21:34 (clothoid) 了解しました。
21:35 (IPUSIRON) まだ定義出てないので厳密にはいえませんが、多分そうだと思います
21:35 (clothoid) テキスト p3の
21:35 (IPUSIRON) はい
21:35 (clothoid) 注釈を見ると
21:35 (clothoid) 混乱して f　が不変量かと　思いました。
21:36 (IPUSIRON) なるほど
21:36 (IPUSIRON) fというのがグラフの点の個数を数えよという定義なら、fそのものはこの定義であって点の個数ではないから、不変量ではないはずです
21:37 (clothoid) 了解しました。
21:37 (clothoid) ありがとうございます。
21:37 (nesys) あれ資料#1のp3の下に「点数や変数」とありますが、辺数ですよね？
21:37 (kuroneko_) 「同じ値」というところがミソで、例えばAとBは両方とも単純グラフという意味で同じですが、それは値ではないので不変量ではない、という感じでしょうか？
21:37 (IPUSIRON) 辺の数も不変量の一種です＞nesysさん
21:38 (kuroneko_) あ、それは小生も思いました＞変数と辺数の誤植
21:38 (IPUSIRON) ああ
21:38 (IPUSIRON) ほんとだ（笑）
21:38 (clothoid) ありますが，前の文を見ると少し混乱していました。＞nesysさん
21:38 (IPUSIRON) 誤植ですね
21:38 (IPUSIRON) 辺の数が正しいと思います
21:38 (FreeSeven) ついでに言うとs12の例の点Pも違う気分
21:39 (IPUSIRON) 他に何が不変量なのがまだ謎ですが、それはまたの楽しみにしておきます
21:39 (IPUSIRON) どこですか？＞Freeさん
21:39 (IPUSIRON) スライド12の例の点Pですか？
21:39 (kuroneko_) わかりました＞不変量の楽しみ
21:40 (IPUSIRON) ああ
21:40 (FreeSeven) 多重辺の例の点Pと点Sじゃなくて点Qと点S？・・・
21:40 (IPUSIRON) ミスってますね
21:40 (kuroneko_) 間違い「点Pと点Sの間の辺であるQSは」正しい「点Qと点Sの間の辺であるQSは」ですよね？
21:40 (IPUSIRON) 例：点Qと点Sの間の辺であるQSは2本ある。これは多重辺である。
21:40 (IPUSIRON) が正しいです
21:40 (FreeSeven) どうでもよかったです、すいません。。
21:40 (Defolos) 了解
21:40 (clothoid) 了解
21:40 (IPUSIRON) いえいえまた誤植あったら教えてください
21:41 (mudai) 了解です。
21:41 (nesys) 逆に2つのグラフの点と辺が不変量だとして一致しても、その2つのグラフが同形とは限らないんですよね。（次数もあるため
21:41 (clothoid) 訂正版 後に上げてください>ipusironさん
21:41 (IPUSIRON) もちろん訂正版アップしておきます
21:41 (IPUSIRON) なるほど＞nesysさん
21:42 (IPUSIRON) 必要十分ではないってことですね
21:42 (nesys) はい
21:42 (IPUSIRON) 同形である必要としてはもちろん点とか辺の不変量が一致しなければなりませんが、それだけで同形とはいえない（十分ではない）ということですね
21:42 (IPUSIRON) 次スライド13にはいります
21:43 (IPUSIRON) 今度は辺に矢印がついているグラフです。これを有向グラフといいます　有効と間違えやすいので注意
21:43 (IPUSIRON) といってるのに間違えてますね（笑）
21:43 (Defolos) ＾＾；
21:43 (nesys) ほんとだｗ
21:43 (clothoid) ｗ
21:43 (carbon0) ｗ
21:44 (IPUSIRON) もちろん矢印がついているので、その矢印順に移動したときが重要なわけで、そのときの辺の列を「道」といいます
21:44 (IPUSIRON) みす　道ではなく歩道です
21:45 (IPUSIRON) 道というのは、歩道であってなおかつ一度通った点は通らないときのことです
21:46 (nesys) 有向の辺と有向でない辺が同時に存在するグラフってありですか？
21:46 (IPUSIRON) そして閉路というのは元の点に戻るような道のことです
21:46 (IPUSIRON) あってもいいと思いますが、どういった場面に対応するのかをいわれると難しいですね
21:47 (nesys) データベース設計などで、idの関連付けで有向にして、その他をただの辺にするとか
21:47 (IPUSIRON) なるほど
21:47 (Defolos) 道は歩道の特別な場合と考えていいのですか？
21:47 (IPUSIRON) そうですね＞Defolosさん
21:48 (Defolos) なるほど
21:49 (IPUSIRON) ちょっと謎なのですが、閉路の定義で資料4ページではQ→S→T→Qのような道とありますが
21:49 (IPUSIRON) 道なのか歩道なのかちょっと調べてなくてわかってません
21:49 (IPUSIRON) 多分歩道でもよさげですが
21:50 (IPUSIRON) そもそもQ→S→T→Q自体が歩道ですので
21:50 (Defolos) T→Qは順路に逆らってるように見えるのですが良いのでしょうか
21:50 (nesys) Q→Sで道はありえないのか、それとももQ→S→T→Q全体を見て歩道なのか
21:50 (carbon0) 図2でのことのようです
21:51 (nesys) ミス、全体を見て道なのか
21:52 (IPUSIRON) ちょっとDefolossannno
21:52 (IPUSIRON) さんのいってるのはどこでしょう？
21:52 (Defolos) あ、テキストの4ページの図4でした
21:53 (Defolos) すいませんでしたー、ミスです
21:53 (nesys) 図4のTQの向きがQ→Tになっているが、T→Qとして回れるのかということですよね
21:53 (IPUSIRON) ほんとだ　テキストのおかしいですね
21:53 (IPUSIRON) 周れないはずだと思います
21:53 (carbon0) 図2の右側の図が閉路であって図4は違うのではないでしょうか？
21:53 (nesys) この資料ところどころ抜けてますねぇ
21:54 (IPUSIRON) Tで行き止まりになってますしね（笑）
21:54 (Defolos) 道や歩道などの概念は有向グラフにのみ出てくる概念なのですか？
21:54 (IPUSIRON) 誤植直すのも勉強になります（笑）
21:54 (dotdister) P3の図２の右のグラフの事だと思います＞閉路
21:54 (IPUSIRON) 定義次第だからなんともいえませんが、＞Defolosさん
21:55 (IPUSIRON) ああ
21:55 (clothoid) 有向グラフでは，矢印の方向にのみしか歩けないというわけではないのでは？
21:55 (IPUSIRON) 例題1.1の２を参照ってかいてますね　すぐしたに
21:55 (IPUSIRON) ということは閉路は有向グラフとはかぎらず、もどってくるようなのなら普通のグラフでもOKということですね
21:56 (Defolos) ふむ
21:56 (Defolos) なるほど
21:56 (dotdister) でも、戻ってくる、ということは向きが与えられてないと無理ではないでしょうか？
21:56 (IPUSIRON) 戻ってくるというか点と線でループになっているといったら正しいのでしょうか
21:57 (nesys) それだと、今まで出ているグラフの全てが閉路グラフということに？
21:57 (dotdister) そういうことですか。納得です。
21:57 (IPUSIRON) そですね＞nesysさん
21:57 *recit join #akademeia (~recit@c027096.net219124.cablenet.ne.jp)
21:57 *clothoid mode +o recit 
21:57 (IPUSIRON) でも単なる直線だけのときも一応グラフですよ
21:57 (nesys) はい
21:58 (IPUSIRON) こんばんは＞recitさん
21:58 (FreeSeven) 質問ノ
21:58 (Defolos) 直線だけだと閉路グラフにはならないわけですね
21:58 (FreeSeven) こんばんわ
21:58 (asuno) こんばんは
21:58 (nesys) こんばんわー
21:58 (Defolos) こんばんわ
21:58 (mudai) こんばんは
21:58 (IPUSIRON) 単に閉路といったときは道のことをさすぽいですね
21:58 (kuroneko_) こんばんは
21:58 (dotdister) こんばんは。
21:58 (IPUSIRON) どぞ＞Freeさん
21:59 (clothoid) （点だけでもグラフです・・・）
21:59 (IPUSIRON) ああでも有向グラフならもしかしたら閉路を含まないグラフもたくさんあるとおもいますよ＞nesysさん
21:59 (FreeSeven) 有効グラフで矢印の無い辺を一緒に使ったりする事ってあるんですかね？
21:59 (FreeSeven) それとも両方の端に矢印をつけるとか？・・・
21:59 (IPUSIRON) さっきデータベースの例で説明してくれたようにあるぽいですね
22:00 (nesys) あぁそうですね
22:00 (FreeSeven) ぬ、、、すいません、かぶったっぽいですね、。。
22:00 (IPUSIRON) 両方矢印つける＝2本別々の矢印つけると同じですね
22:00 (clothoid) それは次数が異なるから同じではないのでは？＞IPUさん
22:00 (IPUSIRON) ああ、でも辺の数が変わるから微妙には違いますね
22:01 (IPUSIRON) その通り。同じではないです（笑）
22:01 (clothoid) はい。
22:01 (recit) こんばんは、
22:01 (IPUSIRON) 次のスライドに有向グラフの例を挙げてみました
22:02 (IPUSIRON) ありきたりですけど、じゃんけんで考えてみました
22:02 (IPUSIRON) そもそも矢印がある＝何か意味をつけるということなので、ここでは勝ち負けという意味があります
22:03 (IPUSIRON) スライド15　グラフが固まってるかどうかで連結グラフか非連結グラフかと区別します
22:03 (IPUSIRON) 固まる＝全部繋がっている
22:03 (IPUSIRON) そして、成分とは非連結グラフの数です。もちろん連結グラフなら成分は１です
22:04 (Defolos) 成分の数も前述の不変量のひとつでしょうか
22:04 (IPUSIRON) かもしれませんね
22:04 (nesys) この3つの図をそれぞれバラバラなグラフではなく、全体が1つのグラフとして見るわけですね
22:04 (IPUSIRON) そそ
22:04 (Defolos) なるほど
22:05 (IPUSIRON) 3つバラバラのセットのグラフ
22:05 (IPUSIRON) スライド16　オイラーとかハミルトンとかは超有名数学者で、彼らの名前が付いた特別なグラフがあります
22:05 (IPUSIRON) オイラーグラフはすべての辺を通ることができるグラフ
22:05 (nesys) 資料4pの下の図では、わざわざ境界線を設けたことから別のグラフなのかと勘違いしましたよｗ
22:06 (Defolos) 同じく＾＾；
22:06 (IPUSIRON) ハミルトングラフはすべての点を通って出発点に戻れるグラフです
22:06 (IPUSIRON) 自分も最初勘違いしましたよ
22:06 (IPUSIRON) 一般的な一筆書きはオイラーグラフです
22:07 (IPUSIRON) そもそもグラフ理論自体が一種の一筆書きとかケーなんとかの橋の議論とかから登場したわけですから
22:07 (Defolos) ケーニヒスベルグですね＾＾；
22:07 (IPUSIRON) それです（笑）
22:07 (clothoid) ケーなんとかｗ
22:07 (IPUSIRON) 一般向けの数学本とかによく登場しますね＜ケーニヒスベルグの橋
22:08 (Defolos) アレを必死で一筆書き使用とした私は・・・・
22:08 (IPUSIRON) http://homepage3.nifty.com/sugaku/hasiwatari.htm
22:08 (nesys) 現地に行ってみたいですねｗ
22:08 (IPUSIRON) ここに載ってますね
22:08 (IPUSIRON) ケーニヒスベルグの橋もオイラーグラフかどうかの問題ですね
22:09 (IPUSIRON) 解く方法とか関連する定理はいずれゼミで登場すると思います
22:09 (nesys) ケーニヒスベルクの橋は結局オイラーグラフなんですか？
22:10 (Defolos) ではないのでは？
22:10 (nesys) あ、先ほどのページに違うとありますね
22:10 (IPUSIRON) オイラーグラフではないことが証明されてると思います
22:10 (kuroneko_) 一筆書きが出来ない＝オイラーグラフではない でよいと思います。
22:10 (kuroneko_) かぶった(爆)
22:10 (IPUSIRON) 次はスライド17　木とは、ぶどうぽいグラフのことです
22:11 (Defolos) ブドウ・・・
22:11 (IPUSIRON) 厳密には、どの2点の間にも道が1本しかない連結グラフのこと
22:11 (IPUSIRON) ブドウってグラフ理論では木になるわけですね（笑）
22:11 (mudai) 果物・・w
22:11 (IPUSIRON) コンピュータの世界や自然界には木の構造（木構造）のものがたくさんあります
22:11 (nesys) ディレクトリ構造ですね
22:12 (IPUSIRON) そです
22:12 (nesys) ショートカットはどうなるんだろ…？
22:12 (Defolos) ヒープなんかですね
22:12 (IPUSIRON) ショートカットを考えたらダメですね（笑）
22:12 (nesys) おｋｗ
22:12 (Defolos) ＾＾；
22:13 (IPUSIRON) 実際木構造はファイル構造に関連があって、次のスライドのURLとかみるとわかりますが
22:13 (FreeSeven) ホスト中心的なP2Pのあれですね
22:13 (IPUSIRON) 色つきのとかいろいろあります
22:13 (IPUSIRON) ですね　そもそもP2P自体がグラフ理論と相性よさげだと思います
22:13 (Defolos) コピペはできないのですね
22:13 (IPUSIRON) http://sunak2.cs.shinshu-u.ac.jp/~miyao/AL/Class/binary_search_tree.pdf
22:14 (Defolos) ありがとうございます
22:14 (nesys) P2Ptte
22:14 (IPUSIRON) アルゴリズムとか勉強すると必ず登場するはずです。これ
22:14 (nesys) 木構造じゃないような・・？
22:14 (IPUSIRON) え　なってませんか？
22:15 (nesys) あれは1つ1つは木構造のようになっていますけど、1つのサーバーに複数の辺がつながることがあるような
22:15 (FreeSeven) 某MXとかそうだった記憶、。。。
22:15 (mudai) 俺も違うような・・きがします。
22:15 (FreeSeven) ぬぐ、、、多数決で違うで、、、すいません。。。m(_ _)m
22:15 (nesys) nyなんかはサーバーであると同時にクライアントですから
22:15 (kuroneko_) MXだと、親に子がぶら下がる構造になっていると思いましたので、基本的に木構造かと思っていましたが
22:16 (nesys) サーバーとして木構造の始まりであると同時に他の木構造の配下でもあります
22:16 (kuroneko_) 「1つのサーバーに複数の辺がつながることがある」ことを思い出すと、確かに違いそうですね
22:16 (kuroneko_) nyはちょっと存じ上げませんm(__)m
22:16 (IPUSIRON) 一般的にP2Pは木構造にはなってませんね　あくまでグラフと関連があるってことです
22:16 (FreeSeven) 根元はMXサーバだった記憶、。。
22:16 (Defolos) なるほど
22:17 (FreeSeven) なる、、、大変すいませんでした。。。_no
22:17 (kuroneko_) なるほど、そうだと思います＞　あくまでグラフと関連がある
22:17 (IPUSIRON) これで一通り定義が終わって、後は練習問題だけです
22:18 (IPUSIRON) 問1は
22:18 (nesys) あーなんか人工知能のニューロンもグラフ理論に関係ありますね
22:18 (IPUSIRON) 化学知っている人ならわかると思いますが、これもグラフに関連するってことで問題になってるだけだとおもいます
22:18 (IPUSIRON) もろあるとおもいます
22:19 (Defolos) たぶんかなりありそうです＞ニューラル
22:19 (IPUSIRON) 問2の問題スペルミス　JohhではなくJohnですね
22:20 (IPUSIRON) 問2は矢印を組み合わせていくだけです。やりかたは最初2つの点とその矢印付き辺を書いて、後はそれらを組み合わせます
22:20 (Defolos) 細いところから関係を作っていくと楽だったのですね・・・
22:20 (kuroneko_) Joeもてない…(笑)
22:20 (IPUSIRON) （笑）
22:20 (mudai) それはいわない約束。w
22:20 (Defolos) ＾＾；
22:20 (carbon0) 気づかなかったｗ
22:21 (IPUSIRON) 次に問3ですが、これは簡単だとおもってたら、結構何度も考えてやっともれなく計算できました
22:21 (Defolos) 質問
22:21 (nesys) 次数からグラフ作るのめんどそうですね
22:21 (IPUSIRON) 図にするのが一番時間かかりました（笑）。是非一度問３は自分で解くことをお勧めします。
22:22 (IPUSIRON) どぞ＞Defolosさん
22:22 (Defolos) この問3はしらみつぶしにやるしか解法はないのでしょうか
22:22 (IPUSIRON) 最初自分もしらみつぶしにやろうとおもったんですが、
22:22 (Defolos) かなり時間かかったのですがTT
22:22 (IPUSIRON) よく考えるとfは1つしかないとかを考えるとそれほど多くなりませんよ
22:23 (IPUSIRON) 実際の解法もスライドのとおりでいけるはずです。もっとよい解き方あるかもしれませんが
22:23 (Defolos) なるほど
22:23 (IPUSIRON) ポイントは最初に次数の大きいものから考えたことでしょうか
22:24 (IPUSIRON) 頭いいひとはすぐ解いちゃうかもしれませんけど
22:24 (Defolos) 頭悪いです(ノ∀｀)
22:24 (mudai) 正直ずっと図を書いて悩むしか思いつきませんでした・・orz
22:24 (IPUSIRON) 次に１．２の問１ですが、これは１．１の問２のときの矢印ないバージョンなだけですね
22:24 (IPUSIRON) 数学の場合
22:25 (IPUSIRON) わからないときに悩むより実際に手を動かして、実験したほういいですよ
22:25 (Defolos) なるほど
22:25 (IPUSIRON) そうすると規則性（一般性）に気付くことがあります
22:25 (clothoid) 色々解法を思いつくのですが途中で挫折します・・・
22:26 (mudai) 図を立体にして見方を変えたら・・５とおりとか？
22:26 (IPUSIRON) 問２は単にまた矢印をつくって、それを同じ点同士をくっつければよいだけですね
22:26 (IPUSIRON) 答えは5通りです＞さきほどの問３
22:26 (IPUSIRON) グラフは平面にかかれてますが、別に空間に立体図のように考えても同形なので
22:27 (IPUSIRON) そのようにしたほうが考えやすければ問題ないですね
22:27 (IPUSIRON) 自分は立体は頭こんがらがりますが
22:27 (kuroneko_) そういえばそうですね＞は平面にかかれてますが、別に空間に立体図のように考えても同形
22:27 (kuroneko_) 気がつかなかったです(爆)
22:27 (IPUSIRON) 別に地球儀の上に描いてもいいわけですね
22:28 (mudai) なるほど・・
22:28 *nisi_ join #akademeia (~nisi@p2233-ipad209kobeminato.hyogo.ocn.ne.jp)
22:28 (IPUSIRON) 次は練習問題　これらは答えなかったので考えてみました　もしかしたら間違っている可能性あり
22:28 (IPUSIRON) こんばんは＞西さん
22:28 (nesys) こんばんわー
22:28 (Defolos) こんばんはー
22:28 (kuroneko_) こんばんは
22:28 (piro-_-) こんばんは
22:28 (carbon0) こんばんは
22:28 (dotdister) こんばんは。
22:28 (IPUSIRON) 木の例として、DNSと文法の図を考えてみました
22:29 (mudai) こんばんはー
22:29 (nisi_) あ、こんばんわー
22:29 (IPUSIRON) ちなみにDNSの図に２ｃｈとかのドメインありますが、どこかから持ってきた画像なので気にしないでください
22:29 (Defolos) ＾＾；
22:29 (clothoid) （練習問題の答えは次の回の最初にあります（なので，掲示板の質問になりました）　）
22:29 (nesys) ドメインのルートにある.は何ですか？
22:30 (IPUSIRON) 一番根っこのドメインサーバーですよ
22:30 (IPUSIRON) まず最初にこれ考えないとnetとかcomとか繋がりませんよね？
22:30 (nesys) あぁこれサーバーをあらわしているんですね
22:31 (IPUSIRON) それで問題は次の練習問題２ですが
22:31 (Defolos) 文法の例の名詞の後のピリオドはいらないのでは・・・
22:31 (IPUSIRON) なるほど　いらないですね
22:31 (kuroneko_) あ、練習問題1の文法について何ですが、いいでしょうか？
22:31 (IPUSIRON) どぞ
22:32 (kuroneko_) 「Time flies like an arrow.」を、このように正しく解釈できれば問題ないのですが、機械翻訳にかけたら
22:32 (nesys) 英文法に関して言えば、名詞と動詞の間に辺が引けそう（単数のsの判定として）
22:32 (kuroneko_) 「時ハエたちは矢に似ている」と、間違った解釈をしたソフトがあったそうで、これは
22:33 (kuroneko_) 「木構造を取り違えた」例となり得ますか？
22:33 (kuroneko_) 「Time flies」「like]
22:33 (kuroneko_) [
22:33 (kuroneko_) 「an arrows]
22:33 (IPUSIRON) 翻訳ソフト自体が木構造に分割して考えているかどうかはプログラミング依存だとおもいますが
22:34 (kuroneko_) みたいな木構造にしちゃったみたいです。ヘンな改行ですみません
22:34 (kuroneko_) ふむふむ
22:34 (IPUSIRON) 木構造の奥深くだけで考えると、意味がつうじなくなりますし、
22:34 (kuroneko_) はい
22:35 (IPUSIRON) 浅いところだけで考えてもおかしくなりそうなので、翻訳ソフトは奥と浅いところのどこを見るかで精度かわったりするのかも
22:35 (nesys) [time - files] - [like]のように2つの点を1つの点と考えて辺を引く必要性もでてきますね
22:36 (IPUSIRON) 時ハエは矢が好きだとかもありえますよね
22:36 (kuroneko_) あ、そっちでした「時ハエは矢を好む」でしたm(__)m
22:36 (IPUSIRON) あくまでこのグラフの図は
22:37 (kuroneko_) なんとなく納得しました＞ [time - files] - [like]のように2つの点を1つの点と考えて辺を引く必要性もでてきますね
22:37 (kuroneko_) はい
22:37 (nesys) 文の場合、単語単語を全体から辺を引っ張って意味を推定しないといけないんだ
22:37 (nesys) 厳密な文のグラフは大変そう…
22:37 (IPUSIRON) 多分グラフ理論とかと関係しない技術とかも並行して使われて相ですね
22:38 (IPUSIRON) で最後の問題ですが、そもそも2部グラフってなんだろとおもって調べました
22:38 (IPUSIRON) 正直問題文の意味がわからかったので
22:38 (Defolos) 同じく〜(￣∀￣；)
22:39 (IPUSIRON) スライド44のように、単にグループを上下にわける（ここでは2部だから）グラフのようです
22:39 (IPUSIRON) そして同一グループ同士は繋がれないという性質をもつようです
22:39 (nesys) なるほど
22:39 (Defolos) ふむ
22:39 (IPUSIRON) だから上下のグループにわけると、下のグループの2点が繋がることはダメということですね
22:40 (IPUSIRON) 問題文では閉路を考えると、辺の数が奇数にならないということなので
22:40 (Defolos) ３部グラフなんてものも存在するのでしょうか
22:40 (IPUSIRON) 実際に実験するとわかりますが、
22:40 (IPUSIRON) 下の点→上の点→…→（元の）下の点
22:40 (IPUSIRON) となって偶数回ないと下に戻ってきませんよね
22:41 (IPUSIRON) 3部グラフとかも普通にあると思いますよ
22:41 (IPUSIRON) スライド45では単純な例をあげてますが
22:42 (IPUSIRON) 八の字みたくなって辺の数は偶数になります。証明になってませんがすみません
22:42 (IPUSIRON) あくまで例を挙げただけであって実は証明になってません
22:42 (clothoid) 証明は難しそうですが，簡単なのですか？
22:43 (IPUSIRON) どうやって証明するか全然見当つきません
22:43 (kuroneko_) いえ「見れば分かる」の典型的なやつじゃないでしょうか？理屈としても「下の点→上の点→下の点→上の点という4つの線が必要」で、証明までは行かなくても
22:43 (IPUSIRON) 多分証明するとしたら数学的帰納法とかでしょうか？それとも背理法とか使うのかな？
22:43 (IPUSIRON) 奇数の辺の閉路があったと仮定して矛盾を示せれば背理法成功。それでもピンときませんが
22:44 (kuroneko_) 「ということを示せ」であれば、十分通用するんじゃないかと思います。小生は「こんなわかりやすい方法があったのか」と少々驚きました
22:44 (IPUSIRON) でも数学の試験だったら部分点ですよ（笑）
22:44 (Defolos) Σ（゜д゜ｌｌｌ）
22:44 (mudai) いまだに問題の意味がわからない・・
22:44 (IPUSIRON) でもこうやって実験をやることによって証明方針とかも見つかることがあります
22:44 (IPUSIRON) 問題の意味は
22:45 (IPUSIRON) 2部グラフ理解できました？＞無題さん
22:45 (mudai) はい。
22:45 (nesys) 上から下に来るときの辺の数は必ず奇数になって、さらに閉路にするためにはスタート地点に戻らないといけないってことから、奇数+1で必ず偶数になる感じですね
22:45 (IPUSIRON) 今n=7だから、上のグループの点が7個、下のグループが7個あるのです
22:46 (IPUSIRON) そういった状況において、
22:46 (mudai) �ｽｶ�ｾ橸ｽｯ�ｾ��ｾ晢ｼ��ｼ��ｽｶ�ｾ橸ｽｯ�ｾ��ｾ晢ｽｶ�ｾ橸ｽｯ�ｾ��ｾ晢ｼ��ｼ�
22:46 (mudai) 理解できましたw
22:46 (IPUSIRON) 閉路グラフを作ったとき、辺の数が奇数にはなりえないことを証明せよということです
22:46 (Defolos) 示す＝証明する　ですか？
22:47 (IPUSIRON) そうです
22:47 (Defolos) なるほど
22:47 (IPUSIRON) 実例をあげても他の例で定理が崩れる可能性があるので、証明するというのと例を挙げるのとでは意味が異なりますね
22:47 (Defolos) ふむふむ
22:47 (IPUSIRON) 太陽は必ず朝東から登りますよね
22:48 (nesys) nの数に関係なく、必ず偶数になることを証明したらいいんですね
22:48 (IPUSIRON) それは経験的に知っているわけですが、それが1万回そうであっても、明日そうでない可能性あります
22:48 (Defolos) はい
22:48 (kuroneko_) あちゃー、小生は「証明する＝厳密にやる」「示す＝ある程度の精度があればいい」だと思ってましたが_|￣|○＞「示す＝証明する　ですか？」「そうです」
22:48 (IPUSIRON) 本当はｎの数は関係無いですね＞nesysさん
22:49 (IPUSIRON) 物理学とかは実験によってその説が正しいことを実証しますが、数学は定義や公理からスタートして証明します
22:49 (Defolos) 私は「示す＝例を挙げる」だと思ってましたσ(￣▽￣i) 
22:49 (IPUSIRON) 実証と証明は違います
22:49 (Defolos) なるほど
22:49 (nesys) 全ての点の数=n*2（つまり偶数)
22:50 (nesys) それで2つの点の間に辺陬が1つで
22:50 (nesys) さらに最後にスタートに戻らないといけないで
22:50 (nesys) ってあれ、おかしいな
22:50 (nesys) 忘れてくださいｗ
22:50 (Defolos) ＾＾；
22:50 (mudai) っw
22:51 (IPUSIRON) 一応終わりましたが、質問あればどうぞ
22:52 (carbon0) 連結グラフについて質問です
22:52 (IPUSIRON) ないのかな？
22:52 (IPUSIRON) どぞ
22:52 (carbon0) テキストにはその2つの点も道で結ばれているグラフが連結グラフとありますが
22:52 (carbon0) その→どの
22:53 (carbon0) 図5はなぜ連結グラフではないのでしょうか
22:53 (carbon0) どの2つの点も道で結ばれている気がするのですが
22:53 (IPUSIRON) 例えば、
22:53 (IPUSIRON) 前のページの図３で考えてみましょう
22:54 (carbon0) はい
22:54 (IPUSIRON) このときどの2点でもいいわけなので、ランダムにPとRを選んだとしますよね
22:54 (IPUSIRON) どの＝任意＝どれでもOKという意味です
22:54 (nesys) 図5の2つのグラフを1つのグラフだと見ればいいんですよ
22:55 (IPUSIRON) PとRは離れているけど、辺の列＝歩道で繋がりますよね
22:55 (IPUSIRON) ここでは道にもなっていますが　色んな道順はあります
22:56 (kuroneko_) （P-R-Rとか、P-S-Rとか ですね？）
22:56 (kuroneko_) （むむ、P-Q-Rとか、P-S-Rとか、の間違いでした）
22:57 (IPUSIRON) ですね
22:57 (IPUSIRON) nesysさんがいうように、あまり難しく考えずに
22:57 (IPUSIRON) 単に全体的にグラフが繋がっているかどうかです
22:57 (carbon0) 図5は2つのグラフではなく、1つのグラフであって、線でつながっていないだけですか？
22:57 (IPUSIRON) そです
22:58 (IPUSIRON) 2つのグラフがあるようにみえますが
22:58 (IPUSIRON) 実は非連結グラフひとつがあるのです
22:58 (Defolos) 真ん中の破線が邪魔な気がしますよね＾＾；
22:58 (nesys) 左のグラフと右のグラフは線で繋がってないから非連結グラフということですね
22:58 (carbon0) ありがとうございます！>>ipusironさんnesysさん
22:58 (mudai) なるほど！！っw
22:58 (kuroneko_) （江戸時代風に）「じゃあ、おめえさん、なんだい、図5でTとQを結べるかい？できねぇだろ？んだから非連結グラフなんでい」ってトコでしょうか(笑)
22:58 (Defolos) ＾＾；
22:59 (carbon0) w
22:59 (IPUSIRON) 非連結グラフで、成分が2つってことですね
22:59 (mudai) この破線はふたつはぶった切ったぜ！！ってことなんですねw
22:59 (IPUSIRON) 今日初めてでしたが、もう2時間もやったんですね
22:59 *IPUSIRON mode +o nisi_ 
22:59 (Defolos) そのようですねぇ
23:00 (nesys) 結構資料1以上の質問をしましたからねｗ
23:00 (IPUSIRON) 次回はclothoidさんですね
23:00 (mudai) いやー笑いありなんですねw
23:00 (clothoid) あ
23:00 (clothoid) はい。
23:00 (Defolos) 非常に充実していました
23:00 (kuroneko_) あ、あと小生が気がついて重要だと思いつつ、皆さんにはどうでも良い情報かもしれませんが
23:00 (IPUSIRON) 2,3週間後ぐらいに予定後ほど組みましょう
23:01 (clothoid) 了解。google カレンダーに予定は早めに入れておきます＞IPUさん
23:01 (IPUSIRON) 了解しました
23:01 (IPUSIRON) とりあえず今日はお疲れ様でした。資料やログはアップしておきます
23:01 (clothoid) スライド作らないと^^;
23:01 (kuroneko_) 「オイラーグラフは、同じ点を二度通っても良いが同じ辺を二度通ってはならない」「ハミルトングラフは同じ点は一度しか通れないが、通らない辺があっても良い」という定義に
23:01 (IPUSIRON) スライド自分で作らなくても
23:02 (IPUSIRON) 例のサイトにあるじゃないですか。あれつかっても問題ないですよ
23:02 (kuroneko_) なんとなくスカッとしたものというか、潔さを感じました(笑)
23:02 (clothoid) そか。みてみますー＞IPUさん
23:03 (mudai) 俺は今まであのサイトの資料をプリントアウトしてログよんでましたw
23:03 (IPUSIRON) とりあえず今日は解散です。ありがとうございました。適当に雑談でもしていってください（笑）