20:59 (clothoid) ほとんど前回の復習なので問題ないと思いますよ＞nesysさん
21:00 (nesys) 了解です
21:00 (clothoid) 分からないことがあれば，がんがんつっこんでください＞Defolosさん
21:00 (nesys) では、宜しくお願いします！
21:00 (Defolos) はいー
21:00 (mudai) スタートですかね
21:00 (IPUSIRON) 時間ですね。どうぞ
21:00 (clothoid) はい
21:00 (clothoid) よろしくお願いします。clothoidです。風邪で明日から大阪ですｗ
21:01 (clothoid) 資料開いてください。
21:01 (mudai) あい
21:01 (dotdister) おーけーです。
21:01 (clothoid) まず，p.3
21:01 (clothoid) 今回の講義の目的です。
21:01 (clothoid) まぁ読んだとおりですが，少し数学チックな言葉を用いて
21:02 (clothoid) 前回よりもより厳密に，正確に言葉を定義しよう
21:02 (clothoid) というのが，今回の目的です。
21:02 (nesys) 数学チック…本格的になってきましたね
21:02 (mudai) �ｽｶ�ｾ橸ｽｸ�ｽｶ�ｾ橸ｽｸ
21:02 (clothoid) mudaiさんの発言が化けて見えないのですが・・・
21:02 (mudai) 半角だと無理みたいですね・・申し訳ないです。
21:03 (clothoid) いえいえ。
21:03 (clothoid) じゃ次，p.6
21:03 *IPUSIRON mode +o carbon0 
21:03 *IPUSIRON mode +o asuno 
21:03 (clothoid) 「点集合」の定義です
21:03 (clothoid) グラフの点ばかりを抜き出して，並べたのが点集合です。
21:03 (clothoid) 下の例では，u, v, w, zが点なので，
21:04 (clothoid) {u, v, w, z}が点集合ということになります
21:04 (clothoid) 元資料で，点集合はV(G)と書くようです。
21:04 (clothoid) 次，p7
21:04 (clothoid) 辺集合E(G)です
21:05 (clothoid) グラフから辺ばかりを集めた集合です。
21:05 (clothoid) 例を見ていただければ，分かると思うので，次，p.8
21:05 (Defolos) 配布資料ではＶ（Ｇ）になってませんか？
21:05 (IPUSIRON) これ7ページのところV(G)じゃなくてE（G)ですよね
21:05 (clothoid) あ
21:05 (clothoid) そうですね。
21:05 (mudai) ほんとだ・・
21:05 (clothoid) typoです。
21:06 (clothoid) すみません。E(G)です。
21:06 (Defolos) 了解ですー
21:06 (IPUSIRON) 後で修正したのは私に送ってもらえれば、SASのページに修正版追加しますね
21:06 (clothoid) メモ：p.7にミスプリ
21:06 (clothoid) 了解しました＞IPUさん
21:06 (clothoid) で，次，p8「接続関数」です
21:07 (clothoid) 一つの辺に対し，頂点の対を対応させる関数のことです。
21:07 (nesys) なるほど。点と辺の接続関係を関数としているのですね
21:08 (clothoid) 例えば，下の図で，e1という辺に対しては，uとvが頂点ですから，ψG(e1)=uvというふうになります。
21:08 (clothoid) はい＞nesysさん。
21:08 (talon_) ふむふむ
21:08 (clothoid) 次，p.9，「単純グラフ」です。
21:09 (clothoid) 多重辺やループを含まなく，かつ，ぜんぶつながってるグラフのことです。
21:09 (Defolos) リンクは線ですよね
21:09 (clothoid) これは前回やりましたね。正確に書くとスライドのようになります。
21:09 (clothoid) そうです＞Defolosさん
21:09 (clothoid) 次，p.10
21:10 (clothoid) 一般グラフ。単純グラフでないものです。
21:10 (clothoid) 次，p11
21:10 (clothoid) 同型。
21:10 (clothoid) これも前回やりました。
21:11 (clothoid) 辺や点を動かして，同じ形にできれば同型ってことです。
21:11 (IPUSIRON) 辺が輪ゴムのようになってると考えればいいわけですね
21:11 (talon_) なーる
21:11 (Defolos) なるほろー
21:11 (clothoid) そうですね。補足有難う御座います＞IPUSAN
21:12 (clothoid) 二つのグラフが与えられたとき，同型であるかどうかを見極めるのは
21:12 (clothoid) 簡単じゃないと思いますが，これから，色々，学んでいくと思いますので・・・。
21:12 (clothoid) 次，p12。同型写像です。
21:13 (IPUSIRON) ここは最初の山場ぽいですね
21:13 (clothoid) いきなり，数学っぽいですが，スライドの意味は分かりますか？
21:13 (Defolos) ごめんなさいちょっとわかりにくいです
21:13 (clothoid) 了解です。＞Defolosさん。では，p.13の例から説明したいと思います
21:14 (IPUSIRON) まず数学記号の意味から説明するとよいかもです
21:14 (Defolos) すいませんです
21:14 (clothoid) p.13で，G1とG2という二つのグラフを考えます。
21:14 (clothoid) 答えから言うと，この二つのグラフは同型です
21:14 (nesys) p12のG1、G2とはp13のことですか？
21:15 (clothoid) 頭の中で，輪ゴムだとおもいウネウネ動かして同型であることを確認してください。
21:15 (Defolos) はい
21:15 (clothoid) 違います。p12のG1とG2は一般的なグラフの場合で，p13は具体例を考えています＞nesysさん。
21:15 (nesys) なるほど
21:16 (clothoid) p.13を見て，同型であることが分からない方，いらっしゃいますか？
21:16 (clothoid) 紙に書いてみると，良いかもしれません。
21:17 (mudai) VとYを横にびーーーーっとひっぱってっ縦にした感じですよね？
21:18 (mudai) VとYを縦にです・・・
21:18 (mudai) ひっぱって横でした・・
21:18 (talon_) Vを下に、Yを上とか？
21:19 (mudai) はい・・
21:19 (clothoid) どの点とどの点が対応して，どの辺とどの辺が対応するのかを
21:19 (clothoid) 考えてみてください。
21:19 (nesys) G1の点を1つ1つG2の点に当てはめていって分かりましたー
21:19 (mudai) ああ・・
21:19 (clothoid) たとえば，点uは点lに対応します。
21:19 (Defolos) はい
21:20 (clothoid) よろしいでしょうか？
21:20 (mudai) あ理解できました。
21:20 (clothoid) 答えを書くと，点u→点l　,
21:20 (clothoid) vがm，wがn
21:21 (clothoid) といった感じになります。
21:21 (clothoid) 辺の場合であれば，辺uxが辺lpに，
21:21 (clothoid) 辺uyが辺lqに対応するといったぐわいです。
21:22 (clothoid) p.14を見てください。
21:22 (clothoid) θを次のように定める　と書いてあり，下に二行書いてあると思います。
21:22 (clothoid) 数式が。
21:23 (IPUSIRON) θは点の写像、φが辺の写像ですね
21:23 (clothoid) この数式二行の意味は，今まで，みなさんが頭の中で，どの点とどの点が対応しているものか
21:23 (Defolos) uをlと対応しているとするとvはm
21:23 (Defolos) に対応ってかんじでしょうか？
21:23 (clothoid) ということを表したって感じです
21:23 (Defolos) なるほど
21:24 (clothoid) そうですね＞IPUさん
21:24 (clothoid) どうでしょうか？＞mudaiさん
21:24 (mudai) 今のところ付いてこれてます。
21:24 (clothoid) 了解です。
21:24 (clothoid) 四行目にうつって，φの場合ですが，
21:24 (clothoid) こちらは，先ほどIPUさんがおっしゃったように，
21:25 (clothoid) 辺と辺の関係を表しています。
21:25 (clothoid) ここまでで，分からない方，いらっしゃいますか？
21:25 (Defolos) 1対１写像というのは辺の写像のことですか
21:26 (nesys) うーん…写像の意味がよく分かりません…
21:26 (asuno) 同じく　>写像
21:26 (clothoid) p.5を見てください＞defolosさん，nesysさん
21:26 (nesys) →この記号が写像なのは分かりましたが、その根本の意味がよく
21:26 (clothoid) ＞asunoさん
21:26 (mudai) 点を別の点に写すって感じですか？
21:26 (talon_) 行列の一次変換に似ているような気がしますが。。。
21:26 (IPUSIRON) 根本的な意味というか単なる「対応させる操作」ですよ
21:27 (carbon0) 関数って言ったほうが分かるかも
21:27 (clothoid) 写像は「関数」だと思ってもらって大丈夫です
21:27 (nesys) なるほど。対応付けということか
21:27 (IPUSIRON) コンピュータ慣れしているひとには、アルゴリズムみたいなものといったほうがいいかな。アルゴリズムって入力と出力がありますよね
21:27 (mudai) なるほどw
21:27 (asuno) ほー
21:27 (talon_) なーる
21:28 (IPUSIRON) θ：V（G1）→V（G2）という写像θは
21:28 (mudai) 写像処理にUXを入力したらlpって感じですか・・
21:28 (nesys) 同型で使われていたので、○→○の左右が実際は同じものでただ移動しているだけのことが写像なのか？と思ってましたよ
21:28 (IPUSIRON) G1の点たちのどれかを、アルゴリズムθに入力して、G2の点になっているという感じですかね
21:28 (nesys) 了解です
21:28 (Defolos) ＯＫですー
21:29 (clothoid) OKっすかね。情報系の話は私は分からないのですが・・・ｗ
21:29 (clothoid) で，一対一写像ってのは
21:29 (clothoid) 入力一つに対し，出力が唯一つ定まる
21:30 (clothoid) といった意味です。
21:30 (mudai) ふむふむ
21:30 (clothoid) y=2x+3であれば，x=1にたいし，y=5と唯一つに定まります
21:30 (asuno) おー　なるほど　OKです
21:30 (Defolos) あー
21:30 (Defolos) なるほろー
21:31 (clothoid) こんなんが一対一対応，一対一写像って意味です。
21:31 (mudai) ふむふむ
21:32 (clothoid) y　× y = x+2 という式では，x=2に対し， y×y=4 で， y=±2となりますから，一対一写像じゃありません
21:32 (nesys) ほぉ
21:32 (talon_) 円の方程式とかも代表例ですよね
21:32 (mudai) 多重辺・？
21:32 (clothoid) そうですね＞talonさん
21:33 (clothoid) するどいですね！。それで，掲示板でうんぬんやったように，実はこの先悩んでいますが・・・＞mudaiさん
21:33 (clothoid) 話を戻して，一対一写像ですが，
21:33 (nesys) 返り値が1つ時、1対1写像と言うわけですね
21:33 (clothoid) 一対一写像の場合は，逆写像というものを定義できます。たとえば，
21:34 (clothoid) y=2x+3　で， x=1 のとき y=5を唯一つ定まりますが， y=5ときめてあげれば，x=1と逆に辿ることができます
21:34 (Defolos) ふむふむ
21:34 (nesys) なるほど
21:35 (clothoid) こんな感じのものを逆写像といいます。
21:35 (mudai) なるほどです
21:35 (nesys) 1対1写像は必ず逆写像となるってことですかな？
21:36 (clothoid) 一対一写像では，必ず逆写像も考えることができるよ，ってことですかね。＞nesysさん
21:36 (dotdister) 些細なことですが、同型→同形では？
21:36 (nesys) 了解
21:37 (clothoid) どっちでも良いと思います＞dotsisterさん
21:37 (clothoid) 失礼。dotdisterさん
21:37 (dotdister) いえ、話の腰を折ってすいませんでした。
21:37 (clothoid) 昔は，型と形という感じを分けて使っていた場合が多いようですが，
21:38 (clothoid) いまは，同じ意味に使っている場合が多いと思います。
21:38 (clothoid) 数学の世界では。たぶん。数学の人じゃないので，正確に言えませんが。
21:38 (nesys) ほぉ
21:38 (clothoid) どうでしょううか？＞IPUさん
21:38 (IPUSIRON) 同型のほうがよくみるけど、どっちでも変わらないですね
21:38 (dotdister) 気にしたところでどうにもなりませんしね。
21:38 (IPUSIRON) 本によるかな
21:39 (clothoid) 線形代数と線型代数は二つ見ます。
21:39 (clothoid) 古い本，古い人だと型を使うような気がしていますが。
21:39 (IPUSIRON) かも
21:39 (clothoid) まぁ，とりあえず，元資料にならって，「型」でいきましょう。
21:39 (Defolos) そうなんだー
21:40 (clothoid) で，写像の意味はよろしいでしょうか？
21:40 (nesys) はい
21:40 (dotdister) はい、続きお願いします。
21:40 (mudai) よろしいです
21:40 (Defolos) たぶん大丈夫です
21:40 (talon_) OKです
21:40 (asuno) OKです
21:40 (clothoid) 元に戻って，p.12です。
21:41 (clothoid) 今まで，具体例で説明したθとφの意味が，最初の三行に書かれています。
21:42 (nesys) eはとある点のことですね？
21:42 (clothoid) 二行目の意味は，「θはG_1の点をG_2の点に対応させる」という意味です。
21:42 (clothoid) そうですね。＞nesysさん
21:42 (IPUSIRON) いや
21:43 (clothoid) 三行目の意味は，「φはG_1の辺をG_2に対応させる」という意味です。
21:43 (clothoid) 違いましたか？＞IPUさん
21:43 (IPUSIRON) G1の点の集合、即ちV(G1)に含まれている要素たち（つまり点たち）全部って意味だと思います
21:43 (IPUSIRON) ∀＝「任意」「すべての」という意味ですから
21:43 (Defolos) なるほど
21:43 (nesys) なるほど
21:43 (talon_) ほほぉ
21:43 (Defolos) ∀　口だと思ってました＾＾；
21:44 (IPUSIRON) ∃＝「ある」という意味であって
21:44 (nesys) リターンAって何だろうと思ってましたｗ
21:44 (mudai) そのターンエーガンダムのマークみたいなのはなんと打つと変換できますか・・滝汗
21:44 (Defolos) きごう？
21:44 (clothoid) そうですね＞IPUさん。
21:44 (IPUSIRON) ある点という解釈だと、下の⇔の式がひとつでも成り立てばOKになってしまいます
21:44 (clothoid) 失礼しました。>nesysさん
21:44 (IPUSIRON) すべてのという意味なら、下の式はすべての点に対して成り立つという意味ですね
21:45 (clothoid) そうですね。
21:45 (clothoid) 四行目以降にいっちゃいましたが，
21:45 (clothoid) Aをひっくり返した記号の意味は
21:45 (clothoid) IPUさんがおっしゃるように
21:45 (clothoid) すべての，任意の，といった意味です。
21:46 (IPUSIRON) 英語で言うと「for all」なので、allのAをひっくり返したんだと思います
21:46 (Defolos) なるほど
21:46 (nesys) ほぉ
21:46 (IPUSIRON) eはExist（存在）かな？
21:47 (IPUSIRON) ∃
21:47 (clothoid) また，V(G1)の前に書いてある記号は
21:47 (mudai) すべてと任意が同義ではないと思いますが・・この場合すべての意でいいですか？
21:47 (clothoid) V(G1)の中に存在する要素
21:47 (clothoid) という意味です。
21:47 (IPUSIRON) ここのeはelementなのかな
21:48 (nesys) eが全ての点なら、uvは全ての辺という意味なのかな？
21:48 (clothoid) 「任意の〜に対し，○○が成り立つ」という文にすると，「任意の」と「すべての」が同じ意味になると思いますが＞mudaiさん
21:49 (clothoid) 違います>nesysさん
21:49 (nesys) ありゃ
21:50 (clothoid) V(G_1)の中から，自由に選んだ辺eに対するuvという意味です。
21:50 (clothoid) 難しい。。。
21:50 (nesys) なるほど。
21:50 (IPUSIRON) これは一旦⇔のところ説明したほうがいいとおもいます
21:50 (mudai) いや・・その解答でわかりました。
21:50 (clothoid) あれ・・・
21:51 (clothoid) e in V(G)じゃなくて e inE(G)ですか・・・
21:51 (nesys) ？？
21:52 (clothoid) ちょっと待ってください
21:52 (IPUSIRON) ψという写像（アルゴリズム）は入力は辺のはずだから　∀e∈E(G)ですね…
21:52 (clothoid) ですね。
21:52 (Defolos) あ、なるほど
21:53 (IPUSIRON) 辺を入力すると、その両端の点を出力なので
21:53 (clothoid) typoです。○∀e∈E(G)　×∀e∈V(G)
21:53 (clothoid) すみません。
21:53 (nesys) あ。ほんとですね
21:53 (mudai) きずかなかった・・・
21:54 (clothoid) G_1の辺集合から，任意に辺eを選んだ時，という意味です。
21:54 (clothoid) メモ：p12にtypo
21:54 (Defolos) eは辺のことだったのですね
21:54 (clothoid) で，⇔の式ですが。
21:54 (clothoid) はい。そうです。すみません＞Defolosさん
21:54 (Defolos) 量化しました
21:54 (Defolos) 了解・・・
21:55 (clothoid) eを選んだとき，ψ_G1(e)=uvという式は，
21:55 (clothoid) さきほど，接続関数の定義のところでやったように
21:55 (clothoid) 辺eに対し，頂点を対応させれば良いですから，
21:56 (clothoid) uvというのは 辺eの両端の点uと点vを表しており，
21:56 (clothoid) 辺eに対する，点uと点vの関係を表した式だということです。
21:57 (mudai) ただ括弧の中と右辺を別の書き方に直したと言う感じでいいですか？
21:57 (IPUSIRON) ⇔の左の式の意味のことですね
21:57 (clothoid) ⇔の
21:57 (clothoid) 左側の式
21:57 (clothoid) あ，そうです＞IPUさん
21:57 (clothoid) ⇔の左側の式の意味です。
21:58 (clothoid) 任意に選んだeに対し，接続関数ψを用いると，⇔の左側が成り立つ，とします。
21:58 (clothoid) ここまで良いですか？
21:58 (nesys) はい
21:58 (Defolos) はい
21:58 (mudai) はい
21:58 (dotdister) はい。
21:58 (asuno) はい
21:58 (clothoid) で，この左側の式が，なんと，右側の式を同じ式だ！つーのです。
21:59 (clothoid) ⇔の意味です↑
21:59 (IPUSIRON) あくまで成り立つと仮定するのがポイントですね
21:59 (nesys) ⇔の意味は=と？
21:59 (clothoid) まぁ，そうですね。ただ，＝は既に式の中で出てきているので，等式と等式がイコールのとき
21:59 (clothoid) ⇔と書きます＞nesysさん
21:59 (nesys) なるほど
22:00 (Defolos) そうだったのですか
22:00 (dotdister) なるほど。
22:00 (IPUSIRON) あ
22:00 (mudai) なるるるー
22:00 (clothoid) で，右側の式を理解していくわけですが。
22:00 (IPUSIRON) 同値（⇔）のところですが、確かに左と右は同じなんですが
22:00 (clothoid) はい。
22:01 (IPUSIRON) まず左の式がありますよね。それが成り立つならば、右が成り立って、
22:01 (IPUSIRON) なおかつ右を仮定して、左の式を真であることが導ければ、同値なんです。
22:01 (IPUSIRON) A⇔Bのとき
22:02 (talon_) 必要十分条件というやつですね
22:02 (IPUSIRON) A⇒BとA←Bを示せたときA⇔Bになるんですね
22:02 (clothoid) たしかに。そうですね。ありがとうございます。
22:02 (nesys) なるほど
22:02 (IPUSIRON) ポイントは
22:02 (nesys) 単純な=ではないということか。
22:02 (IPUSIRON) 最初A⇒Bを考えると、あくまでAが成り立つと仮定して、そのときBが成り立てばよいわけですね
22:03 (IPUSIRON) 例えば
22:04 (IPUSIRON) 「aが整数」⇒「aは偶数」とわかりますよね
22:04 (nesys) はい
22:04 (IPUSIRON) みす
22:04 (nesys) ん？
22:04 (dotdister) 逆ですよね。
22:04 (IPUSIRON) 「aが偶数」⇒「aが整数」です
22:04 (talon_) あーびっくりした
22:04 (nesys) あぁ
22:05 (IPUSIRON) あくまで左が成り立つと仮定した上だけでしか、右側の証明のとき（ここではすぐわかりますが）には考えてないんです。
22:05 (IPUSIRON) これを両方の矢印でやったときに⇔なんです。
22:05 (Defolos) なるほどー
22:05 (IPUSIRON) その⇔がいえてはじめてさっきいったように式変形ができるということなんですね
22:06 (nesys) なるほど
22:06 (clothoid) ありがとうございますー
22:06 (mudai) 逅�隗｣�ｽｯ�ｽｯ�ｽｯ!
22:06 (clothoid) 読めないっす＞mudaiさん
22:06 (IPUSIRON) 今のは⇔関係の証明のときに使う方法なので
22:07 (mudai) あ・・すいません・・＞clothoidさん
22:07 (IPUSIRON) 「x+1=0」から下に「x=-1」と書きますよね。よく方程式の計算とかで
22:07 (mudai) ついうっかり・・
22:07 (clothoid) いえいえ。
22:08 (IPUSIRON) これはあくまで簡単だからすぐにいけてますが、実際には「x+1=0」⇔「x=-1」をやってるんです。
22:08 (dotdister) ほぉー。
22:08 (Defolos) ほほー
22:08 (nesys) ほぉ
22:08 (mudai) かなりわかりやすいです。その例は
22:08 (IPUSIRON) 簡単ですぐ導けないときは、最初いった⇔の定義から2つに場合分けて、⇒のときと←のときで示さなければならないんです
22:09 (IPUSIRON) こんなところです。続きどうぞ
22:09 (clothoid) はい。分かりやすい説明ありがとうございますｍ（＿＿）ｍ
22:09 (clothoid) で，えっと・・・
22:09 (asuno) あっ　すいません　読みは「←」「⇒」の両方とも矢印?
22:09 (clothoid) そうですね
22:10 (asuno) 了解です
22:10 (clothoid) 左向きの矢印で
22:10 (clothoid) 同じ形のものが，無いので
22:10 (clothoid) ←と書いたんだと思います。
22:10 (Defolos) なるほど
22:10 (nesys) ほんとだ
22:10 (IPUSIRON) 「A⇒B」を口頭でいうときは「AならばB」です
22:11 (IPUSIRON) 「A←B」をいうときは「BならばA」です
22:11 (nesys) ｆｍ
22:11 (asuno) ほぉ
22:13 (clothoid) で，右側の等式ですが，左辺は，「任意に選んだeに対し，G_2の辺を対応させる写像φにより，G_2の辺に対応させ，
22:14 (clothoid) その上で，さらに，その対応させた辺に接続関数を用いる，という意味ですが，
22:14 (clothoid) この説明で，分かるでしょうか・・・。
22:15 (clothoid) （）の中の方から，順に考えていきます。
22:15 (mudai) おkです。
22:15 (talon_) たぶんOKです
22:15 (nesys) 分かりました
22:15 (Defolos) なんとなく理解できた気がします
22:15 (dotdister) だいじょぶだと思います。
22:15 (IPUSIRON) 簡単にいうとG1の点を一個選んでG2の点にぴょーーんととばす。さらにeの両端の2点もぴょーーんと飛ばすとちょうど、G2まで最初飛ばした点の両端と一致してるってことですね
22:16 (clothoid) 了解。また，分からなくなったら，言ってください。
22:16 (clothoid) 点じゃなくて辺ですね。＞IPUさん
22:16 (IPUSIRON) ああ辺です
22:17 (IPUSIRON) 続きどうぞ
22:17 (clothoid) 右式の意味は
22:18 (clothoid) θ(u)が，G_1に含まれる点uに対応するG_2の点，θ(v)が，G_1に含まれる点vに対応するG_2の点
22:19 (clothoid) で，それらを並べて書けば，ψG2(・・・）により，ぴょーんと飛ばされてきた，ある辺に対する頂点が表される，
22:19 (clothoid) といった意味ですが，こちらは，どうでしょうか。。。
22:20 (dotdister) 分かりました。
22:20 (mudai) おkです。
22:21 (clothoid) 右の式は，全体として，グラフG_2のことを表しています。
22:21 (Defolos) なんとなくわかった感じです
22:21 (clothoid) あ，ちと，分かりにくいから，撤回しときますね・・・。
22:22 (clothoid) 実際，例で見てみることにしましょう
22:22 (clothoid) スライド，p14を見てください。
22:22 (nesys) 単純にG1をG2に当てはめるために、写像を適応したってことですね
22:23 (clothoid) θ，φについては，そうですね＞nesysさん
22:23 (clothoid) p.14では，さきほど，考えたように，
22:23 (clothoid) G1のどの点がG2のどの点に対応し，
22:23 (clothoid) どの辺が，どの辺に対応するか，
22:23 (clothoid) というのを
22:24 (clothoid) θ，φを使って，具体的に書いてあります
22:24 (clothoid) ここまではOKだと思います。
22:24 (clothoid) そして，最後の二行ですが，
22:24 (clothoid) ミスがあり，
22:24 (clothoid) 同型写像の逆写像　ではなく，
22:24 (clothoid) 接続関数の逆写像　です。
22:24 (clothoid) すみません。
22:25 (clothoid) 接続関数ψとは，ある辺eに対し，その辺の頂点uv（ここではuvとする）を対応させる関数でした。
22:26 (clothoid) 多重辺を含まなければ，ある頂点2つ（たとえば，uとv）を指定すれば，辺eが唯一つ定まることになります。
22:27 (clothoid) すなわち，逆写像というものを考えることができる，というのが，下二行の意味です
22:27 (clothoid) よろしいでしょうか？
22:27 (dotdister) 逆写像の指数みたいなー１の意味は何ですか？
22:27 (talon_) 逆関数ですか？
22:27 (nesys) "接続関数の"というのがよく分かりませんが、とにかく逆写像が成り立つということですね
22:28 (clothoid) たんなる記号ですが，ある写像 f の逆写像を f^-1　と書くならわしになっています＞dotdisterさん
22:28 (clothoid) そうです＞talonさん
22:28 (dotdister) 了解です。
22:28 (Defolos) なるほろ・・・
22:28 (clothoid) 接続関数ψG1の逆関数ψG1^-1という意味です。
22:28 (talon_) 了解
22:29 (clothoid) 関数やら写像やら，用語が統一されてませんでした。すいません。
22:29 (mudai) 点と点どうしならΘ、辺と辺どうしならΦ、辺とそれぞれ対応する点ならφ・・ですか？
22:29 (nesys) 逆写像でなく、逆関数と？
22:29 *asuno_ join #akademeia (~asuno@KHP222227183230.ppp-bb.dion.ne.jp)
22:29 (clothoid) 辺とそれぞれ対応する点ならψですね＞mudaiさん
22:29 (asuno_) すみません　落ちました。。
22:30 (mudai) おかですw
22:30 (mudai) なるほどです。
22:30 (clothoid) 写像と関数はとりあえず，同じ意味なので＞nesysさん
22:30 (mudai) プサイでしたね・・
22:30 (nesys) あ。そういうことですか。了解です
22:30 (clothoid) 逆関数と書いたほうが良かったですね。すみません。>nesysさん
22:31 (clothoid) で，こうやって定義した，θ，φ，ψ^-1を使って，式をグリグリやっていきます。
22:31 (clothoid) p.15です。
22:31 (Defolos) グリグリ・・・
22:31 *asuno quit (Ping timeout)
22:31 (clothoid) 了解です＞asunoさん
22:32 (clothoid) 今，θとφ，ψ，ψ^-1の説明が終わったところですが，
22:32 (clothoid) 分からないことがあれば，再度説明しますが，どうでしょう？
22:32 (clothoid) スライドで言うと，p.15まできています。
22:32 *talon_ mode +o asuno_ 
22:33 (asuno_) altu
22:33 (asuno_) あっ　このまま続けてください
22:33 (nesys) ぅ…2行目から分からないです…すみませｎ…
22:33 (clothoid) 了解です。分からないことがあれば，また，いつでも言ってください＞asunoさん
22:33 (clothoid) で，p15ですが，一番上の式は，接続関数の定義から，そのまま書いた式です。
22:33 (asuno_) はい　ありがとうございます
22:33 (mudai) ちょっとP15は混乱してしまってます・・
22:34 (clothoid) 辺uxに対応する点はuとxです。
22:34 (mudai) ふむふむ
22:34 (clothoid) 今，p.13で考えているグラフでは
22:34 (clothoid) 多重辺を含みませんから，
22:35 (clothoid) 点uと点xを指定すれば，辺uxが唯一つ決まります。
22:35 (clothoid) 二行目の式は，右から左へと読むと分かりやすいと思います。
22:35 (mudai) ふむふむ
22:35 (nesys) あ！2行目は1対1写像の時、逆写像が成り立つというあれですね。
22:36 (IPUSIRON) f^-1はアルゴリズムfの入出力を逆に見ていると思えばいいですよ
22:36 (clothoid) 「点uと点xを選ぶと，それに対応する辺uxが唯一つ決まる」＝ψ^{-1}の意味
22:37 (clothoid) 二行目まで，OKっすか？＞nesysさん
22:37 (nesys) おｋです
22:37 (Defolos) 2行目のψＧ１＾−１（ux）は辺を入力してるのですか？
22:37 (clothoid) mudaiさんはどうでしょう？
22:37 (nesys) 関数で言う、戻り値を入れたら引数が分かるってことですね
22:37 (mudai) おけですw
22:37 (IPUSIRON) 2行目は単にfを移動しただけと考えたほういいです
22:37 (clothoid) そうです＞Defolosさん
22:37 (IPUSIRON) 表記を変えているだけです。1行目と2行目は
22:37 (Defolos) なるほど
22:38 (IPUSIRON) 1行目は自動販売機にお金を入れるとジュースが出てくるという式であり、2行目はジュースを入れるとお金がでてくるというわけです。
22:38 (Defolos) ほむ
22:38 (mudai) わかりやすいw
22:38 (dotdister) ほぉ。
22:38 (talon_) ほほぉ
22:39 (IPUSIRON) f^-1は「エフインバース」というので、逆操作ね
22:39 (IPUSIRON) ここではψ（プサイ）ですが
22:39 (nesys) 蛇足ですが、そんな自販機が実在したらいいかもなｗ
22:39 (clothoid) 教科書に書いてあることがポンポンでてきて，すごいっす。ありがとうございます＞IPUさん
22:40 (clothoid) 三行目ですが，2行目の左式はG1の辺uxを表しているので，φにより，辺ux対応するG2の辺に写すことを考えています。
22:41 (clothoid) 三行目，どうでしょう？
22:41 (dotdister) これはただ単に２行目のことをG2の方に言い直しただけですかね？
22:41 (mudai) おkです。
22:41 (talon_) a=b ならば f(a) = f(b)と考えると楽ですね
22:41 (clothoid) そうですね>talonさん
22:42 (Defolos) 3行目まではＯＫですー
22:42 (nesys) 4行目も同様にですね
22:42 (clothoid) talonさんの説明でどうでしょう？＞dotdisterさん
22:42 (dotdister) はい。大丈夫です。
22:42 (clothoid) 4行目も同様ですね。
22:42 (clothoid) φの変わりにψG2を使っています。
22:42 (clothoid) で，四行目の式となります。
22:43 (clothoid) 四行目だいじょうぶでしょうか？
22:43 (nesys) はい
22:43 (Defolos) たぶんはい
22:43 (mudai) おけですw
22:43 (dotdister) はい。
22:44 (clothoid) あとは，四行目の式の右辺をひたすら計算していくだけです。
22:45 (clothoid) まず一つ目のイコールで，右辺ψ_(G1)^(-1)(ux)は二行目を見て分かるとおり，辺uxのことですから，ψ_(G1)^(-1)(ux)を辺ux（bar(ux)のこと）と書き直しています。
22:46 (clothoid) 書き直した式を見てみると，φ(ux)となっていますが，これはφの定義より計算できて，辺lpとなります。
22:46 (clothoid) これが二つ目のイコールです。
22:46 (clothoid) そして，ψ_G2(lp)は，これまた，接続関数の定義により，計算できて，lpとなります。
22:47 (clothoid) ここまで，どうでしょう？
22:47 (mudai) おkです
22:47 (dotdister) ダイジョブです。
22:47 (Defolos) 問題なさそうです
22:47 (nesys) おｋです
22:48 (nesys) これp14の続きでしたね、あっちのほうの定義をばんばん入れてって解決しそうです。
22:48 (clothoid) で，グラフG_2の点lは，グラフG_1の点uに対応する点ですから，
22:48 (clothoid) θ関数を用いると，θ(u)=l
22:48 (clothoid) 同様に，θ(x)=p
22:48 (clothoid) となり，最後の式となります。
22:49 (clothoid) どうでしょう？
22:49 (mudai) おkです
22:49 (Defolos) ＯＫ〜
22:49 (dotdister) おーけーです。
22:49 (clothoid) で，一連の式を眺めて見ますと，
22:49 (clothoid) 一行目の式が
22:49 (clothoid) いろいろ変形されて，
22:49 (clothoid) 最後のψG2(・・・)=θ(u)θ(v)と
22:50 (clothoid) 同じ式である，ってことになります。
22:50 (clothoid) スライドで言うと，「であるから，〜」の「〜」の部分のことです。
22:51 (clothoid) この同値式は，さきほど同型写像の定義のところで示した同値式のeをuxに変えたものとなっています
22:51 (nesys) は〜なるほどね。
22:52 (clothoid) すなわち，θとφ，ψ^{-1}をp.14で定義したわけですが，この定義より，同値関係の式が導かれたことになります。
22:52 (nesys) uxをeに変えることでp12の式が証明されたわけですね。
22:53 (clothoid) この同値関係の式が導かれる時，グラフG1はグラフG2と同型である，といえます。
22:53 (clothoid) そうですね＞nesysさん
22:53 (Defolos) なるほど
22:53 (clothoid) ここでは，点u，点x，辺uxの関係を用いて，同値関係の式を導きましたが，
22:54 (clothoid) その他の点，辺についても，どうように確かめる必要があります。
22:54 (clothoid) スライドには書いていません。書いてある記号を変えるだけです。
22:54 (clothoid) すべての点，辺について，この同値関係の式が満たされることを示せたら，θとφが同型写像であり，
22:55 (clothoid) グラフG1とグラフG2が同型であることが示せた。ということになります。
22:55 (clothoid) 同様に〜で，ごまかしていますが。
22:55 (mudai) すべての！ですね
22:55 (clothoid) ですね。＞mudaiさん
22:55 (clothoid) 同型写像の具体例はこれで終わりです。
22:55 (clothoid) 再度，p12を見てみてください。
22:56 (clothoid) どうでしょう？分からないことがありますか？
22:56 (mudai) ないです！！！
22:56 (nesys) やっと同型終了ｗ
22:56 (Defolos) 大丈夫ですー
22:56 (clothoid) 良かったですｗ
22:56 (clothoid) 説明下手ですみません。
22:57 (mudai) 乙ですw
22:57 (talon_) そんなことないですよ
22:57 (Defolos) いえいえ、私こそ理解力不足で申し訳ない
22:57 (clothoid) あと，一スライド，同型の話して，同型を終わりにしましょう。
22:57 (clothoid) p.16です。
22:57 (clothoid) 先ほど，p.11で同型の定義をしましたが，
22:58 (clothoid) 同型写像という概念を用いると，同型を，よりすっきり定義できます。
22:58 (clothoid) つまり，同型写像θφが二つのグラフ間に存在すれば，同型というわけです。
22:58 (clothoid) 今までは，頭の中で〜とか，わごむで〜とか考えていましたが，
22:59 (clothoid) これからは，同型写像を探すことにより，二つのグラフが同型であるかどうかを判断することとなります。
23:00 (nesys) 確かに頭の中でごちゃごちゃ考えるより、数学的にその2つがあるから同型だ！というほうが楽ですね。
23:00 (clothoid) 複雑なグラフ同士を同型かどうか判断するとき，頭の中や輪ゴムの考えじゃ分からない場合があると思います。
23:00 (mudai) 質問いいですか？汗
23:00 (clothoid) そんなとき，同型写像が存在し，あの同値関係が満たされるかなぁ〜と考えると，少し楽になるかもしれません。ならないかもしれません。というか，たぶん，ならないと思います・・・（謎
23:01 (clothoid) はい＞mudaiさん
23:01 (clothoid) そうですね＞nesysさん
23:01 (mudai) P15の最下行の「の関係が満たされ、したがって、（Θ、Φ）は同型写像」とありますけど・・雰囲気的に（G_1,G_2)のような気がします。
23:02 (clothoid) G_1とG_2なら，同型写像ではなく，同型ということになりますね。
23:02 (mudai) 合点！承知の助!
23:03 (mudai) 要約合点が行きました。
23:03 (mudai) ようやく・・
23:03 (clothoid) したがって，「（θ，φ）は同型写像であり，G_1とG_2は同型である」と書いたほうが良いかもしれませんね。
23:03 (clothoid) メモ：↑直す。
23:03 (clothoid) 一番，やっかいな部分が終わったので
23:03 (clothoid) 五分休憩にしませんか？
23:04 (mudai) そうですねw
23:04 (talon_) 賛成です
23:04 (Defolos) (*'ω')休憩だー
23:04 (clothoid) それでは，23:10まで。
23:04 (asuno_) 了解ー
23:04 (clothoid) 休憩で。
23:04 (Defolos) 寝てたらごめんね
23:04 (mudai) なんか大学の講義より集中したわー
23:04 (Defolos) ＾＾；
23:04 (clothoid) そんときは，また，ログ見て，後日聞いていただければOKです＞Defolosさん
23:05 (nesys) 休憩ーｗ
23:06 (clothoid) メモ：p.16で同型の式のG2だけ斜体なので直す。
23:08 (talon_) 重箱の隅つつくようでいけないんですが、p.8の右上のしきの後にあるコロンが妙に離れてるような…汗
23:08 (clothoid) あ，ホンとですね。ありがとうございます。>talonさん　　　メモ：↑直す
23:10 (mudai) リスタート？W
23:10 (dotdister) 準備OKですー。
23:10 (Defolos) おけー
23:10 (clothoid) ですね。
23:10 (talon_) おーけー
23:10 (clothoid) えっと，
23:10 (clothoid) p.17です。
23:11 (clothoid) ラベルつきグラフです。
23:11 (clothoid) スライドの例にあるように，点にそれぞれ名前をつけたものを
23:11 (clothoid) ラベルつきグラフといいます。
23:11 (clothoid) ラベルがなかったら，ラベルなしグラフです。あまりいいませんが。
23:11 (clothoid) ラベルなしぐらふでは，例の2つのグラフは同じものですが，
23:12 (clothoid) ラベルつきグラフとなると
23:12 (clothoid) 異なったグラフとして扱うので
23:12 (clothoid) 注意してください。
23:12 (nesys) ｆｍ
23:12 (clothoid) 次に，p.18です。
23:12 (clothoid) 点uと点vがつながっている，リンクされているとき，連結されると言います。
23:12 (clothoid) ここで，「道」という単語が出てきましたが，
23:12 (Defolos) 繋がってるってことですか
23:13 (clothoid) はい。＞Defolosさん
23:13 (clothoid) 第一回で出てきた「道」とは違うようです。
23:13 (clothoid) 元資料のp.38に，再度，道が出てきていますので，
23:13 (clothoid) 見てみてください。
23:14 (clothoid) 道やらなんやら，用語の統一はされてないようですが，そのつど，考える方向でよろしいでしょうか？＞ipusironさん
23:14 (IPUSIRON) そうですね
23:14 (IPUSIRON) あまり本質的じゃないところぽいので
23:14 (clothoid) ですね。りょうかいです。
23:15 (clothoid) ここでは，つながってるという意味です。
23:15 (clothoid) 次，p.19
23:15 (clothoid) グラフの成分です。
23:15 (clothoid) これまた数学チックに書いてあり，分かりづらいので，p.20に挙げた例から見ていきましょう
23:16 (IPUSIRON) 例がわかれば十分かもしれませんね
23:16 (clothoid) そうですね>IPUSIRONさん
23:16 (clothoid) p.20の下図では，
23:16 (clothoid) 繋がっていないグラフもぜーんぶひっくるめて
23:16 (clothoid) グラフGということにします。
23:16 (nesys) あぁ例ですぐに分かりますね。
23:17 (Defolos) 大陸みたいな感じですねーと思いました
23:17 (clothoid) この，ぜーんぶひっくるめたグラフを考えるとき，繋がっているグラフ
23:17 (clothoid) いくつかに分けられるんじゃないかー？と考え，わけることにします。
23:18 (clothoid) そうですね＞Defolosさん
23:18 (clothoid) で，つながってるやつに分けると，例では，V1，V2，V3といったようにわけることができる。
23:18 (clothoid) この，V1とかV2とかを成分といいます。
23:19 (clothoid) そして，三つに分けられたので，グラフGの成分数は3ってことになります。
23:19 (Defolos) なるほど
23:19 (clothoid) どうでしょう？成分と成分数のイメージは分かったでしょうか？
23:19 (nesys) はい
23:19 (Defolos) おｋですー
23:19 (mudai) おけぇぇぇいいいい！！
23:19 (dotdister) だいじょぶです。
23:20 (clothoid) p.19では，数学チックな言葉で書いてありますが，意味はこの程度です。
23:20 (clothoid) 後で読んでみてください。分からなければ，後に質問という形にします。
23:20 (clothoid) 次に，p.21連結グラフです
23:20 (clothoid) これは前回やったと思います。
23:21 (clothoid) 全部繋がってるグラフが連結グラフで，そうじゃないものが非連結グラフです。
23:21 (IPUSIRON) 全部つながっているというのを厳密に言うと成分１ということですね
23:21 (clothoid) 成分という言葉を用いて，より正確に定義すると（←これが目的），スライドのような表現になります。
23:21 (IPUSIRON) 誠分数１
23:21 (clothoid) そうですね。＞IPUSIRONさん。
23:22 (asuno_) 成分が全てくっついている=連結グラフ　と考えてよいですか？
23:22 (clothoid) いえ，成分が1のグラフと考えてください＞asunoさん
23:22 (asuno_) あー　そうですね
23:22 (asuno_) OKです
23:23 (clothoid) asunoさんが言うことと結果は同じですが，意味合いが違います。目的は正確に〜なので，とりあえず，
23:23 (clothoid) で，次。p.22
23:23 (clothoid) 次数ですが，
23:24 (clothoid) ある点から出ている線の数を次数と言います。
23:24 (clothoid) これも前回やりましたね。
23:24 (clothoid) ループのときは2とカウントすることに注意してください。
23:24 (clothoid) 例では点vについて考えているので，多重辺，ループに注意し確かめてみたください。
23:25 (clothoid) 次に，p.23，孤立点。他のどの点にも連結されていなく，ぽつんと一人だけ離れてるヤツが孤立点です。
23:26 (clothoid) 次に端点。次数が1のものです。直感的には，はじっこの点といった意味ですが，より正確に言うと，次数という概念を用いて定義できるって感じです。
23:27 (clothoid) 次にp.25。次数列。グラフGの全ての点について次数を考え，次数が小さい順に並べ，丸括弧（）でくくったものを次数列といいます。
23:28 (clothoid) p.26。握手補題。どんなグラフでも次数を全て合計すると偶数になる，といったlemmaです。
23:28 (clothoid) 証明方法は分かりませんでした。
23:28 (clothoid) どなたか分かりますか？
23:28 (Defolos) ０は偶数ですか？
23:28 (clothoid) 偶数です
23:28 (Defolos) 了解ー
23:29 (clothoid) 直感的説明として，下に書いてみましたが，証明ではないので，参考にする程度としてください。
23:29 (clothoid) 証明は分からないので，次に進みたいと思います。
23:29 (mudai) 点から辺が出るまたは入る場合必ずその出発点もしくは到着点が必要だから偶数にしなならざるをエナリって感じですか・・
23:30 (IPUSIRON) 多分
23:30 (nesys) 辺1つに対して、次数は2つあるので、次数の総和は2の倍数、偶数にしか成りえないでしょぅ
23:30 (clothoid) そうですね＞nesysさん。
23:30 (IPUSIRON) 青と青が両端にそれぞれある色鉛筆ありますよね
23:30 (IPUSIRON) 青と赤だ
23:31 (IPUSIRON) 線もそれと同様に考えれば、必ず青と赤はペアで使われるから（整数）×2色＝必ず偶数　ですね
23:32 (clothoid) そうですね。
23:32 (clothoid) ＋次数0　で偶数。
23:32 (IPUSIRON) ｙ
23:33 (IPUSIRON) 先どうぞ
23:33 (clothoid) はい
23:33 (clothoid) えー，p.27ですが
23:33 (clothoid) 次数列と，ある意味逆の事を考えます。
23:34 (clothoid) 勝手に，数列を考えます。4,3,2,2,1とか
23:34 (clothoid) で，これらが次数列となるようなグラフが描ければ
23:34 (clothoid) その数列はグラフ的だといいます。
23:34 (clothoid) かけなければ，グラフ的でないとなります
23:35 (clothoid) p.28に例があります。
23:35 (clothoid) 4, 3, 2, 2, 1 という数列が与えられ，
23:36 (clothoid) 点1の次数が4，点2の次数が3・・・といったように描いていき
23:36 (clothoid) うまくグラフがかけたら，この数列はグラフ的だー
23:36 (clothoid) って感じです。
23:36 (Defolos) 数列の合計が奇数だったら描けないってことでしょうかねぇ
23:36 (dotdister) 握手補題を使って考えると、次数列の和が偶数ならば、グラフ的ってことになりますか。
23:36 (clothoid) そうですね＞Defolosさん
23:36 (Defolos) なるほどー
23:37 (clothoid) そうとは限らないと思います＞dotdisterさん
23:37 (mudai) なるるw
23:37 (IPUSIRON) でも握手の補題は一方通行ですよ
23:37 (IPUSIRON) 偶数ならばグラフ的とは限らないような気がします
23:37 (clothoid) あ，そうか。
23:37 (dotdister) どういうことですか？
23:37 (IPUSIRON) 例えば
23:37 (clothoid) いや，あってるか。私の言い方↑
23:38 (IPUSIRON) (1,1,1,1)は偶数ですよね。でも明らかにグラフで描けないような気がします。
23:38 (IPUSIRON) 合計が偶数
23:38 (dotdister) ははぁ。。。
23:38 (Defolos) あ、本当だ
23:38 (IPUSIRON) もっと単純に(1,1)でいいですね
23:38 (mudai) 単純にして明解・・wこのことかw
23:39 (nesys) あれ…？
23:39 (nesys) 両方ともグラフかけそうな気がするのですが
23:39 (IPUSIRON) ループにすると2ですよ
23:39 (nesys) 1, 1だと点が2つなので、1つの辺でグラフ書けますし
23:39 (IPUSIRON) ああかけるか（笑）
23:39 (clothoid) 数列の合計が奇数だったら描けない　←これは合ってますよね？違います？
23:39 (mudai) ん？ん？
23:39 (nesys) (1, 1, 1, 1)だと成分2で
23:39 (dotdister) 書けますねｗ
23:39 (IPUSIRON) 普通の線ですね…＜(1,1)
23:40 (nesys) 例え(100, 2)だとしても、ループしまくればいいので、偶数だったらグラフ書けると思うのですが
23:40 (mudai) 成分３で孤独点って場合も可？
23:40 (IPUSIRON) 握手補題を明確にすると、「G：グラフ」⇒「Gのすべての点の次数は偶数」かな
23:41 (IPUSIRON) 孤立点は次数0ですよね
23:41 (mudai) そかそか！！
23:42 (IPUSIRON) 少なくともこの文献にはGがグラフであればという前提なので、逆はまだ謎ですね
23:42 (IPUSIRON) そのうちでてくるか、それとも未解決だったりとか（笑）
23:42 (clothoid) Gの全ての点の次数が奇数ならばGはグラフでない　が　対偶ですか？
23:42 (IPUSIRON) ですね＜対偶
23:42 (clothoid) 全ての点の次数の合計が　の　間違い
23:43 (clothoid) 命題が成り立てば，対偶も成り立つんでしたっけ？
23:43 (IPUSIRON) ｙ
23:43 (IPUSIRON) 必ず成り立ちます
23:43 (mudai) ？？？
23:43 (mudai) つまりはどういうことですか？？
23:43 (clothoid) ってことは，奇数ならグラフじゃないってことですね？
23:43 (IPUSIRON) 「A⇒B」というのがあったら、対偶というのは「Bでない⇒Aでない」＞無題さん
23:43 (mudai) おkです！！
23:44 (nesys) ｆｍｆｍ
23:44 (asuno_) なるほど
23:44 (IPUSIRON) つまり、「Gがグラフ⇒次数の合計が偶数」の対偶は「次数の合計が偶数でない（即ち奇数）⇒Gはグラフでない」となります
23:44 (IPUSIRON) 同じ意味です
23:44 (clothoid) 了解です。
23:44 (dotdister) 了解。
23:45 (Defolos) なるほろ
23:45 (mudai) イエッサー
23:45 (clothoid) えー，次いきます
23:45 (clothoid) p.29
23:45 (IPUSIRON) どぞ
23:45 (clothoid) 部分グラフです。
23:45 (clothoid) グラフを一部切り取ったと考えればOKです。正確に書くとスライドのようになります。
23:46 (Defolos) 集合の部分集合っぽいのかな？
23:46 (clothoid) そうですね。っぽいです
23:46 (clothoid) 次に，p.30ですが，
23:46 (clothoid) これは二つの点をくっつけちゃうってやつです。
23:47 (clothoid) 縮約といいます。
23:47 (Defolos) 辺Ｂもなくなるのですね
23:47 (clothoid) そうですね。ループにはなりません
23:47 (Defolos) なるほど
23:47 (clothoid) なりません　というか　ならない　と決めます。
23:47 (clothoid) p.31です
23:48 (clothoid) 縮約と辺の除去というのを適当に組み合わせてあげれば，必ず，部分グラフができます
23:48 (clothoid) 元のグラフを「切り取り」しているわけですから，あたりまえっちゃーあたりまえですが，明確な数学的証明というと，少しあたふたします。
23:49 (clothoid) というか，分かりません。
23:49 (clothoid) p.32隣接行列です。
23:49 (clothoid) 数学で，行列というのがありますが，
23:49 (clothoid) みなさんどうでしょう？
23:49 (mudai) おkです、
23:49 (Defolos) ちょっとだけかじりました
23:49 (clothoid) まったく聞いたことがないとか
23:49 (dotdister) やってません。
23:49 (clothoid) あ。了解です。
23:49 (nesys) 行列キター
23:49 (clothoid) とくにスライドを用意してませんでした。
23:50 (talon_) 半年くらい前に授業でやりました
23:50 (dotdister) でも、これは感覚的になら若干理解できますが。
23:50 (mudai) 総当たり対戦表で辺・・・
23:50 (IPUSIRON) 行と列で構成されている表みたいなものかな
23:50 (dotdister) リーグ表的な雰囲気で。
23:50 (clothoid) えー，（主に）数字（記号でもいい）を長方形の形に規則正しく並べたものを行列と言います。
23:50 (clothoid) パソコンに詳しい方はExcelをイメージすると良いかもしれません・・・
23:51 (IPUSIRON) 表をそのままカッコにいれたものという直観的な感じでもいいかもですね
23:51 (clothoid) 横を行，縦を列といいます。
23:51 (dotdister) 配列変数に似てます？
23:51 (nesys) (1 2 3 4) = (a b c d)のように、一行でも行列となって、この式の場合、a=1, b=2,...みたいになったりしますね
23:52 (clothoid) 一行目で一列目のことを，(1,1)成分といいます。
23:52 (Defolos) あ、似てるかもー＞配列
23:52 (IPUSIRON) 2次元配列と同じですよ＞dotさん
23:52 (dotdister) なら、少し分かります。まだプログラミングは勉強途中ですが。
23:53 (dotdister) どうぞ、進めてください。分からなくなったらまたお願いします。
23:53 (clothoid) 了解です。
23:53 (clothoid) えー，p.32です。
23:54 (clothoid) グラフGにおいて点iと点jの連結の有無を(i, j)成分として行列をつくることができ，これを隣接行列といいます。
23:54 (clothoid) 具体例で説明します。
23:54 (clothoid) 下の図を見てください。
23:55 (clothoid) 点1は自分自身と連結が無いため，　隣接行列の1行1列目は0となります
23:55 (mudai) i
23:55 (nesys) あーなるほど。
23:55 (clothoid) 2とは連結があるため，2行1列目は1となります。
23:55 (clothoid) 3とも連結されているため，3行1列目mo
23:55 (mudai) iとjが連結されていればつまり真ということでそのセルには１が入ると言うことでおk？
23:55 (clothoid) も1となります。
23:56 (nesys) 縦が連結の次数、横がそれぞれの点なんですね
23:56 (clothoid) OKだと思います＞mudaiさん
23:56 (Defolos) 本数ですから真偽ではないのでは？
23:56 (clothoid) 違います＞nesysさん
23:56 (nesys) あぅ？
23:56 (clothoid) 連結の次数じゃなくて，連結の有無です。
23:56 (nesys) なるほど
23:57 (clothoid) 行（横）も列（縦）も点です
23:57 (nesys) あートーナメント表みたいなものですね
23:57 (clothoid) いいっすかね。
23:57 (Defolos) あ、そうか
23:57 (Defolos) 大丈夫です
23:58 (dotdister) 隣接行列って、本数じゃないんですか？
23:58 (clothoid) iとiが結ばれているとき，すなわち，ループのときも1とします。
23:58 (clothoid) 2とする場合もあるそうです。書物によっては。
23:58 (clothoid) 本数って書いてありますね・・・
23:58 (Defolos) 真偽は接続行列では？
23:59 (dotdister) 接続の有無は接続行列のほうですよね。
23:59 (clothoid) む・・・。
23:59 (dotdister) あ、かぶった。
23:59 (clothoid) 間違った。
23:59 (clothoid) すみません。
23:59 (clothoid) 本数です。
23:59 (mudai) あう・・すみません・・
00:00 (clothoid) nesysさん，すみません。
00:00 (nesys) 右下に直進している中心（何て表現するんだろう？）が0以外となるときはループってことですね。
00:00 (clothoid) 縦も横も現しているのは点ですが，中に入る数字は本数です。
00:00 (nesys) ｆｍ
00:00 (clothoid) そうですね。対角成分といいます＞nesysさん
00:00 (Defolos) ループだと11成分はいくつになるのかな？
00:01 (clothoid) 1です。
00:01 (Defolos) 了解
00:01 (clothoid) >Defolosさん
00:01 (clothoid) 2とするばあいもあるそうです。著者によっていは＞Defolosさん
00:02 (clothoid) えー，おもいっきり間違ってしまいましたが，
00:02 (clothoid) 隣接行列は点と点の関係を表した行列です。
00:02 (clothoid) で，次に，点と辺を表した行列，接続行列を
00:02 (Defolos) 他の例題でも２とか出てきますもんね
00:02 (clothoid) 見たいと思います。
00:02 (clothoid) そうですね＞defolosさん
00:03 (nesys) 対角成分はループしか表さないから必ず偶数になるってことですね。
00:03 (IPUSIRON) 本数と資料にはなってますが、他のページ見ると本数に関係なく1と説明しているところもありますね
00:03 (clothoid) 接続行列では，行に点，列に辺をあてはめ，接続の有無（こっちが接続の有無です！すみません）で行列を定義します。
00:04 (clothoid) ほんとうですか？たとえばどれでしょう？＞IPUSIRONさん
00:05 (clothoid) ループは1なので奇数かと＞nesysさん
00:05 (IPUSIRON) 接続のほうは辺と点の関係であって、隣接のほうは点と点の関係の行列と考えれば、0 or 1のほうが自然のような気がしますけどね
00:05 (nesys) ループの場合は次数と関係なく、1と書くのですか？
00:05 (IPUSIRON) 密なグラフを表現する場合には、行列を用いるのが簡単でよい。行列 A の第 (i, j) 要素は、辺 (i, j) が存在するときに 1, 存在しないときに 0 とすればよい。これで簡単にグラフが表現できる。 このような行列を隣接行列と呼ぶ。
00:05 (clothoid) 私もそう思いますが，行列とグラフを一対一に対応させるためには
00:05 (IPUSIRON) http://www.na.cse.nagoya-u.ac.jp/~reiji/lect/alg99/sec8-1.html
00:06 (clothoid) その定義だと，隣接行列とグラフが一対一には対応しない（というか，別のグラフになる）んでは・・・？
00:07 (dotdister) 隣接行列を元にしてグラフを書くときに、表の数字が本数でなければ、正確に書けないと思うのですが。
00:07 (IPUSIRON) まあここでは後ろの練習問題見る限り、1or0ぽいですね
00:07 (clothoid) 接続行列は0or1です。
00:07 (mudai) この場合本数よりも接続の有無の方が重要な気がします。
00:07 (IPUSIRON) http://www.infor.kanazawa-it.ac.jp/~koblab/home/d1504310/acm/dochtml/46_.html
00:08 (IPUSIRON) とか全部接続の有無ぽいです
00:08 (nesys) 0と1だけの場合、多重辺はどう表すのでしょう？
00:08 (Defolos) あ、そうか縦の１の数＝辺の数になるのかも
00:08 (mudai) １だと思います・・
00:09 (clothoid) すみません。ついていけてないのですが・・・
00:09 (IPUSIRON) 多重辺のときも1です
00:09 (clothoid) 隣接行列でも，この本では本数だが，他の場合は接続の有無で考えてそうだって結論ですか？
00:09 (mudai) この場合質問されているのは接続の有無ですから１だと解釈しました。
00:09 (nesys) 行列では完全にグラフを表せないということですかな？
00:10 (dotdister) 接続行列ならば可能だと思います＞nesysさん
00:10 (clothoid) そうではないと思いますが・・・？例題をとく限り＞nesysさん
00:10 (mudai) 表せそうな気がします。
00:10 (clothoid) 隣接行列まで0or１nisuruto
00:10 (clothoid) 0or1にすると表せないような気がしますが，
00:10 (mudai) どこから接続されているかと逆に考えると書ける気がします。。
00:10 (clothoid) 本数にすると表せるような気がします。
00:11 (nesys) 隣接行列だけでは不可能で、隣接行列と接続行列があって可能ってことですね
00:11 (mudai) 行の総数が次数になると思います。
00:11 (clothoid) いえ，元資料の定義を採用した場合は，どちらか片方の行列でＯＫなきがします＞nesysさん
00:12 (IPUSIRON) では元資料にのっとってすすめていきましょうか。問題があれば後で考えると
00:12 (clothoid) 接続行列の場合ですね。＞mudaiさん
00:12 (clothoid) そうしましょう＞IPUSIRONさん
00:12 (mudai) 隣接も・・
00:12 (nesys) うーｎ・・・そうしますか
00:13 (Defolos) 了解
00:13 (clothoid) 元資料の定義を採用した結果，隣接も・・・ですね。＞mudaiさん
00:13 (mudai) はい・・
00:13 (clothoid) えー，接続行列の具体例。p.34です
00:13 (clothoid) すみません。ありがとうございます＞mudaiさん
00:13 (clothoid) 点1は辺1,2と連結されているので
00:14 (clothoid) 1行1列目，3行1列目が1で，
00:14 (clothoid) 辺2と点1は繋がっていないので，2行1列目は0です。
00:14 (clothoid) その他の点，辺についても考えると，例のような接続行列がかけます。
00:15 (clothoid) 例題です。p.35
00:15 (clothoid) 与えられたグラフの次数列と接続，隣接行列を描きます
00:15 (clothoid) p.36
00:15 (clothoid) 次数列ですが，まぁ，数えて，小さい順に並べます。
00:15 (clothoid) 全部3ですから，並べなくて良いですが・・・。
00:16 (clothoid) p.37 
00:16 (clothoid) typoです。接続行列　ではなく　隣接行列です
00:16 (clothoid) メモ：↑直す
00:16 (clothoid) えー，
00:16 (clothoid) 与えられたグラフの点の数から
00:17 (clothoid) 行列のサイズが分かります。
00:17 (clothoid) そして，たとえば，点1に注目すると，点1と接続されている点は2,3,4であり，多重辺はありませんから，p.37のように
00:17 (clothoid) 一列目の数字がどのようであるかが，分かります。
00:18 (clothoid) 同様にして，点2，点3に注目し，行列の二列目，三列目と書いていけば，
00:18 (clothoid) p.38のように隣接行列が書けます
00:18 (clothoid) よろしいでしょうか？
00:19 (nesys) はい
00:19 (Defolos) うい
00:19 (mudai) おkです
00:19 (dotdister) はい。
00:19 (clothoid) p.39。接続行列です。
00:19 (clothoid) 今度は点の数と辺の数から行列のサイズが分かります。
00:19 (clothoid) そして，例えば点1に注目し，どのような辺と接続されているかを考えると，
00:20 (clothoid) 接続行列の一行目が書けます。
00:20 (clothoid) 同様に，点2，点3・・・と調べていけば，接続行列が書けます（p.40)
00:20 (clothoid) よろしいでしょうか？
00:20 (Defolos) おＫです
00:20 (nesys) はい
00:21 (mudai) おkです
00:21 (dotdister) はい。
00:21 (clothoid) p.41です。
00:21 (clothoid) 例題2.2
00:21 (clothoid) 同型写像を見つける，部分グラフをつくる，接続，隣接行列からグラフを作る，です。
00:22 (clothoid) p.42で，同型であることを確認するイメージを示しました。
00:22 (clothoid) θ，φが，それぞれ，どの点，どの辺に対応するか見極めたら，
00:22 (clothoid) p.43のように書き下し
00:23 (clothoid) 先ほど見た例と同様に，同値変形を繰り返すと（p.44）
00:23 (clothoid) 同型写像と同値関係が示せます。
00:23 (clothoid) 2, 3の組に対してやれと書いてあるので，
00:23 (clothoid) p.45にも具体例を書いておきました。
00:24 (nesys) うわー実際、学校のテストなんかであったらめんどい問題ですねー
00:24 (clothoid) ×同型写像の逆写像　○接続関数の逆関数　で　typoまで同じです（コピペしたことがバレバレですね）
00:24 (clothoid) めんどいですねー＞nesysさん
00:24 (clothoid) ｐ.46です
00:24 (clothoid) 部分グラフを挙げよってやつです。
00:25 (clothoid) 辺の削除や縮約を自由にやれば
00:25 (clothoid) 部分グラフになることを学びました
00:25 (clothoid) したがって私は，p.47のような
00:25 (clothoid) 部分グラフを挙げましたが，
00:25 (clothoid) その他にもたくさん考えられるので，
00:25 (clothoid) 考えてみてください。暇なときにでも。
00:25 (Defolos) あい＾＾；
00:26 (clothoid) p.48で，接続，隣接行列からグラフをかく問題です。
00:26 (dotdister) やはり、隣接行列は辺の本数ですか？
00:27 (nesys) 2とありますしね
00:27 (clothoid) p.49で，i行j列の数をa_ijという文字を使って表すことにしました。行列ではこうしたことをたまにやります。
00:27 (clothoid) そうです。本数です。＞dotdisterさん
00:27 (dotdister) 了解です。
00:27 (clothoid) 先ほどとは逆に
00:27 (clothoid) 行列のサイズから，点の数が分かります。
00:27 (clothoid) そして，対角成分が0であることから，ループなしです
00:28 (clothoid) そして，一列目，すなわち，点1に注目し，二行目，三行目を見ていくことで，p.50のようなグラフが書けます
00:28 (clothoid) かなり，詳しく書いたので，大丈夫だと思いますが。
00:28 (nesys) 先ほどは隣接行列の数値が0か1のみと言っていたので、混乱してましたが、問題解決です。
00:29 (clothoid) ほんと，すみません。私の間違いです。本数です。＞nesysさん
00:29 (clothoid) 同様に2列目，3列目に注目し，グラフを完成させます。(p.51）
00:30 (clothoid) 私のグラフと同型であれば
00:30 (clothoid) 形はどんなんでも良いです。
00:30 (clothoid) p.52接続行列です
00:31 (clothoid) 先ほどと同様で，サイズから点の数と辺の数を求め，1列目，2列目と注目していくと，行列が書けます。
00:31 (clothoid) こんな，説明で良いですかね。不安なことがあれば，言ってください。
00:32 (clothoid) p.54でへんてこな図を描いていますが，これがとりあえず答えで，これと同型であればOKです
00:32 (clothoid) p.55
00:32 (clothoid) 例題2.3です。
00:32 (clothoid) 点を5つ書き，
00:33 (clothoid) 条件に合うように，線を8本描きました。
00:33 (clothoid) やってみるしかないと思います。
00:33 (clothoid) 答えは，p.56
00:33 (clothoid) p.57です。行列もとめます
00:33 (IPUSIRON) 演習問題は各自の課題にして、例題までやってもらうことにしましょうか。時間もあれですし
00:34 (clothoid) 了解しました。
00:34 (Defolos) ですね
00:34 (IPUSIRON) もう少しです。がんばってください（笑）
00:34 (Defolos) ＾＾；
00:34 (clothoid) 先ほどまでと全く同様で，それぞれの点に注目して，行列の列を少しづつ求めていけば簡単にできます。
00:34 (clothoid) （説明がどんどん適当になってますｗ。というか，腱鞘炎が怖いですｗ）
00:34 (Defolos) （￣□￣；）
00:35 (clothoid) p.62
00:35 (clothoid) 次数列で，グラフ的か？グラフはあるのか？って問題です
00:35 (clothoid) p.63で回答を書いています
00:36 (IPUSIRON) お疲れ様です。
00:36 (clothoid) が，単純グラフが存在しないことの証明になっていません。
00:36 (mudai) おつかれさまですw
00:36 (Defolos) おつかれです〜
00:36 (dotdister) お疲れ様ですー。
00:36 (nesys) 乙ｗ
00:36 (clothoid) 矢印の順で徐々に書いていくと無理だよーってp.63で書いてあるので，よろしくお願いします。
00:36 (asuno_) お疲れ様ですー
00:36 (clothoid) ありがとうございました。
00:37 (clothoid) 全体的に，何か質問はありますか？
00:37 (Defolos) 隣接行列は結局どうなるのでしょう
00:38 (nesys) 隣接行列のループの場合の表示は2でなくて1ですか？
00:38 (clothoid) とりあえず，本数で進みましょう？
00:38 (Defolos) 了解です＞本数
00:38 (mudai) ネットワークプラグラミングとかやるときは１か０になりますけど・・ループと多重辺を服務場合は・・本数がわからなきゃ無理っぽいです・・
00:39 (clothoid) 元資料から例を探しています・・・>nesysさん
00:39 (dotdister) ループは２、、、ですかね？