21:00 (IPUSIRON) 時間ですね
21:00 (Defolos) はい
21:00 (nesys) 宜しくお願いします〜
21:00 (IPUSIRON) よろしくお願いします
21:00 (clothoid) おねがいしますー。
21:00 (dotdister) よろしくです。
21:00 (Defolos) よろしくお願いします
21:00 (mudai) しゃーーっす。
21:01 (Defolos) それでははじめちゃっていいのかな？
21:01 (IPUSIRON) どぞ
21:01 (mudai) いいともー！
21:01 (clothoid) はい
21:01 (Defolos) 第三回担当のDefolosです
21:01 (Defolos) それではまず第三回の目的ですが
21:02 (Defolos) 配布資料の1ページをご覧ください
21:02 (Defolos) 様々なグラフの例を挙げ、個々のグラフの特徴を理解する
21:02 (Defolos) 各グラフの名前と大まかな特徴を押さえ、後の学習をスムーズにする
21:03 (Defolos) というのが今回の目的です
21:03 (Defolos) つまりいろんなグラフを見てみましょう、ということだと思います
21:03 (Defolos) 後になってしまいましたが質問はいつでもOKです
21:03 (IPUSIRON) はい
21:04 (Defolos) 次に2ページですが
21:04 (clothoid) はい
21:04 (Defolos) 今回は予備知識として行列の掛け算が必要になると思います
21:05 (Defolos) グラフ理論と行列は深い関係性があるようで、今後も行列の知識が必要になる可能性はあります
21:05 (IPUSIRON) 確か後ろのほうの問題で行列の掛け算がでてきてましたね
21:05 (Defolos) はい
21:05 (clothoid) 前回も，グラフ理論を計算機にやらせる場合は行列による表現が大切だと出てきましたね。
21:06 (Defolos) 今回は行列の簡単なところだけ説明したいと思います
21:06 (Defolos) まず行列とは何か、ですが
21:06 (Defolos) 数字を行と列に並べたものです
21:07 (Defolos) 列は縦の部分、行は横の部分です
21:07 (Defolos) 行列のi行目、j列目の要素を特に行列の(i, j)要素といいます
21:07 (Defolos) ここまでは問題ありませんか？
21:08 (nesys) はい
21:08 (clothoid) はい
21:08 (mudai) おｋでしｗ
21:08 (Defolos) それでは次に3ページです
21:09 (Defolos) 行列の加減算はAとBの各i,j要素同士を加算減算します
21:10 (Defolos) これは図を見てもらえば分かると思います
21:10 (Defolos) 行列Aの1,1要素と行列Bの1,1要素はそれぞれ2と3ですので
21:11 (Defolos) 2+（-）3を計算して
21:11 (Defolos) ３（-1）になります
21:12 (Defolos) これを全部の要素に対して行えば加減算ができます
21:12 (Defolos) 次に4ページですが
21:12 (Defolos) 行列の掛け算です
21:13 (Defolos) 行列の掛け算はAの横要素とBの縦要素同士を掛けたものを足し合わせます
21:13 *nisi join #akademeia (~nisi@p1061-ipad214kobeminato.hyogo.ocn.ne.jp)
21:13 (Defolos) こんばんは
21:13 (IPUSIRON) こんばんは
21:13 (nisi) こんばんわ
21:13 (clothoid) こんばんわ
21:13 *IPUSIRON mode +o nisi 
21:13 (nesys) こんばんわ
21:14 (dotdister) こんばんは。
21:14 (carbon0) こんばんは
21:14 (Defolos) ここですが、配布資料に間違いがありまして・・・Aの縦要素を横要素に、Bの横要素と縦要素を訂正してください
21:14 (clothoid) 横要素と縦要素，なんか資料はtypoが直ってないような気がするんですが，私の持ってるものが古いだけでしょうか？＞Defolosさん
21:14 (Defolos) 申し訳ありません
21:14 (clothoid) ああ。了解です。
21:14 (Defolos) 直し忘れですTT
21:15 (clothoid) いえいえ。
21:15 (Defolos) 掛け算の結果の行列Cの(1, 1)要素はa11*b11+a12*b21になります
21:15 (Defolos) これは便利な公式がありまして
21:15 (Defolos) cij = ai1*b1j+ai2*b2j+ai3*b3j...ain*bnj
21:16 (Defolos) これを覚えておくと頭がこんがらがることなく解けます
21:16 (IPUSIRON) 実際に具体的な数値が与えらた問題解くときは実際に成分に右手と左手で指差してやるといいですよ
21:16 (Defolos) なるほど
21:17 (IPUSIRON) 今まで公式覚えてきてないので（笑）
21:17 (Defolos) Σ
21:17 (Defolos) 指差しながらでも間違うのはダメですか・・・
21:17 (IPUSIRON) 確かにそれ知ってると便利ですが、公式に代入とか考えると計算スピード落ちるので
21:17 (clothoid) 遠山啓の「数学入門」（岩波）に簡単な覚え方（というか，具体的な意味？）みたいのが載っていた気がします。
21:18 (IPUSIRON) どことどこを掛けるかを明確にするために指さすわけであって、計算は暗算しないで書いたほういいけどね
21:18 (Defolos) なるほど
21:18 (IPUSIRON) 指の指し方は、A×Bという計算なら
21:19 (IPUSIRON) Aは左側にあるから左手で指差し、Bは右側だから右手で指差す
21:19 (IPUSIRON) 左手の人差し指でAの(1,1)成分、右手でBの(1,1)成分からスタート
21:19 (Defolos) ふむふむ
21:19 (IPUSIRON) 左手はかならず横にスライド、右手は縦にスライドでいけますよ
21:20 (Defolos) なるほど
21:20 (nesys) 横×縦さえ忘れなかったらいいですね
21:20 (IPUSIRON) 実際に2行2列の計算で指の動きマスターすれば、何行何列になってもいけます
21:21 (Defolos) ここまでは大丈夫でしょうか
21:21 (IPUSIRON) 後、覚えておくと便利なのは、a行b列と掛け算可能なのはb行c列とか
21:21 (nesys) はい
21:21 (dotdister) はい。
21:21 (clothoid) はい
21:21 (Defolos) ふむふむ
21:22 (IPUSIRON) 後もうひとつ行列の掛け算で重要なのが、A×B＝B×Aが必ずしもいえないってことです
21:22 (nesys) ほぉ？Aの列とBの行は同じ値じゃないといけないのかぁ
21:22 (IPUSIRON) 整数だけの世界なら5×3=3×5ですが、行列の場合はそうとはいえないんです
21:23 (IPUSIRON) これを専門用語では非可換【ひかかん】といいます。
21:23 (Defolos) 同じ値になるものは可換なんですね
21:23 (IPUSIRON) 交換しても結果が同じことを可換だから、同じじゃなければ非可換ということね
21:23 (clothoid) 一行一列の縦に並べたものと横に並べたもの（または，その逆）をやると，こんがらがりますｗ
21:24 (IPUSIRON) 1行10列と10行1列は掛け算できます
21:24 (IPUSIRON) まああまりこんなのでないと思いますが
21:24 (clothoid) 一行一列　じゃ　一文字ですね。　すみません。
21:24 (IPUSIRON) 脱線しました。次進んでください
21:24 (IPUSIRON) 1行1列は1文字ですね（笑）
21:25 (clothoid) ｗ。
21:25 (Defolos) はい、IPUSIRONさんどうもありがとうございました
21:25 (Defolos) 次に5ページ目ですが
21:25 (Defolos) ここから17ページまで色々なグラフが登場します
21:26 (Defolos) まずその１つめ、空グラフです
21:26 (Defolos) 空グラフは変集合がないグラフです
21:26 (Defolos) 変→辺　失礼しました
21:26 (Defolos) 点だけのグラフ、辺がないグラフとも言えますね
21:27 (Defolos) 次に6ページの完全グラフです
21:27 (Defolos) 全部の点が隣接してるグラフです
21:27 (Defolos) これを難しく（厳密に？）言うと「∀v,v' ∈ V(G)に対し、v,v'を両端とする辺が唯一1個存在するグラフ」となります
21:28 (nesys) リターンAって全てのって意味でしたっけ…？
21:28 (Defolos) はい
21:28 (nesys) おｋ
21:28 (Defolos) 全ての、任意のという意味だったと思います
21:29 (Defolos) この完全グラフの辺の数は
21:29 (Defolos) グラフKの中の全ての2点のペアの数ですので
21:29 (Defolos) nC2 = n(n-1)/2になります
21:30 (Defolos) 箱の中から2つの球を取り出す　ってやつの式と同じですね
21:30 (Defolos) これは後の例題で詳しく出てきます
21:31 (IPUSIRON) この図はちょうど共通鍵暗号系の共有している鍵と同じ図ですね。どうでもよい話ですが
21:31 (Defolos) ほむ
21:31 (Defolos) 全ての人同士がひとつづつ鍵を持っているというイメージでしょうか？
21:31 (IPUSIRON) n人いる共通鍵暗号系での鍵の総数はnC2で、n人いる公開鍵暗号系の鍵の総数は2nなのです
21:32 (IPUSIRON) ひとりずつというか
21:32 (IPUSIRON) ペアでひとつってことね
21:32 (Defolos) あ、はい
21:32 (IPUSIRON) 脱線してしまいました。
21:32 (Defolos) あと、完全グラフは単純グラフでないとダメみたいです
21:33 (IPUSIRON) 単純グラフって何でしたっけ…？
21:33 (Defolos) 単純グラフはループ、多重辺を含まないグラフですね
21:33 (dotdister) 多重辺、ループのないグラフじゃないですか？
21:33 (dotdister) かぶりました。
21:33 (Defolos) ＾＾；
21:33 (IPUSIRON) どうもです。わかりました
21:34 (IPUSIRON) つまり、単純グラフと完全グラフの関係は
21:34 (IPUSIRON) 完全グラフ⇒単純グラフ　ってことですね
21:34 (IPUSIRON) 逆は必ずしもいえませんが
21:34 (Defolos) ⇒ってなんでしたっけ；；
21:34 (IPUSIRON) ⇒は「ならば」という意味です
21:34 (Defolos) なるほど
21:34 (IPUSIRON) 完全グラフなら、必ず単純グラフになってしまうという意味
21:35 (Defolos) おお、確かにそうですね
21:35 (IPUSIRON) 逆は簡単に反例出せるので、成り立たないことはわかるはずです
21:36 (Defolos) 三角形状にしたら完全グラフじゃないですからね
21:36 (IPUSIRON) 点3つの三角状？
21:36 (Defolos) あ4角形でした
21:36 (IPUSIRON) そです
21:36 (dotdister) では、その裏も偽ですか。
21:37 (IPUSIRON) 裏ということは、完全グラフでない⇒単純グラフでないということなので
21:37 (clothoid) （思いっきり戻ってすみませんが，私的に→の行列積は混乱します・・・。「指を動かさない」ので。講義は続けてくださいー。http://security2600.sakura.ne.jp/up/img/381.jpg）
21:38 (IPUSIRON) 裏は偽ですね
21:38 (dotdister) はい。
21:38 (IPUSIRON) 裏とか逆とか対偶とか、皆さん覚えてますか？
21:39 (IPUSIRON) 覚えてないなら簡単に説明しますが
21:39 (dotdister) 今、授業でやってますから、ダイジョブです。
21:39 (nesys) 覚えてます〜
21:39 (Defolos) 覚えてないです、すいませんTT
21:39 (clothoid) 裏　と　逆　が　どっちがどっちか　覚えられないんですが・・・
21:39 (clothoid) 対偶は　全部否定しちゃえ　みたいに　覚えてるんですけど。まずいっすかね？
21:39 (IPUSIRON) 「A⇒B」の裏が「Aでない⇒Bでない」、逆が「B⇒A」、対偶が「Bでない⇒Aでない」ですよ
21:40 (IPUSIRON) 対偶は裏と逆の組み合わせです
21:40 (Defolos) なるほど
21:40 (clothoid) おお。了解です！
21:40 (IPUSIRON) 「でない」は「否定」ということです
21:40 (IPUSIRON) 「2は整数である」の逆はもちろん成り立ちませんよね
21:41 (clothoid) 逆　は　仮定と結論を　「逆」にする　って覚え方でＯＫですか？
21:41 (IPUSIRON) 「整数は2である」って変ですもの（笑）
21:41 (Defolos) なるほどー
21:41 (IPUSIRON) OKです＞clothさん
21:41 (clothoid) なるほどです。
21:41 (IPUSIRON) 先どうぞ
21:42 (Defolos) 了解
21:42 (Defolos) では次、7ページに行きます
21:42 (Defolos) 正則グラフですが、どの点の次数も全部同じグラフです
21:43 (Defolos) これも難しく言うと∀v ∈ V(G)に対し、dev(v) = rとなります
21:43 (Defolos) Gの中の全ての点の次数は共通にrという意味ですね
21:43 (clothoid) めちゃめちゃ細かくて申し訳ないですが，　ハイフンを入れるべき？＞文中の　3正則グラフ
21:44 (nesys) 完全グラフ⇒正則グラフなのかな
21:44 (dotdister) 違うと思います＞nesysさん
21:44 (Defolos) 入れるべきなのかなぁ。私はしょっちゃいましたけど＾＾；
21:45 (nesys) 完全グラフのそれぞれの点の次数は同じではないんですか？
21:45 (clothoid) 全部の点と繋がって無くても　正則グラフは考えられるのでは？＞nesysさん
21:45 (nesys) あぁなるほど
21:45 (Defolos) 前の例の四角形もそれですね
21:45 (dotdister) 完全グラフに辺を一本づつ増やしても正則グラフになると思います。
21:46 (dotdister) ぁ、もしかして正則グラフって単純グラフですか？
21:46 (Defolos) 多重辺は認められないのでは？
21:46 (Defolos) 正則グラフには単純グラフであることという条件はなかったと思います
21:46 (clothoid) ループがあっても正則グラフにはなりえるのでは？＞dotdisterさん
21:47 (dotdister) 全ての点をループさせればなりますね。＞clothoidさん
21:47 (clothoid) そうですね。ループあると単純グラフではないですから，正則は単純じゃないってことになりますね＞dotdisterさん
21:48 (dotdister) はい、そうですね。
21:48 (IPUSIRON) （先ほどの話まとめておいて、画像にしました。忘れたら確認してください。http://security2600.sakura.ne.jp/up/img/382.jpg　）
21:48 (Defolos) ありがとうございます
21:49 (clothoid) （ありがとうございます。IPUSIRONさん）
21:49 (Defolos) あと、3-正則グラフは3価グラフとも言われるようです
21:50 (dotdister) ほう。
21:50 (nesys) rが3の場合だけですか？
21:50 (Defolos) 見たいです
21:50 (nesys) なるほど
21:50 (Defolos) 私が調べた限りでは4価グラフのようには使わないっぽいのです
21:51 (clothoid) なんとなく，r=3以外の場合も言う気がしますけど・・・
21:51 (Defolos) もしかしたら言うのかもしれません
21:51 (nesys) 3価グラフは完全グラフですね
21:51 (clothoid) 了解です。＞Defolosさん
21:51 (Defolos) 調査不足ですいません；；
21:52 (clothoid) いえいえ＞Defolosさん
21:52 (Defolos) 3-正則グラフはK4ですね
21:53 (dotdister) そうですね。
21:53 (nesys) あれ？3価って点4つなんですか
21:53 (dotdister) ３価＝次数３ってことでしょう。
21:53 (Defolos) はい
21:53 (nesys) なるほど
21:54 (nesys) でもページ7のグラフの次数は4つでは？
21:55 (nesys) 4-regular graphってことですか？
21:55 (Defolos) あ
21:55 (dotdister) そうですね。＞nesysさん
21:55 (IPUSIRON) 多分4正則グラフかも
21:55 (nesys) 了解です
21:55 (Defolos) これはミスですTT
21:56 (Defolos) 点の数を書いてしまった・・・
21:56 (Defolos) えと、次行ってよろしいでしょうか
21:56 (IPUSIRON) はい
21:57 (nesys) はい
21:57 (Defolos) 8ページ、プラトングラフです
21:57 (Defolos) これは後の例題でいきなり出てくるので
21:57 (Defolos) ページを設けてみました
21:57 (nesys) 名前がプラトンというところが気になるなｗ
21:58 (Defolos) プラトングラフはプラトン立体の辺の点だけからなるグラフみたいです
21:58 (Defolos) プラトン立体から面を取り除いたイメージでしょうか
21:58 (IPUSIRON) そうですね。グラフ理論は点と線だけの世界なので（笑）
21:59 (dotdister) プラトン立体という単語がわからないのですが。
21:59 (Defolos) それで、そのプラトン立体というのは通常の３次元上に実現できる正多面体です
21:59 (dotdister) 了解です。
21:59 (Defolos) これは数が決まっていて
21:59 (Defolos) その図にあげた５つだけしかないようです
21:59 (IPUSIRON) ケプラーはプラトン立体を使えば太陽系の形を記述できると考えたという雑学もあります。
22:00 (Defolos) ほほー
22:00 (nesys) 正n面体って20が最高！？それかプラトングラフの最高が20なだけか
22:01 (clothoid) 三次元では考えられるのが，正20面体までってことですか？
22:01 (IPUSIRON) そうです
22:01 (Defolos) ３次元では書けない正多面体も考えると２０以上あるのかも
22:01 (clothoid) へぇー！
22:01 (mudai) あんかまだいけそうな気もしますねｗ
22:01 (Defolos) ですよね
22:01 (clothoid) うん。しますねｗ
22:01 (nesys) 20が最高とは意外ですね
22:01 (IPUSIRON) 数学的に証明されています＜3次元ではこれらだけだってこと
22:01 (Defolos) そうなのですか
22:02 (clothoid) 正無限面体が球だ！とか言ったら駄目ですか（苦笑
22:02 (mudai) 俺もそれ思いましたｗ
22:02 (Defolos) 球って不思議ですよね
22:03 (clothoid) じゃぁ考えるの辞めますｗ＜数学的に証明されてる＞IPUSIRONさん
22:03 (mudai) なんか球より玉って発音が好きｗ
22:03 (IPUSIRON) いえ同じ形以外をつかったりすれば
22:03 (IPUSIRON) 球に近づけますよ
22:03 (nesys) 純真な球に点と線ってありえるんですかね（グラフ理論と関係あるのか？
22:03 (IPUSIRON) サッカーボールはそうですよね
22:03 (IPUSIRON) 2つの図形の組み合わせ
22:04 (Defolos) なるほど
22:04 (clothoid) なるほど
22:04 (IPUSIRON) フラーレンとかはかなり球に近いです　フラーレン
22:04 (IPUSIRON) http://www.mcfullerene.com/world/index.html
22:04 (clothoid) おー。C60
22:05 (nesys) ほぉ＠っとかメルアド以外で始めてみたｗ
22:05 (IPUSIRON) ただフラーレンの場合、全部6角形ですが、大きさのことなるのがあるので
22:05 (mudai) なんかよく見ると気持ちわるいですねｗ
22:05 (IPUSIRON) 正ではないですね
22:05 (Defolos) あ、なるほど
22:06 (Defolos) この立体とプラトンがどう関わったのかは未調査です
22:06 (clothoid) naruhodo
22:06 (IPUSIRON) プラトンは数学的にその5つだけしかないって示したんではなくて、確か直感的に経験的に示したんではないかな
22:06 (nesys) すごいな
22:07 (Defolos) 経験で示せるものなんですか・・・
22:07 (nesys) アインシュタインも相対性理論を証明しないで導き出しましたからね
22:07 (Defolos) Σ
22:07 (clothoid) 感で言ってみたってだけじゃ・・・ｗ＜経験的に示す
22:07 (Defolos) ＾＾；
22:08 (clothoid) ふぇるまーの定理とか，感っぽい説とか　あった気がするｗ
22:08 (IPUSIRON) http://jma-healing.com/oraclecard/crystal6.html
22:08 (IPUSIRON) こんなの売ってました
22:09 (Defolos) おお
22:09 (clothoid) 安い！ｗ
22:09 (Defolos) ほ、ほしい・・
22:09 (nesys) 完売ｗ
22:09 (Defolos) さて、次に行ってよろしいか？
22:10 (nesys) はい
22:10 (mudai) よろしゅうおま
22:10 (IPUSIRON) どうそ
22:10 (IPUSIRON) ぞ
22:10 (Defolos) ９ページ、閉路グラフです
22:11 (Defolos) 次数が２の正則連結グラフで、ぐるっと繋がってるグラフです
22:11 (Defolos) 次の１０ページですが
22:12 (Defolos) その閉道グラフから辺をひとつ取り除いたものが道グラフです
22:12 (Defolos) あ、道→路です
22:13 (Defolos) 次の１１ページ、車輪ですが
22:13 (nesys) 路と書いてみちと読む？
22:13 (Defolos) あ、これは
22:13 (Defolos) へいろ　と打って出てこなかったもので
22:14 (Defolos) 別々に変換したからです
22:14 (nesys) あぁそっちか了解
22:14 (Defolos) それで、車輪は閉路から点をひとつ取りまして
22:15 (Defolos) 閉路の真ん中に点を追加し
22:15 (Defolos) ほかの全部の点からさっきは位置した点に辺をつなぐとできます
22:15 (Defolos) この辺はスポークというらしいです
22:15 (nesys) 追加する点って真ん中じゃないといけないんですかね？
22:16 (Defolos) んー
22:16 (Defolos) たぶん真ん中が好ましいかと・・・
22:16 (nesys) 真ん中の点が円の外にあって、全ての点に繋がってるグラフは車輪なのだろうか？
22:16 (dotdister) C5からC４にするとき点を取る必要はありますか？
22:16 (Defolos) あくまで解説しやすくするためですので
22:16 (clothoid) グラフ理論的には同型だから，スポークがどこにあっても良いのでは？
22:16 (IPUSIRON) どこに追加しても、結局はみんな同型だと思いますよ
22:16 (Defolos) ぐにっと持ってくると考えてもらえれば良いです
22:17 (nesys) ですよね　了解です
22:17 (Defolos) ちなみに自転車のホイールの同じ部分もスポークといいます
22:18 (Defolos) では次、ピータースングラフです
22:18 (mudai) すげｗ
22:18 (Defolos) これはペテルセングラフといわれるほうが多いらしいです
22:19 (mudai) うまいこと考えたなぁ・・
22:19 (clothoid) あ，私もdotさんと同様点を一つ取る意味が分からないのですが・・・＜車輪
22:19 (Defolos) 点をとると書いたのは説明しやすくするためです
22:19 (mudai) とらなくてもいいんじゃないですか？
22:19 (clothoid) 了解です。
22:20 (dotdister) 同じく、了解。
22:20 (nesys) 図のような形状って曖昧な定義ですね
22:20 (Defolos) ピータースングラフはこの形自体に意味があるようです
22:21 (Defolos) 多分同型なだけでは問題を解くのに都合が悪いのではないでしょうか
22:21 (clothoid) 人名ですかね？＜ぴーたーすん
22:21 (Defolos) 人の名前みたいです
22:21 (nesys) おぉすげぇこの形で3正則グラフとは
22:21 (clothoid) 了解。
22:22 (Defolos) で、３正則グラフの代表みたいですね
22:22 (Defolos) ここまではOKでしょうか
22:22 (clothoid) はい
22:22 (nesys) おｋです
22:23 (Defolos) 次は１３ページの２部グラフです
22:23 (Defolos) グラフGの点集合を、二つの素な集合AとBに分け、Gの全ての辺はAの点とBの点を結ぶようなグラフ
22:23 (Defolos) です
22:24 (Defolos) 素名集合とは
22:24 (Defolos) 名→な
22:24 (Defolos) AとBに同じ値が出てこないという意味です
22:25 (nesys) 点に値があると？
22:25 (clothoid) 値というか要素？
22:25 (Defolos) 値というより
22:25 (Defolos) 点１、点２などのように分けたときに
22:25 (Defolos) AとBに共通して含まれる点がないような集合ですね
22:26 (nesys) 番号を振るわけか
22:26 (Defolos) で、
22:27 (Defolos) 集合Aに含まれる点と同じくAに含まれる点とは結びつかないグラフが２部グラフです
22:28 (Defolos) これを集合Aの点と集合Bの点が一本づつの辺で結ばれたグラフは次の１４ページ
22:28 (Defolos) 完全２部グラフと呼ばれます
22:29 (Defolos) この中でもK1,nは特に星グラフというらしいでうs
22:29 (Defolos) 点の数はr+s、辺の数はr*sになりますね
22:30 (Defolos) 次は１５ページのK立体です
22:30 (Defolos) 各点をベクトルに対応させたグラフです
22:30 (nesys) これn部グラフとありますよね？（2部に限らず
22:31 (Defolos) あ、２部位以外にもあります
22:31 (dotdister) 後の例題に完全三部グラフはありました＞nesysさん
22:31 (nesys) おｋ
22:31 (IPUSIRON) 完全n部グラフは
22:32 (IPUSIRON) 多分グラフの点の色の塗り分けだと思います
22:32 (IPUSIRON) n色の
22:32 (IPUSIRON) 線で結びつく隣り合う点は違う色を使うとう制限の中でね
22:33 (Defolos) なるほど
22:33 (IPUSIRON) 完全二分グラフの例見ればわかると思いますが、全部線で隣り合うたびに色が変化してますね
22:33 (Defolos) あ、本当ですね
22:34 (nesys) ぉーほんとだ
22:34 (Defolos) 次のK立体は分かりますでしょうか
22:35 (Defolos) それぞれの点を座標に当てはめて
22:35 (clothoid) k立方体は完全kグラフですか？
22:35 (Defolos) 完全ではありません
22:36 (nesys) ベクトルって方向がなくてもいいんですか？
22:36 (IPUSIRON) 完全kグラフじゃなくて完全2部グラフですよ
22:36 (Defolos) いえ
22:36 (clothoid) k個の点を，それぞれk部に分けると考えれば完全k部グラフになりますか？
22:36 (clothoid) なくてもいいです＞nesysさん
22:36 (nesys) なるほど
22:36 (Defolos) 例で見ますと0,1,1と1,0,0は繋がらないように思えるのですが
22:37 (clothoid) ああ，なるほど。りょうかいです。
22:37 (IPUSIRON) それだとそういえますが＞clothさん
22:37 (IPUSIRON) 定義みると
22:37 (IPUSIRON) 1 or 0とうことと2部グラフのAに属するBに属するが対応しているんだと思います
22:37 (IPUSIRON) Aに属する＝白に塗る、Bに属する＝黒に塗る
22:38 (clothoid) なるほどです。
22:39 (Defolos) これ、私は非常にわかりにくかったのですが
22:39 (clothoid) ベクトル空間 - Wikipedia
22:39 (clothoid) http://ja.wikipedia.org/wiki/%E3%83%99%E3%82%AF%E3%83%88%E3%83%AB%E7%A9%BA%E9%96%93
22:39 (clothoid) ＞nesysさん。ちょっと，数学すぎですが。ベクトル。。。
22:39 (IPUSIRON) k次だと難しいので、3次で考えれば十分かもしれませんね
22:40 (Defolos) 適当に点を配置して、それを２進数で対応させる・・・のような感じだと思います
22:40 (Defolos) これをうまく並べるとn次元の立体になるそうなんですが
22:41 (IPUSIRON) 逆に考えるとわかりやすいかも
22:41 (nesys) ベクトルとはベクトル空間のことを指していたんですね
22:41 (clothoid) ベクトル空間の元のことだと思います＞nesysさん
22:41 (IPUSIRON) まず3次立方体を書いてから、その頂点に黒・白の点を配置して、うまく隣り合うのは同じにならないようにすれば、それが結局3立方体になってますよ
22:42 (Defolos) みたいですね
22:42 (Defolos) これでご理解いただけましたでしょうか？
22:43 (nesys) はい
22:43 (IPUSIRON) おｋです
22:43 (clothoid) おｋです
22:43 (Defolos) （説明が下手で申し訳ありません）
22:43 (clothoid) （いえいえ）
22:43 (Defolos) 次は１６ページ、単純グラフの穂グラフです
22:43 (Defolos) 穂→補
22:44 (Defolos) 点集合V(G)を持ち、Gの補グラフの2点が接するのはGにおけるその2点が隣接していない場合のみに限るような単純グラフ
22:44 (Defolos) となっています
22:44 (Defolos) 前繋がってたところとはつながないで、前繋がってなかったところとつなぐようなグラフ
22:44 (Defolos) と考えればよろしいかと
22:45 (clothoid) 集合と補集合，事象と余事象みたいな感じっすかね・・・。
22:45 (Defolos) そんな感じではないでしょうか
22:45 (clothoid) 了解です。
22:45 (IPUSIRON) そうだけど、注意は補集合をとっても、点は共通してるってことですね
22:45 (Defolos) 元のグラフと補グラフを足しあわせると完全グラフになります
22:45 (Defolos) あ、そうですね＞点は共通
22:46 (clothoid) おお。了解です。＜補集合の注意
22:46 (Defolos) 完全グラフの補グラフは空グラフです
22:46 (Defolos) その逆はいえないらしいですので、注意がいりますね
22:47 (Defolos) 完全二部グラフの補グラフは2つの完全グラフを足し合わせたものになります
22:47 (Defolos) 図を見てもらえれば分かるかな
22:47 (Defolos) 黒い点だけの完全グラフと
22:48 (Defolos) 白い点だけの完全グラフが重なったグラフになってます
22:48 *mudai quit (Ping timeout)
22:48 (Defolos) えと、ここまではOKでしょうか
22:49 (IPUSIRON) 上の例ですが、例えば完全グラフK3の補グラフは空グラフ￣K3になるけど、3点だけはぽつんと残っている状況ですね
22:49 (Defolos) はい
22:49 (IPUSIRON) 空グラフN3でしたね
22:49 (clothoid) 完全二部グラフの補グラフは2つの完全グラフを足し合わせたもの　ってのが分からないんですが
22:50 (Defolos) 完全２部グラフは黒としろが交互に繋がってるグラフですので
22:50 (Defolos) それの補グラフは黒と黒が繋がり、白と白が繋がるグラフになります
22:50 (clothoid) はい
22:51 (Defolos) 黒い点だけに注目すると
22:51 (nesys) あー補グラフの作り方に悩んでいましたが、自分と繋がっているものを全て切り離し、繋がっていないものに繋いだものってことか
22:51 (Defolos) ですね
22:51 (clothoid) 2つの完全グラフをたしあわせる　ってのは　どういうことですか？
22:51 (Defolos) あ、それは
22:52 (Defolos) 重ね合わせる
22:52 (Defolos) と考えてもらっていいと思います
22:52 (IPUSIRON) 足すというのは2つのグラフをまとめてひとくくりにひとつのグラフに考えるということですよ
22:52 (dotdister) 黒で構成された完全グラフと白で構成された完全グラフを重ねるってことですか。
22:52 (Defolos) はい
22:52 (clothoid) ああ　分かりました！！
22:52 (Defolos) ただ、それらをひとつのグラフとして扱うということで
22:53 (Defolos) ご理解いただけました？
22:53 (clothoid) はい！
22:53 (clothoid) （すみません，理解遅くて。）
22:53 (IPUSIRON) 例えば、K1,3の完全二部グラフがあって、それの補グラフと考えるとK3（色つきだが）とK1のあわせたひとつのグラフってことです
22:53 (Defolos) あの、ところでmudaiさんが落ちてしまったようなのですが
22:53 (Defolos) このまま続けていいのでしょうか
22:53 (IPUSIRON) 戻ってきたら落ちてからのログを送信すればいいので、先に続けてOKだと思います
22:54 (Defolos) 了解しました
22:54 (Defolos) ここまでが色々なグラフの例でした
22:54 *mudai join #akademeia (~mudai@p6233-ipad05takakise.saga.ocn.ne.jp)
22:54 *mudai quit (Connection reset by peer)
22:54 (Defolos) 次のページからは問題をとくことになります
22:54 (Defolos) おかえりです
22:54 (dotdister) おかえりです。
22:54 *mudai join #akademeia (~mudai@p6233-ipad05takakise.saga.ocn.ne.jp)
22:54 (Defolos) それでは続けますね
22:55 (nesys) はい
22:55 (clothoid) 具体例の話，了解です。K1=N1ですかね。。。＞IPUSIRONさん
22:55 (Defolos) １７ページ　グラフにまつわるパズル-8つの円の配置問題です
22:55 (clothoid) おかえりです。
22:55 (mudai) すんませんｗ汗
22:56 (Defolos) 問題は資料に書いてあるとおりです
22:56 (Defolos) まずここでは2つのポイントに着目します
22:56 (Defolos) １．アルファベットの並び方の特徴を考えると、AとHがカギになります
22:56 (Defolos) ２．グラフの各点の次数を考えると#1,#2は最も次数が多いという特徴があります
22:57 (Defolos) #1,#2は次数が6ですので
22:57 *clothoid mode +o mudai 
22:57 (Defolos) AかH以外は配置することができません
22:57 (Defolos) えと
22:57 (Defolos) もし仮に#1にBを配置したとします
22:58 (nesys) それ以外だと最大5つとしか繋げられないからですね
22:58 (Defolos) この場合、隣接しないアルファベットは
22:58 (Defolos) はい＞nesysさん
22:58 (Defolos) D,E,F,G,Hの5つだけですが#1の次数は6ですので
22:59 (Defolos) 残るひとつの辺で必ずBと隣接するものがでてきてしまいます
22:59 (Defolos) 具体的にはAかCですね
22:59 (Defolos) このことから#1,#2にはAかHしか配置できません
23:00 (Defolos) 後は#1が隣接しない点である#8に
23:00 (Defolos) Aと隣接するアルファベットであるBを起きます
23:00 (Defolos) 起きます→置きます
23:01 (Defolos) 同じように#2が隣接しない点#7にGを置きます
23:01 (Defolos) で、あとは適当に配置しますと
23:02 (Defolos) #1=A,#2=H,#3=D,#4=F,#5=C,#6=E,#7=G,#8=Bってな感じになります
23:02 (Defolos) OKでしょうか
23:02 (IPUSIRON) 数独やる人はこういうパズルは経験的にピンと来るかもしれませんね
23:02 (Defolos) ほほー
23:02 (nesys) おｋです
23:03 (Defolos) 次は18ページ　グラフにまつわるパズル-急性精神病パズルです
23:03 (Defolos) 問題は書いてあるとおりですね
23:03 (Defolos) cube1からcube4までをある条件に合うように積み上げる問題です
23:03 (clothoid) これ難しいっすね。
23:03 (Defolos) はい
23:04 (Defolos) 普通にブロックをがちゃがちゃやってると
23:04 (Defolos) すごいたくさん試さなくちゃダメらしくて
23:04 (Defolos) 即席発狂機ともいわれてます
23:04 (Defolos) なんとなく理由がわかりますね
23:05 (Defolos) まぁ、どの面を左にするかとか上にするかとか
23:05 (Defolos) キューブをぐるぐるいじくる問題です
23:05 (Defolos) これをグラフ理論を使ってスマートに解こうというのが今回の問題ですね
23:05 (clothoid) なんで，問題の手順に従って考えると，うまく問題がとけるのか，直感的に分からないんですが
23:06 (Defolos) んー
23:06 (Defolos) 私もはじめ何をやってるのかわけわかりませんでした
23:06 (Defolos) 今も分かってないところ多いように思いますが・・・TT
23:07 (Defolos) まぁ、見ていきましょうか
23:07 (Defolos) まずそれぞれのキューブの展開図がありますね
23:07 (clothoid) はい。
23:08 (Defolos) それを組み立てたときに平行しあう面同士を辺で結びます
23:08 (Defolos) 立方体には6つ面がありますので
23:08 (Defolos) 辺は各キューブで３つづつあります
23:08 (Defolos) 展開図を組み立てたときに
23:09 (Defolos) 左右の組、上下の組、前後の組がそれぞれ平行な面倒氏ですね
23:09 (Defolos) 面同士・・・の間違い
23:09 (Defolos) 例としてキューブ１の場合
23:10 (Defolos) 緑を前面にしますとうえは赤、下は黄、左は青、右は赤、後ろも赤ですね
23:10 (Defolos) 前の面と平行になる面は後ろの面ですので
23:11 (Defolos) 赤と緑を辺で結びます
23:11 (Defolos) 上から見下ろした図　とかいうのがそれを表した図です
23:11 (Defolos) こんな感じで全部の組を辺で結びまして
23:12 (Defolos) 全部のキューブに対してこれを行います
23:12 (Defolos) これでとりあえずステップ1は終わりです
23:12 (Defolos) ここまでは大丈夫でしょうか
23:13 (nesys) はい
23:13 (mudai) 一応やってることはわかるんですが・・意図はわかりませｎ・汗
23:13 (clothoid) はい
23:13 (IPUSIRON) おｋです
23:13 (Defolos) 意図は平行しあう面を関連付けておくことで
23:13 (Defolos) おかしな選び方を防ぐ役割があるのだと思います
23:14 (Defolos) 例えばキューブ１において
23:14 (Defolos) ｙを前面に置いたら後ろの面にｇを置くことはできませんね
23:14 (mudai) はい
23:15 (mudai) おｋですｗ
23:15 (Defolos) ステップ3で足しあわせたグラフから部分グラフを作りますので、そのときに必要な条件だと思われます
23:15 (mudai) 了解です！
23:16 (Defolos) それではステップ2へ行きます
23:16 (clothoid) たとえば，注目する面が平行な面ではなく，隣り合う五つの面として同じ事をやっても，うまくいかないんでしょうか？
23:16 (Defolos) うーん
23:16 (Defolos) この問題の考え方として
23:16 (clothoid) でも，グラフが複雑になるから，頭悪そうなとき方ですかね・・・。
23:17 (Defolos) 前後の組と左右の組の選び方というのが
23:17 (Defolos) 重要になりますので
23:17 (clothoid) はい。
23:17 (Defolos) 平行な面で考えたほうが楽な気がします
23:17 (clothoid) はい。
23:18 (Defolos) まぁ、ステップ2は先ほど作ったグラフを重ねるだけです
23:18 (Defolos) ここで注意が必要なのは
23:18 (Defolos) 辺がどのキューブのものなのかを明記しておくことです
23:19 (Defolos) これを忘れてしまいますと本来平行な面にないキューブ１のｙとｇが組になってることになっちゃいますので
23:19 (Defolos) ご注意ください
23:19 (Defolos) 重ね合わせたものは図を参照してください
23:20 (Defolos) 次にここから積み上げ方を考えます
23:20 (Defolos) 積み上げ方は前後の組と左右の組で考えます
23:20 (Defolos) 上下はほかのキューブが積み重なるので
23:20 (Defolos) 無視して良いです
23:21 (Defolos) ですので、左右にどの色の組を配置するか、前後にどの色の組を配置するかの2つだけ考えればOKです
23:22 (Defolos) ステップ３ではH1,H2を選ぶ問題になってますね
23:22 (Defolos) H1には前後の色の組み合わせ、H2には左右の色の組み合わせが現れるようになっています
23:23 (Defolos) ここで部分グラフHの条件を確認しますと
23:23 (Defolos) １．各cubeの辺をちょうど一本ずつ含む
23:23 (Defolos) ２．H1,H2で共通な辺が現れない
23:23 (Defolos) ３．次数2の正則グラフである
23:23 (Defolos) という条件でした
23:24 (Defolos) で、この条件がいる理由です
23:25 (Defolos) １．はキューブを4つ積み上げる問題ですから全部のグラフを使わないといけません
23:26 (Defolos) ステップ1で作ったcube1とかcube2とかの平行な色の組み合わせのグラフですね
23:27 (Defolos) ２．はキューブはそれぞれひとつつづしかないので、H1とH2で同じ辺が現れるとキューブを2つ使ってしまうことになります
23:28 (Defolos) 例えばR-Yという組み合わせを左右の組を表す部分グラフで使いますと
23:28 (clothoid) 色の関係が（前，後）＝（左，右）というのは，与えられたキューブ的にありえないって理解でよいですか？＜条件2
23:28 (Defolos) あ、そうです
23:29 (Defolos) R-Yを左右で使っちゃいますと、もう前後では使えませんよね
23:30 (Defolos) これはキューブ１において、ですけれど
23:30 (Defolos) ここまではOKでしょうか
23:31 (clothoid) 条件2って，step2でグラフを書いた時点で，満たされている気がするのですが，そんなことないですか？
23:31 (nesys) あーH1とH2って前後、左右のことだったのかー
23:31 (Defolos) はい＞nesysさん
23:31 (Defolos) えと
23:31 (Defolos) H1で選んだ後
23:32 (Defolos) H2でも同じ辺を選んじゃうと
23:32 (Defolos) ダメってのが条件２です
23:32 (clothoid) えっと
23:33 (Defolos) はい
23:33 (clothoid) H1のG→Rで，辺1を選んで，H2でもG→Rで，辺1を選らぼうとしても（選んでも），条件１to
23:33 (clothoid) 条件1と条件2に合うようなグラフは作れないような気がするのですが（同型を除いて）
23:34 (clothoid) 条件1と条件3の間違い↑
23:34 (Defolos) ごめんなさい、そこまで調べてませんでした
23:34 (clothoid) 了解っす。
23:35 (nisi) あの
23:35 (Defolos) はい
23:35 (nisi) 時間が押してるみたいなんで今日はこのあたりで巣連れ意
23:35 (nisi) 失礼の間違いです　で失礼します
23:35 (Defolos) あう。時間掛けすぎですかね・・・
23:36 (nesys) この問題が難しすぎです…
23:36 (Defolos) 手際が悪くて申し訳ないです
23:36 (Defolos) それではお疲れ様でした
23:36 (nisi) いえいえ、もう少しいれたらよかったのですが
23:36 (nisi) それでは
23:36 (clothoid) 私も，長引かせてるようで，すみません。おつかれさまです。
23:36 (nesys) お疲れさまですー
23:36 (nisi) おつかれさまです
23:36 *nisi part (Leaving...)
23:36 (mudai) おつかれっしたー
23:36 (Defolos) 条件2の意味はご理解いただけましたか？
23:37 (nesys) はい
23:37 (clothoid) はい。さっき，言いたかったのは，条件2って，そんなに考えなくても，自動的に満たされるんじゃね？ってことです。ありがとうございました。
23:37 (Defolos) あ、なるほど
23:37 (Defolos) 自動的に満たされるかどうかまでは考えていませんでした、すいません
23:38 (clothoid) いえいえ。了解です。
23:38 (Defolos) それでは条件３ですが
23:38 (Defolos) 2次の正則グラフであるというのは
23:38 (Defolos) 左右、前後というペアを点と辺で表しているためです
23:40 (Defolos) この条件３、ちょっと私の理解がいい加減な気がします・・・
23:40 (Defolos) これで分かりますでしょうか？
23:41 (mudai) おｋです。
23:41 (clothoid) ふむ。おｋです。
23:41 (Defolos) いい加減な説明ですいませんです
23:42 (clothoid) いえいえ。
23:42 (Defolos) それで、この条件に合わせて部分グラフを選びますと
23:42 (Defolos) と左右の組み合わせを表したグラフと前後の組み合わせを表したグラフができることになりますね
23:43 (Defolos) この部分グラフ通りに積み重ねますと
23:43 (Defolos) あら不思議！問題が解けます
23:43 (nesys) おぉ？
23:43 (clothoid) すげー
23:43 (Defolos) H1の辺1のところ
23:43 (clothoid) 頭のいいヤツにやらせて，ニヤニヤしてぇ（謎
23:43 (Defolos) GとRが関係付けられていますね
23:44 (Defolos) H1は前後の組を表していますので
23:44 (Defolos) キューブ１の前後はGtoRです
23:44 (Defolos) こんな感じで積み上げていきます
23:45 (Defolos) これで終わりなんですが、OKですかねぇ
23:45 (clothoid) 下から順に，cube1，２，３，４な必要はないですよね？
23:45 (Defolos) はい
23:45 (Defolos) ただ
23:45 (Defolos) 分かりやすいようにキューブ１を下にしてるだけです
23:45 (clothoid) 了解です。OKです。
23:46 (Defolos) それでは次に行きましょう
23:46 (nesys) なんか分かるようで分からないなぁ…
23:46 (IPUSIRON) 今日は次の例題3.1までやって終わりにしましょうか
23:46 (Defolos) 了解です
23:46 (Defolos) それでは例題３．１ですが
23:46 (Defolos) まず接続行列を求めます
23:47 (Defolos) 接続行列は前回やりました、点iと辺jが繋がってるときに
23:47 (Defolos) 1をつけ、繋がってないときに０をつけます
23:48 (Defolos) 例えば点1と辺4がつながっている場合には行列の(1, 4)成分に1と書きます
23:48 (Defolos) で、問題に戻りまして
23:48 (Defolos) グラフGについて考えましょう
23:48 (Defolos) 点1には辺1，2がつながってますので
23:49 (Defolos) 行列の(1,1),(1,2)成分を1にしましょう
23:49 (Defolos) 次に点2について考えます
23:49 (Defolos) 辺1,2,3,4がつながってますので
23:49 (Defolos) 行列の(2,1),(2,2),(2,3),(2,4)成分を1にします
23:50 (Defolos) こんな感じで全部の点に対して
23:50 (Defolos) どの辺と繋がってるかを考えます
23:50 (Defolos) 最後に１が入ってない成分を全部０にすると
23:50 (Defolos) 接続行列の出来上がりです
23:50 (IPUSIRON) ですね
23:50 (Defolos) 配布資料の図のようになります
23:51 (Defolos) 次に例題３．１の回答その２です
23:51 (Defolos) 接続行列は点iと辺jがつながっているかどうかとう行列でしたので
23:51 (Defolos) という・・・です
23:52 (Defolos) 列は縦の成分のことで、辺について点何と結びついているかをあらわすものでした
23:52 (Defolos) 握手補題により
23:52 (Defolos) 辺一本には両端に点があるはずですから
23:53 (Defolos) 点の数は常に２となります
23:53 (Defolos) 握手補題はひとつの握手に手が2本関与するというものでしたね
23:53 (Defolos) これは図に手に見えない手を描いて表しています
23:53 (clothoid) ＊ちなみに，これは接続行列からグラフを書くときに重要な視点です（前回資料参考）
23:54 (Defolos) どうもありがとうございます
23:54 (Defolos) すなわち接続行列の各列の和も2になりますね
23:54 (Defolos) これで21ページ終わりです
23:55 (Defolos) 次の22ページです
23:55 (Defolos) 行は横の成分のことでしたね
23:55 (Defolos) 点についてどの辺とむすびついているのかを表しています
23:56 (Defolos) 例えば点1が辺1と辺2につながっている場合
23:56 (Defolos) 接続行列の横の成分は(1,1,0,0)のようになりますね
23:56 (Defolos) 点に繋がる変の数は次数として定義されていましたので
23:57 (Defolos) 接続行列の各行の和は各点における次数を表していると言えます
23:57 (Defolos) ここまで大丈夫でしょうか
23:57 (clothoid) はい
23:57 (nesys) はい
23:57 (Defolos) 次で本日の最後となります
23:57 (clothoid) おつかれさまでしたー。
23:57 (Defolos) 23ページです
23:58 (clothoid) あ，まだでした。
23:58 (clothoid) すみませんｗ
23:58 (Defolos) まずは左辺から考えましょう＾＾；
23:58 (Defolos) 左辺の意味は
23:58 (Defolos) グラフGに含まれる全ての点vの次数を合計する　となります
23:59 (Defolos) 次に右辺ですが
23:59 (nesys) なるほど、そういう意味だったのかぁ
23:59 (Defolos) グラフGの辺集合の2倍
23:59 (Defolos) という意味ですね
23:59 (Defolos) すべての点の次数の和は
00:00 (Defolos) 回答その3から接続行列のすべての成分の和と言い換えることができます
00:00 (clothoid) これは握手補題じゃ？
00:00 (IPUSIRON) 行列を使うことでこの関係式が成り立つのはある種明らかぽいですね
00:01 (Defolos) はい
00:01 (IPUSIRON) 握手の補題を別の視点で見たという感じかな
00:01 (clothoid) おお。接続行列を定義すれば，握手補題の証明が一瞬？
00:01 (Defolos) といえますね
00:01 (Defolos) これって証明なのかな？
00:02 (IPUSIRON) 自明になっちゃってるわけですね
00:02 (IPUSIRON) 補助線引くと証明が簡単になるみたいに
00:02 (Defolos) なるほど
00:02 (IPUSIRON) 行列を考えて関係式が明らかになりたってしまったという状況ですね
00:02 (clothoid) 一般的ではないので，この解答にかぎると証明ではないでしょうが，自明になるから，証明といってもよさげ。
00:03 (Defolos) まあ、各列の和は常に2なので辺の数は接続行列の列の数*2となりますね
00:03 (IPUSIRON) つまり、握手の補題の証明が、接続行列の定義に内包された感じかなあ
00:03 (clothoid) なるほど。前回，握手補題の証明方法をバカみたいに考えてた・・・orz
00:04 (Defolos) これで示せたといって終わってよろしいのでしょうか＾＾；
00:04 (clothoid) というか，自分が接続行列定義したのに，気づかなかった・・・orz
00:04 (IPUSIRON) これ以降の問題は各自の自習ということでいいかもね。重要なところはまた別のところで登場するので
00:04 (clothoid) あ，おつかれさまですー。
00:04 (Defolos) お疲れ様です
00:04 (nesys) お疲れ様です〜
00:04 (dotdister) お疲れ様ですー。
00:04 (Defolos) あ、そうだ
00:04 (Defolos) 教科書のほう
00:05 (Defolos) 最後のページで1桁の引き算のミスがあるので
00:05 (Defolos) ご注意ください