グラフとネットワーク
電気通信大学情報理工学部情報・通信工学科
2017年度前学期
月曜2限 (10:40-12:10)
教室：西2-101
岡本 吉央
ショートカット：
講義資料 |
コメント |
試験・成績 |
公式シラバス |
履修上の注意 |
スケジュール |
過去の講義 |
過去の試験問題
講義資料
- 7/24 (13) 平面グラフ：モデル化
- 7/10 (12) 平面グラフ：数理
- 6/26 (11) 彩色：モデル化
- 6/19 (10) 彩色：数理
- 6/5 (9) 連結性：数理とモデル化
- 5/29 (8) 最大流：モデル化 (2)
- 5/22 (7) 最大流：モデル化 (1)
- 5/15 (6) 最大流：数理
- 5/8 (5) マッチング：モデル化
- 5/1 (4) マッチング：数理
- 4/24 (3) 木：数理
- 4/17 (2) 道と閉路：数理
- 4/10 (1) グラフの定義と次数：数理
コメント
- 7/24 (13) 平面グラフ：モデル化
- コメントありがとうございました．来週，講義はなく，再来週が期末試験です．しっかりと準備をしてきてください．
-
1学期間ありがとうございました。期末試験がんばります。
---
こちらこそありがとうございました．
-
ありがとうございました。期末試験もがんばります。
---
こちらこそありがとうございました．
-
この分野により一層興味を持てました。ありがとうございました。
---
こちらこそありがとうございました．
-
この2週間本当に疲れた
---
何があったのか知りませんが，おつかれさまでした
-
それなりに丁寧な講義だと思いました．ありがとうございました．
---
こちらこそありがとうございました．
-
半期の間，わかりやすい講義をありがとうございました．
---
こちらこそありがとうございました．
-
期末試験頑張りたいです。
---
しっかりと準備をしてきてください．
-
試験がんばるぞい！
---
しっかりと準備をしてきてください．
-
単位をとれるように頑張ります。
---
しっかりと準備をしてきてください．
-
期末試験がんばります
---
しっかりと準備をしてきてください．
-
期末試験がんばりたいです．
---
しっかりと準備をしてきてください．
-
夏休みだ〜その前にテストあるけど…
---
しっかりと準備をしてきてください．
-
ちゃんとレポートをやって出せれば去年の離散のように秀狙いもいけそうだったんですが去年はなかった実験のレポートに追われてムリでした...
---
うまく時間を使う，ということが求められているのかもしれません．
-
8/2提出締切の実験レポートが3つ重なっていて、それはもう (スケジュール的に) えらいことになっていますが、ここを乗り切って、グラフとネットワークの試験も乗り越えて、気分よく夏休みを迎えたいところです。
---
うまく時間を使う，ということが求められているのかもしれません．
-
夏休みが待ち遠しいです！
---
よい夏休みが迎えられるようにして下さい．
-
時間が無い！(実験，レポート，期末 etc...)
---
うまく時間を使う，ということが求められているのかもしれません．
-
演習問題を毎回解くのは大変でしたが，その分実力がついたのだと思います．ありがとうございました．今日以降にレポートの再提出を行った場合，期末試験の前に返却してもらうことは可能ですか？
---
実力がついたことを実感できたならば，よかったと思います．レポートの再提出は今後受け付けられません (期末試験前に返却できないからです)．ご了承ください．
-
授業お疲れ様でした。濃密でした。
---
こちらこそありがとうございました．
-
授業全体的に、勉強のしやすい形式でした。
---
勉強の仕方は人それぞれだと思いますので，自分の勉強の仕方を築いてもらえたなら，よかったと思います．
-
漫然と解いていた『美術館』のパズルも，よく考えるとグラフだった…この授業を通してまわりの物事がグラフに見えてきました。
---
まわりの物事がグラフに見えてくる，というのがこの講義で目指していたこと (グラフやネットワークとしてモデル化できるようになること) なので，その点では目標を達成しているように思います :-)
-
エキセントリックな美術館監視、p.37の図を見るに7人でもいけそうな気がしてきます。配置を変えれば5人でも…？
---
確かに，5人でもできますね．授業では，どんな美術館でもn/3人で監視できる方法を紹介したわけですが，それが監視に必要な最も少ない人数を与えるわけではないので，その点には注意をして下さい．
-
美術館定理とは不思議な名前ですね．つくった人は美術館が好きだったのでしょうか。
---
名前の由来は知らないのですが，「美術館定理」とか「結婚定理」とか，離散数学には不思議な名前の定理が多い気もします．
-
美術館定理が面白かったです。次の潜入の参考にします。
---
美術館は完璧に監視されているので，おそらく潜入の参考にはならないでしょう．;-)
-
任意の無向グラフGについて、Gは双対グラフ⇔Gは平面的グラフは成り立つのでしょうか？
---
「無向グラフの双対グラフ」という用語を定義しないと，成り立つかどうか考えることができないですね．講義でやったのは「領域分割の双対グラフ」あるいは「地図の双対グラフ」であって，「無向グラフの双対グラフ」というのは定義していません．
-
13-3を考えていましたが、グラフの外面を含めても3色で彩色ができるのですね．
---
「グラフの外面を含めても」という部分の意味がよく分からないですが，外面に注目するのはよい考え方です．
-
"$\lfloor$"，"$\rfloor$" や "$\lceil$"，"$\rceil$" はTeXで何を書いたら出力されますか．
---
\lfloorと\rfloorで"$\lfloor$"と"$\rfloor$"が，
\lceilと\rceilで"$\lceil$"と"$\rceil$"が出力されます．
-
美術館の監視員は高々[|V|/3]であるのは分かったのですが，下界や，最小化するアルゴリズムは存在しますか？
---
実際に $\lfloor n/3\rfloor$ 人必要な例が存在します．考えてみて下さい．その意味で，下界は $\lfloor n/3 \rfloor$ です．また，最小化についてですが，これはいろいろな意味で難しいことが知られています．美術館の頂点の座標がどれも整数であったとしても，最小化しようとするとき，監視員のおかれる座標として無理数が必要となる場合があることが知られています．(これは2017年に発表された論文で指摘された事実です．) また，最小化問題はNP困難です．その意味で，多項式時間アルゴリズムは存在しないと思われています．
-
近年，異常気候が増加しているように思えます。とにかく暑いです。子供のころの夏休みはもっとすごしやすい気温だった思い出があります。
---
「気候」と「気象」の区別が付けられるとよいです．
-
先週ハチにさされました．周りを気にしていたけれど、全然ハチがいたなど気づかず、突然痛みがして見たらハチにさされていてびっくりしました。思いもよらないところにもいるので気をつけなければいけないなと思いました．
---
私も1ヶ月半程前にハチに刺されました．
-
OPで岡本研見に行きました！パズル面白かったです．
---
お楽しみいただけて良かったです．(^^)
-
来期は是非クラフトネットワークの開講をお願いします
---
では，クラフトの不等式を使うことを検討してみます．
- 7/10 (12) 平面グラフ：数理
- コメントありがとうございました．来週は休講ですので，お間違いのないように，よろしくお願いします．
-
期末試験の範囲はどこからどこまでですか？ 最後の授業で出したレポートはどうなりますか？ 最後の授業の演習問題を提出する機会はありますか？
---
期末試験の範囲は第8回講義の最初から，第12回講義の最後までです．最後の授業で出したレポートは7/26に返却できるようにします．
-
7/24に提出した宿題はいつ受け取ることができるのでしょうか？
---
7/26に返却できるようにします．
-
夏休みまで残り1ヶ月テストやレポートに向けて時間を無駄にしないようにしたい
---
はい，計画を立てて進めるようにするとよいと思います．
-
いろいろな科目の期末試験が近く，レポートもたまっていたので，昨日と一昨日の休みは勉強したりレポートを進めたりする予定でした．しかし怠けてしまってほとんど何もしなかったです．どうしたら怠けずに過ごせるのでしょうか．
---
計画を立てて進めるようにするとよいと思います．
-
最近，勉強しなきゃなぁと焦燥感に駆られています。
---
計画を立てて進めるようにするとよいと思います．
-
授業後の演習時間で、毎回1問も解けずに終わってしまいます……
---
相談をするようにして下さい．ひとりで解こうと思っても難しいことはわかっていますし，そのような問題を出しているつもりです．
-
ついに資料の印刷に成功しました．
---
おめでとうございます．
-
立体モデリングってすごいですね！
---
これを本格的に味わうには『コンピュータグラフィックス』の授業を履修してもらうとよいのですが，カリキュラム上，なぜ『コンピュータグラフィックス』が4年後学期に置かれていて，置かれ続けているのか，私もよくわかりません．
-
平面的グラフの証明は直感的なものになってしまいがちのような気がするので気をつけたいです．
---
そうですね．気を付けて下さい．
-
「的」という言葉は便利だと感じました。
---
「合目的的」という日本語がありますが，ちょっと違和感があります．;-)
-
凸多面体のグラフは平面的グラフであることの証明はどこを参照すればいいでしょうか．
---
「stereographic projection」や「Schlegel diagram」という用語で調べていただくとよいのですが，ちゃんと証明を書いている文献はあまりないようです．『凸多面体の数学』という本がありますが，そこにはちゃんと書いてあります．
-
(やる気)-(授業のコマ数)+(友達の数)=1+(秀の個数)
---
「おいらの公式」でしょうか？
-
平面グラフの方が非平面グラフより見やすいことが多いのかなと思いました．
---
「graph drawing」という分野があって，それはまさにグラフを見やすく描くことに関する研究を行う分野です．様々な問題が活発に議論されていて，平面グラフもその中の重要なトピックになっています．
-
「数え上げ＋オイラーの公式」の部分で木を扱わないのは、木は平面的であることが分かっているからですか？
---
そうではありません．そこに書いてある証明に書かれていることが木に対しては正しくないからです．そのため，木に対しては別の証明が必要となるのです．
-
今回の講義スライドの20ページに、「辺数 $m\geq 0$ の平面グラフがオイラーの…」や「辺数 $m+1 \geq 0$ の任意の平面グラフ $G'$ を考える」とありますが、ここで「平面グラフ」と言っているところは「平面的グラフ」でなくて良いのですか？
---
「平面グラフ」で正しいです．「面」という概念は平面的グラフにはなく，平面グラフ (平面描画) にしかないのです．ただ，講義中，「平面グラフの頂点や辺」というのをちゃんと定義していなかったので，混乱があったかもしれません．平面グラフの頂点はグラフの頂点を表している平面上の点のことを指していて，平面グラフの辺とはグラフの辺を表している平面上の曲線のことを指しています．
-
↑外平面的グラフ
---
正しいです．;-)
-
ストレス発散でカラオケにいきたいです。
---
どうぞ ;-)
-
暑くて気持ち悪くなりました。
---
うちわや扇子を持ち歩くとよいと思います．お薦めします．
-
あつい日がつづいて、外に出るのがつらいです．
---
うちわや扇子を持ち歩くとよいと思います．お薦めします．
-
あつい夜が続いてつらいです
---
そうですね．寝ているときでも脱水症状になるそうなので，注意して下さい．
-
今年度から教授になられたのですね。おめでとうございます。
---
ありがとうございます．
-
好きなノート (A4, B5, 無地など) は何ですか．
---
方眼です．
-
冬休み，地元で同窓会があるらしいのですが出席するべきですかね？
---
出席するとよいと思います．よいことも悪いことも，いろんなことを感じることのできる貴重な機会ですし．
-
僕は先生の着ているTシャツで外を歩くことはできそうにないです．
---
Tシャツではないので大丈夫です ;-)
- 6/26 (11) 彩色：モデル化
- コメントありがとうございました．来週は休講ですので，お間違いのないように，よろしくお願いします．
-
五輪 (オリンピック) みたいですね．
---
2週続けてオリンピックネタですね ;-)
-
最近寝不足です
---
昼間にしっかりと疲れることが重要だと思います．メリハリのある生活を心がけたいですね．
-
そろそろ暑さが本格的になって来そうですね．
---
そうですね．体調の変化に気を付けて下さい．
-
雨で洗濯が間に合いません
---
いつ洗うのか，という選択が難しいですね．
-
採点おつかれさまでした。
---
ありがとうございます．(^-^)
-
しけんのさいてんおつかれさまでした！！！！！
---
ありがとうございました！！！！！
-
課題が山積みでテンションが上がってきました。
---
課題を愛し，課題に愛されて，テンションが上がってしまったのでしょうか．;-)
-
土日遊びすぎて課題がたまってしまい、大変焦っています。
---
講義の間，または前後に空いている時間があるとき，それを有効に使うことが求められていると思います．自分の時間割を見てみて，空いている時間をどのように自習に使うのか，ということを計画的に行うようにできると，時間が有効に活用できるようになっていけると思います．もう1つ重要なことは時間を区切ることだと思います．締切いっぱいまで一つのことに取り組むのではなくて，それにかける時間を前もって決めておき，その時間で終われるように進めていくのです．これも時間を有効に活用するための技術だと思います．
-
J4課題の締切日を間違えて覚えており、あと2日しかないことを朝友人に言われ絶望しました。
---
それは大変そうですね ;-) スケジュール帳を使いこなせるようになってください．
-
MICS実験に時間を取られてグラフとネットワークの演習問題の時間がなかなか取れません。休講の間にじっくり解く時間を作りたいです。
---
はい，是非お願いします．:-)
-
実験のレポート頑張ってる
---
文章を書いてまとめる，というのは重要な技法なので，しっかりと身に付けて下さい．
-
大学生のとき，どんな悩みを持っていましたか？
---
いろんな悩みがあったと思いますが，どんなときでもよい友に恵まれたと思います．
-
フリージャズは好きですか？
---
ガチャガチャしている感じがするので，個人的にはあまり好きではないです．
-
今日のピアノの曲が大変気に入ったので，教えて欲しい。
---
YouTubeを検索してでてきた適当なものなので，詳しく覚えていません．たぶんこれだったと思いますが，違うかもしれません．
-
期末試験の試験範囲は第何回の講義から第何回の講義までですか？ 予定だけでも良いので教えてもらえるとありがたいです。
---
予定ですが，第8回の最初から第12回の最後までです．予定なのであしからず．
-
極彩色
---
「ごくさいしき」ですね．これを「ごくさいしょく」と読んではいけないので注意して下さい．
-
区間グラフであるかどうかの判定が難しい．
---
実際は，線形時間で判定ができます．区間として表現するときにどのような条件が必要になるのか，考えてみて下さい．
-
11.5はスライドのP19と同じように証明できると考えました．
---
では，その方針で証明できるか試してみて下さい．
-
は単位円グラフですか？
---
単位円グラフではありません．講義でやった場合と同じように証明できますが，細かい場合分けがあるので，扱いませんでした．
-
区間グラフは単位円グラフを彩色として考えることで，より実用的なことをモデル化できて，おもしろいと思った。
---
そうですね．グラフだけを見るのではなくて，グラフを通して何ができるのかを見ることが重要ですね．
-
今回扱った2つのモデル以外に特殊な性質を持つグラフは存在するのでしょうか？
---
あります．例えば，次回扱う「平面的グラフ」はそのような特殊なグラフのひとつです．
-
彩色で考えるグラフが少し大きいのでこんがらがりました。
---
現実世界に現れるグラフはもっと大きいので，ご注意ください．;-)
-
全順序は具体的に何を指しているかがはっきり分からない．異なる全順序の例をお願いします．
---
前回 (第10回) の講義スライドの29ページと30ページを見て下さい．異なる全順序の例を挙げています．
-
○○の定理より〜って書くときに○○に日本語じゃない人を書くのがなんか恥ずかしい
---
では，「Hallの結婚定理」と書かずに「講堂の結婚定理」と書くことにして下さい (冗談です)
- 6/19 (10) 彩色：数理
- コメントありがとうございました．
-
今年のうちから，東京五輪が楽しみです．
---
国道20号線 (甲州街道) に沿って西に向かっていくと，西調布と飛田給の間辺りで，東京オリンピックのマラソン折り返し点がでてきます．是非見に行って，オリンピックに思いをはせて下さい．
-
好きなLinuxディストリビューションはなんですか？
---
最近Linuxを使っていないので，よく分からない，というのが実態ですが，以前はVineやCentOSを使っていました．
-
アイドルが結婚宣言しました。どう思いますか．
---
周りが騒ぎ過ぎだと思います．
-
今までつや姫しか食べてこなかったのですが、一昨日あきたこまちを食べ、山形びいきから秋田びいきになりました。
---
あきたこまちがそんなに良かったのですね ;-)
-
Amazon
---
仮面ライダーでしょうか．
-
岡本先生には作業用BGMの好みはありますか？
---
特にありませんが，おそらくラテンジャズかバロックが好きだと思います．
-
この紙に「ラッスンゴレライ」とだけ書かれていたら，先生はどのように対応しますか？次から選んで下さい．
(1) 怒って紙を捨てる．
(2) ノリツッコミをする．
(3) 無視する．
(4) 説明する．
(5) イヤチョトマテチョトマテ，オニイサーン
(6) その他 ( )
---
説明しろと言われても意味分からんからできませーん
-
ギリシャ文字のχとかκとか書きにくいです．
---
ギリシャ文字も書き取り練習をするとよいと思います．練習しているうちにコツがつかめてきます．
-
目覚まし時計が鳴る時間より早く目が覚めてしまうのは幸か不幸か
---
眠りが浅いのかもしれませんね．
-
実験課題がたまってきて大変です。
---
たまらないように計画を立てることが重要ですね．
-
前回の中間試験で時計を忘れてあせった。
---
あせっただけで済んでよかったです．
-
中間テストにIDを書き忘れました。
---
それは残念です (-_-;
-
中間試験の結果はいつ頃公開されますか？
---
未定です．すみませんが，まだ採点を始めてすらいません．
-
中間テストの結果はいつ頃見れるのでしょうか．
---
未定です．すみませんが，まだ採点を始めてすらいません．
-
試験で悲しいミスをしてしまったため，これからはより一層注意深くありたいと思いました．
---
よい心がけだと思います．励行して下さい．
-
試験前の週末に一気に勉強するときつかった。日頃からの復習が大切だと思った。
---
日頃から復習をするようにして下さい．
-
直しや問題が返ってくる提出日のラストはいつですか？
---
現在調整中です．
-
期末試験の範囲を教えてください。
---
近づいたらご連絡します．
-
試験の結果が気になります！！期末の範囲は8回〜ですか？
---
近づいたらご連絡します．
-
期末試験もがんばりたいと思います
---
はい，しっかりと準備をして下さい．
-
テスト失敗しましたが期末で頑張ります
---
しっかりと準備をしてきてください．
-
問題9.6の2はsからtへ至る道を考えるのですか？
---
はい，その通りです．
-
「彩」色と「染色」が混じっていて混乱します．
---
私も混乱します (-_-;
-
直感的に捉えると、クリークと完全グラフは同じ…と思いきやクリークが示すのは頂点のみなんですね。
---
その通りですね．完全部分グラフの頂点集合がクリークです．
-
彩色の概念は今回から導入されたものですが、使われる性質などは既出のものと深い関わりがあると感じました。復習をしながら確認します。
---
そうですね．今まで取り扱ってきたいろいろな概念が組み合わされて行きますので，しっかりと復習をして下さい．
-
彩色問題の下界を示すクリークという概念には驚きました．
---
「下界を示す」や「上界を示す」ということは最適化においてとても重要な考え方です．演習問題を通して慣れて下さい．
-
弱双対性は本当にいろんなところで出てきますね。
---
はい，双対性を理解することがこの講義の目的の一つです．しっかりと身に付けて下さい．
-
🌰ーク
---
それはビックリしました．(^^;
-
クリークって聞くとどうしても思い出す
そのせいで先生の服が迷彩に見えた
---
何を思い出すのですか？ ;-)
-
クリークを見つけるコツはありますか．
---
気合です ;-) 案外難しいです．
-
部分集合と部集合って字面が似ているので間違えそうです．
---
確かに紛らわしいですね．気を付けて下さい．
-
どんな地図も4色あれば国境をまたいで同じ色が隣接せずに塗りつぶせるみたいなことを聞いたことがありますがこれも彩色のひとつですかね？
---
彩色のひとつです．第13回で登場する予定です．
-
次回は四色定理が登場しそうです。
---
登場しそうですが，次回は登場しません (^^;
-
四色問題を言い換えると「すべての無向グラフは4彩色である」ですかね？
---
言い換えてもそうはならないのですが，それについては第13回の講義で扱います．
-
四色問題を思い出す講義でした．
---
はい，第13回の講義をお楽しみに．
- 6/5 (9) 連結性：数理とモデル化
- コメントありがとうございました．
-
中間テスト頑張ります．
---
テストではなく試験です．
-
中間テスト頑張りたいです。
---
テストではなく試験です．
-
テストがんばりたいです。
---
テストではなく試験です．
-
テストがんばります。
---
テストではなく試験です．
-
中間試験がんばります！
---
はい，しっかりと準備をしてきてください．
-
中間試験がんばります！
---
はい，しっかりと準備をしてきてください．
-
中間試験頑張ります。
---
はい，しっかりと準備をしてきて下さい．
-
中間試験頑張ります．
---
はい，しっかりと準備をしてきて下さい．
-
中間試験をまず頑張りたいと思います．
---
はい，まずしっかりと準備をしてきて下さい．
-
中間満点狙います！
---
どうぞどうぞ．
-
多少演習レポートが追いついていませんが中間がんばります
---
はい，しっかりと準備をしてきてください．
-
試験ではよくわかっていただけるよう努力します。
---
はい，よろしくお願いします．
-
来週の日曜日がいそがしいので中間の勉強ははやめにしようと思います。
---
「中間の勉強はやめにしようと思います」と読み間違えて，一瞬混乱しました．;-)
-
テストの解答に誤字があった時、それは減点対象になりますか？
---
場合によるので，一概には言えません．
-
週末に試験勉強をしました．辛抱強くスライドを読んだら、徐々に分かってきました．
---
それはよかったです．:-)
-
中間試験では，演習問題から2題出ますが，復習問題から出る可能性もあるということですか？
---
復習問題から出る可能性もあります．
-
今までの問題で前解けなかったものが復習できないのですがどうすればいいでしょうか？
---
直接聞いて下さい．
-
今更ですが非負重みの数値のおき方が分かりません．どうやって設定しているのでしょうか？
例 
←こういうやつ
---
今更でもかわないのですが，聞かれている内容が何なのかが分かりません．直接聞いて下さい．
-
早く感じる口調だけど，わかりやすい。
---
不思議ですね．:-)
-
6月なのに部屋の湿度が10〜20％くらいでした。不思議！
---
不思議ですね．
-
辺でグラフを分離するより点で分離した方がすぐに (？選ぶ数が少なく？) 分離されるのは、点を除くと辺も除かれることになるためですか？
---
演習問題9.6の内容ですので，演習問題として解いて下さい．
-
ムカデ人間の点連結度は1ということがわかりました！
---
そうですね．辺連結度も1なので，確かめて下さい．
-
これまでにやった性質が先でも使えておもしろいと思いました．
---
そうですね．最大流の話は一旦終わります．中間試験を挟んで，次の講義は別の話題になります．
-
数学の解答は作るものでしょうか，見つけるものでしょうか．(検索などをするといった意味ではありません．)
---
表現に関する質問だと捉えますが，私の感覚で言うと，英語ではcome upするものだと思います．
-
ペトリネットの勉強を始めました
---
どうぞどうぞ．ペトリネットはグラフとして表現することが多いので，この講義とも大いに関係がありますね．
-
インターンシップ申し込みました．いい経験になればと思います．
---
そうですね．いい経験をしてください．
-
キングオブコメディの今野に似ていると言われたことはありませんか？
---
よくあります．
-
先生は好きなアイドルなどいらっしゃいますか？ (2次元，3次元問わず)
---
最近は欅坂46のパフォーマンスに注目しています．とりたてて，好きなわけではないと思いますが．
- 5/29 (8) 最大流：モデル化 (2)
- コメントありがとうございました．
-
トランプは紙製に限りますね．バイスクルのような高級品に慣れると二度と戻れなくなります。
---
そうですね．ただ，最近は「ご当地トランプ」もたくさんあり，(自分への) お土産として買っておいたりもします．豆知識が書いてあったりして面白いです．
-
中間試験を頑張ります！！
---
はい，しっかり準備をしてきてください．
-
テスト頑張ります
---
はい，しっかり準備をしてきてください．
-
中間がんばります．
---
はい，しっかり準備をしてきてください．
-
中間がとっても不安です．
---
しっかり準備をしてきてください．
-
1日24時間は足りない気がするもっとほしい
---
30秒を1分だと思って生活すれば，1日が48時間になります．お試しください．
-
少しはやくてついていくのが大変でした
---
そうですね．はじめの復習の部分だけで30分使ってしまっているので，その部分を短くまとめることにして，後ろの説明に余裕を持たせられるようにできればよかったです．
-
段々と証明が複雑になってきているように感じます。
---
いままで使ってきた道具をいろいろな形で使っていますからね．しっかりと復習をして下さい．
-
だんだん証明が複雑でむずかしくなってきました．
---
いままで使ってきた道具をいろいろな形で使っていますからね．しっかりと復習をして下さい．
-
今まで学んだものが道具として全部でてきて、脳の忘却を感じます．
---
はい，覚える必要はないので，しっかりと復習をして，忘れたときに，うまく思い出せるようにまとめておいて下さい．
-
マッチング系の最大流のグラフ書くときは線の数が増えすぎて見えにくいゾ．
---
見やすくなるように工夫をして下さい．;-)
-
グラフがごちゃごちゃになってしまいました...
---
見やすくなるように工夫をして下さい．;-)
-
最大流を答えるときに流れが0である孤は書いた方が良いですか？
---
どちらでもよいです．
-
次回出したレポートはいつ帰ってきますか？
---
6月19日に帰ってきます．
-
いつも細かくてんさくしていただいてありがとうございます！
---
残念ながら，添削はしていません．書かれているものを読んで，私が理解できるかどうかをチェックしているだけです．(^^;
-
一度間違えた問題はなかなかときなおしても答えにたどりつけないです。
---
粘り強く取り組んで下さい (^^)
-
印刷用スライドって白黒印刷すると色変えして強調してる線が他の線とまったく同じに見えて死亡．太さ変えて ♥
---
よく見ると，重要な部分はほとんど太さも変えています．見えにくい場合は自分で色を付けて下さい．よろしくお願いします．
-
今回扱ったトランプマジックを一般化させたものが追加問題8.4ですか？
---
一般化ではありませんが，確かにトランプマジックと関係があります．よい着眼点だと思います．:-)
-
先生がおすすめするグラフ理論の本はなんですか？もしあれば教えていただきたいです。
---
和書に限定します．この講義の参考書は初回に示したとおりです．そこでも紹介していますが，グラフ理論の入門書としては，ウィルソンの『グラフ理論入門』をお薦めします．現代的なグラフ理論を学ぶためには，ディーステルの『グラフ理論』をお薦めします．ただし，この本はかなり難しいです．
-
J8実験での無向二部グラフの最大マッチングを見つけるときに用いたアルゴリズムに対する理解が深まって良かったです。
---
理解が深まったと聞けて良かったです。
-
色々な問題を最大流に帰着できるのが面白いと思いました．
---
そうですね．いろいろな問題に使える，ということが道具としては重要ですね．
-
Hallの結婚定理っていう名前が独特で面白いと思いました
---
確かに独特ですね．考えている状況をうまく表現しているとも思います．
-
握手補題とか結婚定理とか用語が可愛いですね。
---
かわいいんですね (^^;
-
Hallの結婚定理は二部グラフ以外には適用できませんか？
---
二部グラフではないグラフに対してはTutteの定理 (タットの定理)と呼ばれるものが知られています．ある意味で，Hallの結婚定理の一般化になっています．
-
最小頂点被覆や最小s,tカットが必ずしも一通りに定まらない所に奥深さを感じました。
---
そうですね．重要な視点ですので，十分味わって下さい．
-
実際の問題がモデル化されて解決するのがとてもおもしろく、ピースがはまった感じがしました。
---
そのような例がまだこの講義では出てきますので，お楽しみに．
-
前で話していると暑くかんじるものなのでしょうか
---
感じます．90分の講義をするというのは，割と肉体労働です．
-
梅雨が近づいてきたのでせんたくものが心配です。
---
私は乾燥機を使っているので，まったく心配ありません．;-)
-
リチャード・ワーマンの『理解の秘密』の1章と2章を読んでみました．ぞっとしました．
---
ありがとうございます．では，続けて読み進めて下さい．
- 5/22 (7) 最大流：モデル化 (1)
- コメントありがとうございました．
-
飲み物 大切ですね。
---
そうですね．
-
お茶を取ってくるくらい大丈夫ですよ ^^
---
ありがとうございます．(^^)
-
ここ数日で突然暑くなりすぎだと思います．岡本先生も無理せず途中で飲み物を買ってきて良いと思います。
---
確かに暑くなってますね．体調管理には気をつけて下さい．
-
最近急に暑くなりましたね．
---
すぐに梅雨の季節がくるでしょう．
-
暑い日でバテます
---
冷房に頼り過ぎないようにするのも大切ですね ;-)
-
土日も含めて2時間しかねむれません。どうすれば眠れますか
---
そのために昼間に眠気が襲ってきて，昼間に寝てしまったりしてますか？ 昼間に寝ると夜に寝れなくなるので，昼間は何とかもちこたえるというのが大事かもしれませんね．
-
紙はまずい でもなにかかんでるとおちつく．
---
変なカミングアウトですね．(^^;
-
そばおいしい
---
調布には「深大寺そば」という名物がありますので，ぜひ食べに行って下さい．
-
提出期限切れの問題を先生が見る保証はないということは、誰かしらは見てくれるということですか？
---
誰かしらが見るという保証もありません．あしからず．
-
グラフGが「完全」グラフであることを見落としていました…。
---
細かい条件には必然性があります．見落とさないように気を付けて下さい．
-
すごく難しいです。
---
難しいですよね．わからないところを明確にして，是非質問して下さい．
-
我々はオアシスに辿りつけるのでしょうか．
---
最大流問題としてモデル化して下さい (^^;
-
フローたのしい
---
次回と次々回も最大流の話になります．お楽しみに．
-
割当問題は実験のJ8でやった二部グラフの最大マッチングを求める問題をより一般化したものの感じがします．
---
その通りですね．二部グラフの最大マッチングについては次回扱います．
-
実験のJ8課題を思い出しました。
---
よい連想だと思います．二部グラフの最大マッチングについては次回扱います．
-
最大流を最大マッチングに転換 (もしくは逆) することは可能ですか？
---
「転換」ということばの意味にもよりますが，転換することは難しいと考えられています．一方，二部グラフの場合は次回説明する通り，最大マッチング問題を最大流問題に転換できます．
-
最近の授業の内容をJ8課題よりも前に知りたかったと思った。
---
J8課題はこの授業がなくても理解ができるように構成しています．もちろん授業と組にすると理解が深まりますが，J8課題が先にあったから，この講義の理解が進んでいるという一面もあると思うので，どちらが先になるのがよいのかは一概に言えなさそうですね．
-
具体的な題材が入ると分かりやすいのだと思いました
---
そうですね．モデル化はこの講義の重要な側面なので，数学的な技法や概念だけではなく，それがどのように使えるのか，という視点もしっかりと学んで下さい．
-
最大流，最小カットを見つけるためには増加道法を実行しないと駄目なのですか？
---
実行しなくてもよいです．重要な点は，自分の主張する流れとs,tカットが本当に最大流と最小s,tカットであることを証明することです．なお「増加道法を実行して得られたから最大流である」という言い方は証明として成り立っていないことに注意して下vさい．それが証明になるためには，実際に増加道法を実行している様子を示す必要があります．それをしてもらってもよいですが，非常に手間がかかるので，やめた方がよいです．
-
容量を整数と条件をつけて増加道法の停止性を証明していましたが，この方法で小数のであるときも証明できますか？
---
よい視点です．「小数」が「有理数」を意味しているなら，同じ方法でできます．うまくいかないのは無理数が絡んでくる場合です．
-
第6回の増加道法の例 (pp. 48-63) において下図のようなグラフも見つけましたが、最大流となるとなる流れは複数存在し得るのでしょうか。
---
はい，これも最大流です．最大流となる流れは複数存在する場合があります．
-
最大流はすごく万能ですね！
---
万能，というわけではないですが，いろいろな問題をモデル化することができます．特に，今回扱ったように「割り当てる」という考え方ができる場合に有効である場合が多いです．もう一つはs,tカットを見つけるように「分割する」という考え方を必要とする場合です．最大流最小カット定理より，s,tカットを見つけることと流れを見つけることは関係があるので，分割を見つけるために流れを考えるということもよくあります．その典型例は画像処理・画像理解の分野でよく現れて，「グラフカット法」として，今となってはよく知られています．
-
先週あたりに「ロッテの自力優勝が消えた」みたいなニュース見ましたが この「自力優勝」というのは最大流を考えなくても可能性がわかったりするんでしょうか
---
「自力優勝が消える」というのは，「残り試合を全勝しても優勝できない場合がある」という意味なので，今回の優勝可能性判定とは考えている状況が違います．今回の優勝可能性判定は「残り試合を全勝したとしても，絶対に優勝できない」ということです．自力優勝の可能性は，最大流を考えなくてもわかります．
-
グラフにfとcを表すととても見栄えが悪く 書きにくくなってしまうのですが 上手く書くコツなどはありますか？
---
これは難しい問題ですね．私も上手く描く方法を知りたいです．
-
モデル化をして，そのモデルで正しく議論できるということを，しっかり説明するのは大変そうに感じました
---
そうですね．そのためにしっかりと論理的な文章を書く能力を養って下さい．
-
強化学習したくなって少し勉強し始めました。
---
機械学習で使われる主な技術の1つは最適化ですので，しっかりと最適化を勉強することが重要だと思っていて下さい．:-)
-
「賢明な読者はお気付きだろうが」と書くのは、気づいていない時に悲しい思いをするだけなのでやめて欲しいなと思いました。
---
同意します．(^^;
-
自然数は0を含みますか？
---
分野によって含むか含まないか，変わります．数論のような数学の分野では，0を含まないことが多いです．一方，数学基礎論や論理学，また，それらに近いコンピュータサイエンスでは0を含むことが多いです．
-
大阪の友人が先生の名前を知ってておどろきました．
---
私も驚きました ;-)
-
学生時代に気に入っていた本を教えて下さい．
---
私がちょうど大学3年生のときに読んで，気に入り，このような機会がある度にお薦めしているのは，リチャード・ワーマンの『理解の秘密』です．私の人生を変えたとも思ってます．今となっては内容が古くなっていますが，私に大きな影響を与えたことは間違いありません．
- 5/15 (6) 最大流：数理
- コメントありがとうございました．
-
出しそびれたレポートを後日出すのは可能でしょうか？
---
可能ですが，そのレポートを私が見る保証はありません．あしからずご了承ください．
-
第5回のスリザー問題に関連してなのですが、先手の証明はしても後手の証明をしなければ引き分けの可能性が残るため先手必勝とは言えないのではないでしょうか
---
ご指摘通りです．実際，このゲームは引き分けで終わることがないので，先手が常に着手できるならば，先手必勝であるわけで，その考え方に従って，先手必勝であることを証明しています．
-
6.5の証明をしていましたが、握手補題の証明のように、行列を定義し、それに対する特定の列、行でのΣをとることで示せそうでした。
---
よい方針だと思います．その流れで進めて下さい．
-
試験はA4の手書きのメモが持ち込み可ですよね？
---
はい，その通りです．
-
GWまで360日を切りました！わくわくします
---
そうですね！
-
GWが終わってレポートの提出は中間テストが始まってきたので頑張っていきたいと思います。
---
はい，よろしくお願いします．
-
日本語がおかしい証明を書いてしまっていたので気をつけたい
---
意識をしながら日本語を使う，という習慣を身に付けるとよいと思います．日本語だから無意識に何かを書いたり話したりしても，通じていると思うのはよくありません．
-
ちょっと字が汚くなってしまったので丁寧に書くよう気を付けます。
---
はい，よろしくお願いします．
-
「各頂点」と「任意の頂点」という表現の意味上の違いはありますか？ 「持つ」と「含む」についても，違いはありますか？
---
どちらについても，違いはないと思って下さい．
-
海外のサイトで
{ 〜：∀〜：∃〜：〜 }
という表記を見ましたが，
{ 〜 | 〜 }
と同等ですか？
---
具体的に見てみないと何ともいえません．上の「〜」と下の「〜」がどのような関係なのか，というところが重要かもしれません．
-
証明は難しいです
---
慣れて下さい．
-
最近説明が速い。
---
ここまでにやってきていることは前提にしていますので，しっかりと復習をして下さい．
-
どんどん複雑化してると思いました。
---
ここまでにやってきていることは前提にしていますので，しっかりと復習をして下さい．
-
フロー、ついに出てきましたか…
---
お待たせいたしました．(^-^)
-
まだ全然わかっていませんが，流れの定義がとても考えられている気がしていて，エレガントに感じています．
---
ぜひ分かって下さい (^^)．「流れ」という直感を数学の概念を使って表しているわけで，これもある意味で数理モデルと言えると思います．
-
モノクロいんさつだと増加道がらみがわかりにくくなりますね．
---
増加道を太くしているはずですので，それで判別して下さい．
-
上手くs,tカットを行なえばダイヤモンドカットになりますか？
---
なりません (-_-;
-
最大流の下界が上手に証明できないです。
---
どうやって流せそうか，考えてみて下さい．
-
最大流最小カット定理において、「fが最大流、Sが最小s,tカット $\Leftarrow$ val(f) = cap(S)」は成り立たないのでしょうか？
---
成り立ちます．弱双対性 (と最大流，最小s,tカットの定義) を使えば証明できます．
-
val(f) = cap(S) のとき，fが最大流であるだけでなく，Sが最小s,tカットであるというのが面白かったです．
---
そうですね．双対性の偉大さが分かります．
-
弱双対性について理解が深まりました。
---
よく使う考え方なので，しっかりと身に付けて下さい．
-
無向グラフでの最大マッチングと最小頂点被覆が有向グラフでの最大流と最小s,tカットに対応している、という解説が分かりやすかったです。一見して異なる分野の話題も数学的な定義や抽象化によって統一的に扱えるところに自然科学のおもしろさがあると改めて感じました。
---
私もそう思います．そういうものが「ものの見方」であり，科学がいろいろなところで重要な役割を果たしている理由でもあると思います．例えば，物質は世界中に果てしない種類のものが存在するのに，それらが元素に分解できて，さらに元素どうしには周期律という法則が現れるというのは，物質に対する見方をとても整理できていると感じます．不思議です．
-
広島カープのF水流選手がずっと頭からなぜか離れなかった
---
私はm-floが頭から離れなくなることがあります．
-
増加道アルゴリズムは、二部グラフの最大マッチングを求めるプログラムを作成する際に実装した。工夫して、今回の最大流を求めるプログラムも作ってみたいと思った。また、他に増加道アルゴリズムを使う身近な例などがあれば知りたいと思った。
---
似た考え方を使うことはよくあります．増加道アルゴリズムの重要なところは，例えばマッチングの場合，「一旦選んだ辺を選ばなかったことにする」ということをうまく行い，最大流の場合，「一旦流したものを流さなかったことにする」ということをうまく行うことです．そうではなく，一旦選んだものを選ばなかったことにはしない，とすると，いろいろと破綻する場合もあります．柔軟性を持たせていることが増加道アルゴリズムの成功の秘訣なのだと思います．
-
気温が安定しないので、体調があまり良くありません
---
お大事に．
-
カゼひきました。鼻とのどがつらいです。
---
お大事に．
-
日中のパフォーマンスを維持しつつ睡眠時間を削る秘訣はありますか？
---
「日中」を「日本と中国」のことかと錯覚し，何を聞かれているのか一瞬分かりませんでした．;-) よく眠ることをお薦めします．「寝なくても大丈夫」という言い方をあまり信用していません．
-
また分からないことがあったら，聞きに行きます．よろしくお願いします．
---
質問することは大事です．よろしくお願いします．
-
講義資料のグラフはどんなツールを用いて描画していますか．
---
ipeを使っています．
-
電車が遅れたとき，人の手でダイヤを直している様子をテレビで見ました。このような問題は人よりもコンピュータの方がうまくやれそうですが，なんで人の手でやっているのでしょうね。
---
情報数理工学セミナーに是非お越し下さい．
- 5/8 (5) マッチング：モデル化
- コメントありがとうございました．
-
先生はどんなテレビゲームをやりますか？
---
「テレビゲーム」はしません．
-
先生はRubyとPython 3どっちが好きなんですか？！
---
好き嫌いはないです．用途に応じて使い分けます．
-
知恵袋で説教している回答者の多くが大学関係者と聞きましたが、本当でしょうか？
---
すみませんが，知りません．知恵袋で聞いてみるのはいかがでしょうか．
-
前々々回の語呂が好きです．
---
では，今後も使っていきます ;-)
-
最大重みマッチングが最適化につながるなんて驚きました。
---
最適化そのものです．味わって下さい．
-
今日授業はより実世界に役立つ内容だった。
---
このようにモデル化が行われる，という感覚を掴んで下さい．
-
モデル化とは、どこまでがモデル化なのか．
---
今回の場合は，「グラフと辺の重みを作り，その上で最小重み完全マッチングを見つければよい」と述べるところまでがモデル化です．その後はアルゴリズムの話になります．
-
非負重みの値はどのように設定すればいいですか。
---
除雪車の運行計画に関する話を指しているのだと思いますが，2つの頂点間の最短経路長をその2頂点を結ぶ辺の重みとします．
-
実験で演習をやる時間が減ってきてツライです
---
すいません，ちょっと言ってるコトの意味が分からないです．
-
つい印刷を忘れて悲しい気持ちになりながらスマホでスライドと演習問題を見るはめになるので、忘れないようにしたいです．
---
はい，しっかりと準備してきてください．
-
少しはやいところがありました
---
すみません．今回は何度も言い直していた気がします．
-
この部屋は涼しく感じるので快適です．なぜでしょう
---
なぞなぞですか？ ;-)
-
スリザーの格子点ゲームおもしろいですね．今度の盆休みで従兄妹と遊んでみたいと思います。
---
ぜひぜひ (^-^) 楽しんで下さい．
-
友情破壊ゲーム，スリザー…。
---
たまに先手と後手を交代すればよいです．
-
最小重みスリザーとか面白そうですね。
---
どういうゲームになりますか？
-
この授業とMI・CS実験の中でふと思ったんですが，二部グラフの最長一筆書きは多項式時間で解けますか？
---
これは未解決問題です．
-
演習問題が難しくなってきたと感じています
---
いままで扱ってきたことをどれも使いますので，しっかりと復習をして下さい．
-
難しいです
---
はい，難しいかもしれませんが，これぐらいのレベルが大学生のレベルです．しっかりと復習をして下さい．
-
オイラー回路を持つための十分条件の証明で、|E|=1と|E|=2の時はオイラー回路が存在しないので、k≧3の時のみを考えるべきではないでしょうか．
---
それでは帰納法としてうまくいかないかもしれないので，まずいです．特に，|E|=0のときは必ず考える必要があります．
-
「次数が偶数⇒オイラー回路を持つ」の帰納法は偶数である前提から辺数は3以上になるのではないのですか。
---
上のコメントと同じなのですが，0も偶数なので，辺数が0の場合も考える必要があります．
-
何も書かない人もいるのですか？
---
たまに白紙があります．
-
GWが終わって夏休みが待ち遠しいです。
---
そうですね．
-
GWが気がついたら終わって悲しい
---
そうですね．
-
春の大型連休がおわってしまいました。次の祝日が海の日ということが残念でしかたありません。しかも午後は講義あるらしいので本当に残念です．
---
そうですね．
-
ゴールデンウィーク明け初日，快晴でなによりです．
---
そうですね．
-
ゴールデンウィーク遊んでたら追加問題できませんでした。反省します。
---
チクショー1週間，ですね．
-
半袖1枚で過ごしてもお腹を冷やして体調崩すこともない季節になりましたね
私はGW明けで睡眠リズムが乱れまくって今にも頭から崩れ落ちそうです
---
けがをしないように気をつけて下さい．
-
頑
張
っ
て
大
学
来
た
。
---
自由律俳句でしょうか．季語は「大学」？
-
大学に来る前に運動をしたいのですが、汗をかきたくありません。何かないでしょうか。
---
すみませんが，思い当たるものはありません．
-
GW明けで肉体的にも精神的にも滅茶苦茶怠いです．どうやって気持ちを切り換えていけばいいでしょうか．
---
GWに遊び過ぎないのがよいと思います．今更遅いかもしれませんが，来年から心がけて下さい．
-
BGMが良かったです．
---
では，次回もBGMを用意します．
- 5/1 (4) マッチング：数理
- コメントありがとうございました．次回はようやく「モデル化」を扱う回になります．ご期待下さい．
- まずはじめに訂正です．授業中に，最大マッチングは半順序集合の最大元だと (口が滑ったという割にはかなり大胆に) 言いましたが，これは大間違いです．すみません．単純に間違いです．ただし，極大マッチングは半順序集合の極大元です．それは正しいです．なぜか，勝手に混乱しました．ここで訂正します．
- では気を取り直して，皆様のコメントを掲載します．
-
講義のスピードが少し速いです．
---
半順序集合なんて言わなきゃよかったんです．すみません．
-
極大マッチングの定義は「GのマッチングM⊆Eで、任意のマッチングM'に対してM'⊃Mでないもの」と考えてもいいですか？
---
「M'⊃M」が「MがM'の真部分集合である」という意味ならば，そう考えても正しいです．
-
最大マッチング，最小頂点被覆についてですが，$|C| = |M|$ となる $C \subseteq V$, $M\subseteq E$ が見つかればそのときの $C$ は最小頂点被覆，かつ，$M$ は最大マッチングということになりますか？ (無向グラフ $G=(V,E)$ において．)
---
$C$ が頂点被覆であり，$M$ がマッチングであるなら，正しいです．
-
スライド22で上のような増加道もみつかりました．
---
そのとおりですね．他にもあるので，探してみて下さい．
-
対称差を使う証明がすごかったです。
---
演習問題の中にも対称差を使うことで考えやすくなるものがあるので，挑戦してみて下さい．
-
対称差 $\triangle$ というのが出てきましたが排他的論理和 $\oplus$ とは違うのでしょうか
---
対称差は集合に対する記号 (概念) で，排他的論理和は論理に対する記号 (概念) です．つまり，「2つの集合の排他的論理和」というものは存在しません．その意味では違います．一方で，集合 $X$ と $Y$ の対称差 $X \triangle Y$ を，排他的論理和によって，$X \triangle Y = \{ x \mid (x \in X) \oplus (x \in Y)\}$ と書くことはできます．この意味で，対称差と排他的論理和には関係があります．
-
マッチングとまいっちんぐは似ている…
---
エッチングも似ています．
-
シロウト・ベルジュに今日の授業は難しかったです。
---
クロートになる必要はないですが，シロウトの地位から脱却できるようにはなりたいですね．:-)
-
最大マッチングを見つけるのが難しい．
---
授業に出てきているぐらいの例ならば，じーっと見ていれば分かりますので，どのように見つけても構いません．重要なのは見つけたものが本当に最大マッチングであるのか確認できることです．
-
実験のJ8課題をやる前に知っておきたかった。
---
J8課題は講義がなくても理解できるように作っています．もちろん，講義と実験を組として考えると，互いの理解が深まりますので，それを踏まえて，実験のレポートをまとめるのもよいと思います．
-
よくあるお見合い番組とかのやつで、最大マッチング見つけてみたいです！ (お見合い対象としてアリなら辺を接続する形で．)
---
これは，応用としてよく考えられているものです．実際の応用はお見合い番組ではなく，医師のインターン先決定や臓器移植など，多岐に渡ります．
-
一瞬ウトウトしたら証明についていけなくなってしまったので、しっかり復習して演習に臨みたい。
---
はい，しっかりと復習をして下さい．
-
楽しくなってきました。
---
それはよかったです．次回もお楽しみに．
-
数え上げがなんとなく分かりました！
---
今後も使っていきますので，そのときにまた理解を確認して下さい．
-
証明は書くことが多すぎて疲れます。
---
何事に対しても「文章を書く」ということが求められているのだと思って下さい．
-
自分の証明は説明不足なものが多かった
---
どんな文章においても，文と文，段落と段落，など，いろいろな部分が論理的につながっていなければなりません．日頃書いている文章でも，そのような点に注意して下さい．
-
証明の正当性を自分で確認しきれないのが歯がゆいです。
---
重要なポイントだと思います．証明というのは，何かが正しいことを他者に説くための文章です．自分で確認しきれていないということは，その文章で他の人を説得することは難しい，ということだと思います．
-
なかなか追加問題に手を付けられないのでコツコツやっていきたいです。
---
そうですね．時間をしっかり確保して，いろいろと考えてみることが重要だと思います．
-
オススメな参考書ありますか？
---
初回の講義資料を見て下さい．書いてあります．
-
ムズかしくなってきマシタ…
---
よく分からない点は具体的に質問してもらえるとありがたいです．ぼんやりと「分からない」という気持ちをはじめは抱きがちですが，そこから「○○が分からない」と具体的な部分が取り出せるとよいです．
-
難しいのでがんばります
---
はい，演習問題を通して理解していって下さい．
-
大型連休は実家に帰ってレポートします。
---
実家に帰らない人も演習をやって下さい :-)
-
初めて自作PCを組んでたら それだけで土日がつぶれてしまったのでGWの間に遅れを取り戻したいです．
---
はい，よろしくお願いします．
-
提出した演習問題が解けてないのもつらいですが、漢字も直されたので、二重ダメージでした．
---
いま間違えてもよいのです．大事なときに間違えないことが重要です．
-
問3.10と3.11のヒントをもう少し下さい
---
その問題について，何を考えたのかをレポートで書いて下さい．それに合わせたヒントを私が考えます．「よく考えたけど分からなかった」と言われることも多いですが，その言い方では何を考えたのか分かりません．何を考えたのか具体的に述べることが重要です．
-
レポート上に「だいたいOK」と書いてあるんですが，それは試験の場合何％の点数がもらえるか？
---
場合によりますので，何とも言えませんが，満点ではないでしょう．
-
手書きで提出用のレポートを出そうとすると、あとで見返して、この文を追加しておけばよかったとなったときにふきだしみたいな感じでつけたしてもいいでしょうか？ もしくは、これからはパソコンのワードなどでレポートをつくった方がいいでしょうか？
---
個人的な意見ですが，手書きでレポートを書くことはやめた方がよいと思います．手書きでもよいですが，その場合は，必ず清書したものを提出してほしいと思います．私が講義においてレポートの形式を細かく指定することはないと思いますが，レポートには文章を書くのだ，という認識を皆さんには持ってほしいと思います．
-
数学に限らず，何か問題について考えていて，行き詰ってしまったときにはどうすれば良いでしょうか，どうしてますか
---
行き詰まりのレベルにもよると思いますが，重要なことは「他者を頼る」ことだと思います．
-
レポート忘れたからじゅぎょう中にやろうと思ってたら問題のプリントを忘れ、スマホでみようと思ったらスマホを忘れた あるいみすごい．
---
災難ですね．(^^;
-
1日8時間以上の睡眠がほしいです。
---
では，早く寝て下さい ;-)
-
早寝しなければならないと分かっていても夜更かしをしてしまうことがよくあります．これを防ぐ良い方法を知っていたら教えて下さい．
---
ゴルトベルク変奏曲を聴く，とかどうでしょうか．
-
ゴールデンウィークです！
---
ですね．
-
G.Wですね
---
渡部豪太ではありません．
-
5月病が治りました！
---
まだ5月は続きますので，用心して下さい ;-)
-
GW中はどこかに出かけましたか？
---
問いが過去形なのですね (-_-; 遠くに出かける予定はないです．
-
ゴールデンウィークって電通大に無縁だと思いますが先生はどのようにお考えですか？
---
なぜ無縁なのかが，分かりません．
-
「これを研究したい！」という明確な目的が無く、かといって、何にも興味がないというわけではないので、秋の研究室選択が不安です。具体的には、今回の講義で扱ったような離散的なアルゴリズムも興味深いと思いましたが、微分方程式の数値シミュレーションについても、おもしろそうだと思っています。
---
別に明確な目的がなくてもよいと思います．やっているうちに面白さが分かってくるものだと思うので．その面白さを分かりたいと自分が思っているかどうかも大事なポイントだと思います．
-
「自己評価」と「他者からの評価」は時に大きく異なる場合がある。そんなときがありませんか。
---
あると思います．
- 4/24 (3) 木：数理
- コメントありがとうございました．
-
お腹が痛いです
---
お大事に．
-
今朝ものすごい腹痛でした
---
お大事に．
-
かぜっぽく、体調があまり良くありません．
---
お大事に．
-
自転車を東においたと思ったら西においていて，東西間を往復してしまいました。いい運動です。
---
おめでとうございます．
-
バグ埋め癖が治りません。何を気を付けたら治りますか。
---
日本語を注意深く使うように心がけるとよいと思います．ことばというのは，文法的に正しければ伝わるというものではありません．伝えるために，どのような単語を用いるのか，どのような順で文を構成するのか，その他にもいろいろなことに気をつける必要があります．英語が上達しないと嘆く人がよくいますが，そのような人はおそらく日本語もうまくないのだと思います．うまく日本語が使えるように心がけて下さい．
-
証明で自分の言いたいことが言葉でうまく表現できません。
---
証明によって表現するということの訓練をしていると思って下さい．証明というのはコミュニケーションなので，自分の考えが伝わるようにしなければなりません．
-
自分に考察力がないと強く感じます．訓練する方法で何かおすすめのものはありますか．
---
何を指して考察力と呼んでいるのか私が誤解しているかもしれませんが，基本は読書をすることだと思います．そのときに，論理的に読む，ということと，批判的に読む，ということに注意して，論理的思考と批判的思考を身に付けられるように気をつけるとよいと思います．
-
用語としての「森」や「林」を英語で言う時は両方共に「forest」でいいんですか？
---
いいんです．第3回講義の用語集をご覧ください．
-
森さんや林さんはいるのに木さんっていませんよね
---
名字由来netによると，木さんも40名ほど，主に新潟にいらっしゃるようです．
-
---
はい，それは木です．:-)
-
これからは木1本でも森と呼ぶことにします。
---
木を見て森も見て下さい．
-
木は森であるって、なんだか大自然の摂理を感じます。
---
一方，木が集まると森になります．よくできています．;-)
-
この木 何の木 気になる木ー♪
---
おみそならハナマルキです．
-
演習のとき空調が寒くなった気がするのですが気のせいでしょうか
---
木のせいです．嘘です．換気をしました．
-
葉を持つことの証明で
- Pが長さ最大 ⇒ 隣接頂点はP上で閉路を含む ⇒ 閉路を含まないことに矛盾
- Pが閉路を持たない ⇒ 隣接頂点はPの外 ⇒ Pが長さ最大であることに矛盾
これはどちらでも正しいでしょうか。
---
はい，どちらも正しいです．
-
木の辺は全て切断辺であることの証明は、木が閉路を持たないことを軸に証明するのは難しいでしょうか。
---
できると思います．ぜひ試していただいて，レポートとして提出して下さい．
-
3.6について、切断辺の証明と同様に方針で解こうとしましたが、時間が足りませんでした…
---
少し注意が必要な部分もあるので，落ち着いて考えて下さい．
-
「最大性論法」とは先生が名付けたのですか？ 本やインターネットではどのように例を探すと良いでしょうか？
---
私が名付けた，といってもよいかもしれません．英語で「Proof by extremality」や「Extremality proof」と呼ばれるものを指していて，直訳すれば「極大性(極小性)による証明」となりますが，極大性や極小性のはなしをしようとすると，「極大」や「極小」という用語を定義する (あるいは，離散数学の半順序のところの復習として確認する) 必要があります．それを嫌ったので，最大性や最小性という分かりやすいものを使って証明を書き換えています．ちなみに，背理法は「Proof by contradiction」で，直訳すれば「矛盾による証明」となります．
-
2回目の演習で，最大性論法の便利さを実感しました。
---
はい，とても便利ですので，使えるようになって下さい．
-
最大性論法とは最大値が存在する場合、それを仮定して考えていくことにより、仮定よりも大きくなることはないことを利用するという認識であってますか？
---
はい，だいたいあっています．仮定して考えていく，というよりは，それが存在するので，存在するものを用いて証明する，ということです．「それを仮定して」としてしまうと，仮定が成り立たないときには証明できていないことになってしまいます．
-
昔教わった数学の先生によく言われました。「わかるとできるは違う」と。
---
私もそう思います．できるようになって下さい．
-
スライド証明1の方法でも、存在することを証明することはできますか？
---
すみませんが，何が存在することの証明について質問されているのかわからないため，答えようがありません．
-
プリントのいんさつわすれたのでスマホみてたら右目がいたいです．左目はなぜいたくないのでしょう．
---
私は医師ではないのでわかりません．
-
帰納法について詳しく知ることができました。間違った方法を使わないようにしていきたいです。
---
間違えやすいので気をつけるようにして下さい．
-
帰納法を用いるときに，細かいところを意識していなかったので以後注意したい。
---
数学的帰納法を正しく使えるようになることは非常に重要なので，しっかりと身に付けて下さい．
-
だんだんと証明の考え方が理解できるようになってきました。
---
それはよかったです．演習問題を通して理解を深めて下さい．
-
それぞれの証明法を知り、なんとなくどの方法を使えば良いか分かった気がします。
---
離散数学特有の証明法がいくつかあるので，ぜひ使えるようになって下さい．
-
レポートを持ってこないときに、次回に出してもいいですか？
---
いいですが，私が見るとは限りませんので，ご注意ください．
-
私は前回のレポートの発展問題について真に驚くべき証明を発見したが、レポートを忘れてきました。(´・＿・`)
---
それは (いろんな意味で) 残念です．(-_-;
-
2.9のとっかかりすらつかめませんでした．
---
発展問題なので，解けなくてもよいです．:-)
-
補題まではなんとかできるのですが、追加までいくと証明がサッパリです．「問○.○の証明方針がわからない」とだけ書いて出してもOKでしょうか．
---
出してもOKですが，あまりよいフィードバックは得られないと思って下さい．どこまでどのように考えたのかを書いてもらえるとありがたいです．
-
だんだん難しくなってきました。
---
直接質問をして下さい．演習の時間中，私は暇を持て余しています．活用して下さい．
-
ちょっと難しくなってきました…。
---
直接質問をして下さい．演習の時間中，私は暇を持て余しています．活用して下さい．
-
追加かだい難しいです。
---
直接質問をして下さい．演習の時間中，私は暇を持て余しています．活用して下さい．
-
証明問題が苦手で全く手がつかない問題が多いです。何をどう証明すればよいかを理解するコツってありますか？
---
定義に立ち戻ることです．これが証明の基本です．私の意見を述べますが，皆さんが証明問題であると思っているものは，皆さんが計算問題だと思っているものよりも簡単です．なぜならば，皆さんが証明問題であると思っているものは，定義だけ理解していればよいからです．一方，皆さんが計算問題だと思っているものは計算法 (つまりアルゴリズム) も理解する必要があります．重要なものは定義であり，計算法ではないと思っています．場合によっては，定義がわからないのに計算ができる，という事態が引き起こされているかもしれませんが，それは結局何を計算しているのか理解していないわけですから，よくありません．
-
中間の時，問題の解答は答えだけで評価しますか？それとも，その過程も評価します？
---
すみませんが，「答え」と呼ばれるものが何を指すのかわからないので，答えようがありません．
別の回答を試みてみます．演習問題に取り組んでいただければ，受講生に何が求められているのか分かると思います．取り組んで下さい．
-
毎週，提出された課題全てを添削するのは非常に大変だと思いますが，とても有難いです。
---
はい，そのようなシステムにしているので積極的に活用して下さい．皆さんにとって，大学は資源です．資源を有効に活用することが重要です．
-
最近暖かくなってきたので服装選びに少々困ります。先生ももう少ししたらアロハの出番でしょうか。
---
アロハの出番まであと1か月半ぐらいはかかると思います ;-)
-
音楽良いと思います。
---
ありがとうございます．それでは，続けることにします．
-
演習中のBGMがとてもおしゃれで好きでした。何ていう曲ですか？
---
YouTubeにて「bgm」で検索して出てきたものを流してます．ということで，曲名は分かりません．
-
メイトからこの講義の情報を聞いて第2回から参加しようと思いました。が、先週教室をまちがえたため、参加できませんでした．今週からお世話になります。
---
こちらこそよろしくお願いします．
- 4/17 (2) 道と閉路：数理
- コメントありがとうございました．
- 質問から
-
演習問題は提出締切が4月24日とかの場合、4月24日の何時までに提出しなければならないとかありますか？
---
すみません，明示していませんでした．「講義終了時」，つまり，12:10頃を想定しています．よろしくお願いします．
-
レポートを再提出する際にその回でやっていなかった問題もだしていいですか？
---
私が見るかどうかはわかりませんが，出してもよいです．
-
前回の演習問題の1.7がわかりませんでした。与えられた数式に対して、，証明の方針が立たないとき，どのような手法を取れば良いのでしょうか．
---
まず，例を作ってみて，その式が何を意味しているのかしっかりと理解してみて下さい．証明の手法は限られています．無から有が生まれることはありません．勉強した手法が使えないか，考えてみて下さい．
-
追加問題1.7の証明の方針がわからないです！
---
いろいろな方法があるかもしれませんが，例えば，次のように考えてみて下さい．講義で行った証明では，行列の成分が0か1だったのですが，この問題では，そうではない行列を作って下さい．
-
2.2のような証明において「無向グラフにおける握手補題より〜」といった記述は可能ですか？
---
可能です．
-
Gからeを除去したグラフがG-eなら、辺e'を追加したグラフはG+e'と表しますか？
---
はい，そのように表すことが多いです．
-
完全グラフKnに対し，(Knが持つ辺の数) = n-1 + (Kn-1が持つ辺の数) は正しいですか？
---
正しいです．
-
情報基盤センターでの印刷用スライドの印刷がうまくいかなかったのですが学内だとどこで印刷するのがおすすめですか？ (演習問題は印刷できた)
---
おそらく，情報基盤センターのプリンタかプリンタドライバが古いのだと思います．私も同じように情報基盤センターでは印刷できません．例えば，CEDで印刷して下さい．
-
春になるにつれて花粉症がつらくなってまいりました。何か良い対策はないでしょうか。
---
個人的な話をすると，今年はあまり酷くなりませんでした．あまり対策をしたわけではないですけど，ヨーグルトを食べたり飲んだりするように心がけたのがよかったのかもしれません．
-
花粉の所為か異常に眠くて困ります．
---
では質問です。花は自分からミツバチを探しに行きますか？
-
寝不足でした
---
寝てきてください ;-)
-
喉がめっちゃ痛いです．良いのど飴を知っていたら教えて下さい．
---
良いのど飴かどうかは分かりませんが，はちみつきんかんのど飴をよく舐めます．
-
最近あったかい
---
そうですね．過ごしやすくなってきました．(^o^)
-
微妙な気温なのでコーヒーをホットにするかアイスにするか悩みます。
---
分かります ;-) アイスコーヒーを飲み過ぎて，体を冷やさないように注意して下さい．
-
毎年健康診断に合わせて雨が降るように感じるのですが、只の被害妄想でしょうか。
---
おそらく，ただの被害妄想です．(^^)
-
けんこうしんだんって何もってくるべきだったのか
---
しりません ;-)
-
何故か講義資料がDLできませんでした
---
リロードしてみて下さい．
-
kompliziertは，
< komplizieren [過分]
─ 形 [-est]
複雑な，錯綜した.
(クラウン独和辞典 第4版)
のようです．
---
ありがとうございます．すっきりしました．
-
kanzen 良いと思います
---
日本人には分かりやすいですよね ;-)
-
道はPathの英語からとるのに完全グラフKnはドイツ語からとるのですね．不思議
---
道はドイツ語でPfadと呼ぶこともあるので，それだと思ってもらってもよいです．数学の用語や記法にはドイツ語由来のものが割とあって，突然ドイツ語っぽい発音をする必要が出てくる場合もあります．有名なものに「ヒルベルトの零点定理」と訳されるものがあって，英語では「Hilbert's Nullstellensatz」と言い，「零点定理」の部分に対応する「Nullstellensatz」がドイツ語由来になっています．
-
グラフ内の一部の頂点にだけラベルが付いている、ということはありますか？
---
普通，そういうことはありません．
-
グラフの連結性が難しかったです。
--
定義をしっかりと理解することが重要ですね．
-
面白い分野だと思った。
---
それはよかったです．(^^)
-
グラフの切断点でG-hの例がありましたが，辺をsimcityの電線だと思うと停電になってしまい大変だなぁと考えてしまいました。
---
そうですね．そのような例を自分で考えることが大事だと思います．
-
例外が存在するように思えて理解しにくいというのがあり、困っています。たくさん触れるのが近道のような気がしています。
---
そうですね．多くの例を考えてみる，というのがよいと思います．自分でよい例が作れるというのは非常に重要な技術です．
-
示された証明を理解するのに少し時間がかかった。演習をして理解を深めたい。
---
はい，そのために演習問題がありますので，活用して下さい．
-
最大性論法難しいです。
---
はい，難しいので，演習問題を通して慣れていって下さい．
-
最大性論法の使い方がよくわからなかったです。
--
はい，難しいので，演習問題を通して使い方を身に付けていって下さい．
-
最大性理論の使い所が難しいです．
---
はい，難しいので，演習問題を通して使い方を身に付けていって下さい．
-
最大性論法がいまいちよくわからないです…
---
はい，難しいと思います．実際に問題を解いてみると，使い方がわかってくるので，演習を通して理解して下さい．
-
最大性論法は目からウロコでした。
---
離散数学独特の論法です．次回も出て来ます．
-
証明のアプローチを考えるのが難しい．
---
そうですね．ただ，証明の手法は限られているので，勉強した手法をどのように使えるのか，いろいろと考えてみて下さい．
-
少し難しくなってきたので放っておかずにきちんと理解したいと思います．
---
放っておかないのは重要ですね．分からない所は積極的に質問して下さい．
-
分かりやすいですが、少し考えていると置いていかれるのでもうすこしゆっくり説明してもらえるとうれしいです。
---
今回は時間が余りすぎたので，反省しています．もう少しゆっくり説明すればよかったですし，そうできたはずです．
-
早口だった
---
同上です．毎回気をつけているつもりなのですが，気をつけても直らないので
，毎回注意して下さい．
-
演習問題楽しいです。
---
楽しめるなら，何よりです．発展問題もありますので，チャレンジして下さい．
-
演習問題にもうちょっと難しい問題がほしい
---
たまに「発展問題」があります．挑戦してみて下さい．
-
解答がほしい〜
---
ありません．レポートとして提出して下さい．
-
2限はつらい
---
それは困ります ;-)
-
上級科目人多すぎて履修すらできませんでした かなしい
---
学修要覧によると，科目の履修というのは「その科目に対応する授業を受講し，試験に合格することによって，その科目の単位を得る」ことです．おそらく，皆さんは，履修申告のことを履修と呼んでしまっている気がします．
-
格言 もっと欲しいです。
---
あまり多すぎると，重みがなくなってしまうのです…
-
この時期は西も東も食堂が混雑してて大変です．
---
では，南にいってみましょう．
-
MIだけずるいな〜
---
MI以外のことを私に言われても困ります．;-)
-
本日、人生初の迷惑メールが届きました．某大手動画サイトからでした．
---
おめでとうございます (？)
-
自習時間に曲を流してほしいです
---
では，次回は音楽を流します♪
-
相談を推奨する理由が気になります。
---
相談せず，一人でやるなら，大学に来る意味がないからです．他の人と一緒に勉強ができる，というのが (通信制ではない) 大学のよいところですから，それを積極的に活かしてほしいのです．
- 4/10 (1) グラフの定義と次数：数理
- コメントありがとうございました．いただいたコメントとその回答は以下のように掲載されます．
- まずは，あいさつから
-
半年間よろしくお願いします。
---
こちらこそよろしくお願いします．
-
よろしくお願いします。
---
こちらこそよろしくお願いします．
-
頑張りたい。
---
私も頑張ります．
-
離散数学の単位の取得に1年かかったことを無駄にしないよう頑張ります。
---
私も頑張ります．
-
4回生ですが初履修です。頑張ります．
---
「4回生」は関西の呼び方ですね．普通，関東では「4年生」といいます．
-
今学期もがんばります。
---
私も頑張ります．
-
分かりやすいので，頑張ります。
---
分かりやすくなくても頑張って下さい ;-)
-
頑張ります
---
私も頑張ります．
-
今年もよろしくお願いします
---
こちらこそよろしくお願いします．
-
今年「も」よろしくお願いします (^o^)
---
こちらこそよろしくお願いします．
-
春休みにしっかり休めた分，やる気に満ちあふれています。これからよろしくお願いします。
---
こちらこそよろしくお願いします．
-
がんばりたいと思います
---
私もがんばりたいと思います
-
しっかりと努力していきます。
---
はい，よろしくお願いします．
-
本当の離散数学を学ぼうと思います．
---
はい，そのためのよい機会なので，しっかりと勉強して下さい．
-
2年の離散数学に引き続き、面白そうだと思い履修しました。
---
面白く感じられる側面がいろいろとあると思いますので，お楽しみに．
-
離散でお世話になりました．授業の方法、テストの方法が自分にあっていてそれが今回もそのままだったので喜んで履修します
---
はい，今回もそのままです．よろしくお願いします．
-
先生の授業をうけるのは離散以来ですが前と変わらないスタイルなので助かります。
---
スタイルが固定されているのはあまりよくないかもしれません．まだいろいろと試している段階なので，少しずつ変わっていくかもしれません．
- 次は要望です．
-
話すスピード (授業内容の進度ではありません) が速くて聞きとれない時があるので少しゆっくり話して頂けると有難いです。
---
よく言われます．気をつけているつもりなのですが，もっと気をつけます．速くなったときは言い直すなど，対策もしてみます．
- 質問をまとめて
-
レポートは全ての問題を解ききれていなくても提出してよいでしょうか。
---
よいです．むしろ，全ての問題を解き切れていることは想定していません．分からなかった問題については，取り組んだ過程においてどの部分でつまったのか書いてもらえれば，ヒントなどを出すことはできます．
-
レポートの提出はルーズリーフでも可能でしょうか？
---
可能です．学籍番号と氏名を書いて提出して下さい．
-
演習問題がわからなかったときは何を参考にすればいいですか？
---
講義資料を参考にして下さい．それが一番よいです．分からない場合は直接質問して下さい．
-
この講義はおもしろいと感じているのですが、履修することはためらわれます．履修していなくともテストを受け点数を聞くことはできますか？
---
「できますか？」に対する回答は「できません」です．試験を受けることは，受講生が持っている権利で，それは厳格に管理されます．たまに，履修登録をしない人が試験を受けてしまっていることがありますが，その場合は，履修登録をしたことにしています．ただ，履修登録をしていなくても，講義を聞きに来てもらうのは構いません．
-
この講義を受講するかどうか悩んでおります．この講義で学ぶことは今後どういった分野の勉強あるいは研究で必要になってくるのか教えてください．
---
一つの回答は情報数理工学コースの教員一覧に書いてある「重視する科目」を見てもらうことです．それによって，どのような分野でどのような内容が重視されているか，という感覚を持てると思います．
もう一つの回答は次の通りです．勉強した内容を今後使っていくのは皆さんです．皆さんの柔軟で自由な発想により，勉強した内容を自分の生活や仕事の中で使っていければよいと思います．特定の内容が特定の仕事にしか使えない，という思い込みや狭い了見がイノベーションを阻害しています．勉強したことを使うのは皆さんなのですから，他の人がいままで何をしてきたのか，ということにあまり固執しない方がよいです．
-
きゅうけいの時間のために持ち込むとよさげな物ってありますか？ のみもの？
---
(アルコールではない) 飲み物や，飴のようなリフレッシュメントを持ち込んでもらっても構いません．
-
degってなんかの略語ですか？
---
degreeです．
-
ユー (u) とブイ (v) は筆記体がいいでしょうか。
---
分かりやすく，区別ができれば，何でも構いません．
-
スライドp43．ある頂点に対して，1か2ということでしょうか．
---
分かりにくくてすみません．「ある頂点に対して1，かつ，ある頂点に対して2」です．
-
なぜpythonですか
---
グラフを扱う際に，pythonのnetworkxというパッケージがとても使いやすいからです．高速であるわけではないのですが，プログラムは簡単に書けます．
- 次は講義の感想
-
ひさしぶりの授業はしんどいですね
---
私もしんどいです (^^;
-
分かりやすかった。
---
急に難しくなるかもしれないので，注意して下さい．
-
資料が分かりやすかった
---
急に難しくなるかもしれないので，注意して下さい．
-
おおむね理解できた．
---
それはよかったです．演習問題を通して理解を深めて下さい．
-
楽しかった
---
次回もお楽しみに．
-
難しすぎる
---
分からない部分は質問をして下さい．皆さんは質問をする権利も持っていますし，分からないときは，質問をする義務があると思って下さい．よろしくお願いします．
-
難しそうですが面白そうだと感じました．
---
難しいからこそ面白い，ということもあると思います．しっかりと勉強していって下さい．
-
初めての内容でまだ理解し切れていませんが、復習したいと思います
---
はい，演習問題は復習のためのよい材料なので，活用して下さい．
-
説明が分かりやすかったです。
---
分からなくなったら，質問をするようにして下さい．
-
証明がなかなか大変そうなイメージを抱いた。べき集合や直積について自分で復習が必要だと感じた。
---
べき集合は今後出てこないかもしれません．証明はこの講義の重要な構成要素なので，できるようになって下さい．
-
mustよりmayが多いのですね。
---
そうですね．いろいろなことは皆さんの自主性に任されています．活かすか活かさないかは皆さん次第です．
-
なんだか自明って書きたくなりますね。
---
そうですが，「自明」と書いてはいけない，と思って下さい．「自明」という言い方は，(本例は「おのずから明らか」という意味であるにも関わらず) 書き手にとっては明らかであることしか指しておらず，それで論理的なコミュニケーションを行なおうとする態度は誤っています．ご注意ください．
-
直感でわかると証明がしづらい
---
直感でわかる，あるいは，直感でわかった気になっているものを，しっかりと表現することが重要です．直観は非常に危険なのです．
-
最大入次数最小入次数最大出次数最小出次数
は早口言葉みたいな感じ
---
早くいわなくてもいいです ;-)
-
離散数学の最後にやったグラフの復習で分かりやすかったです．
---
復習を超える内容にすぐ入るので，注意していて下さい．
-
授業の時間に演習問題をやるのはいいかなと思います。
---
そのように心がけています．また，演習の時間は質問の時間でもあるので，分からない所は積極的に質問して下さい．
-
とてもわかりやすい授業だった
---
油断しているとすぐに分からなくなるので，注意して下さい．
-
最小次数のδがうまく書けないと思った．
---
私は大学生のとき，自発的にギリシャ文字の書き取り練習をしました．そのためか，いまでは割ときれいにギリシャ文字が書けるようになっています．皆さんもお試しください．
- 最後に雑談
-
休みボケが治りません。
---
朝早く起きて，運動しましょう．;-)
-
さくらがちっててさみしいです
---
その無常さが日本人の心をひきつけるのだと思います．
-
今年は天気が悪い日が多く、桜があっという間に散ってしまいましたが、お花見には行けましたか？
---
西9号館の前の桜を見ました ;-)
-
キンコメの今野さんですよね？ 相方は今何をなさっているのですか？
---
相方は今反省しています．
-
まちがえてB101の教室にいってしまった。
---
次回からは間違えないようにして下さい ;-)
-
暗記は悪 ← ごもっとも
---
本当にそう思っています．暗記というか，こういうものは「覚えようとして覚えるもの」ではなく，「覚えてしまっているもの」であると思います．「覚えてしまっている」という段階まで慣れることは極めて難しいです．そのため，覚えることは軽視しているわけです．
-
バイトが忙しくて大変です。
---
有効な時間の使い方を見つけて下さい．とても重要です．
試験・成績
- 中間試験と期末試験により，成績の評価を行います．
- 成績 = min{100, 中間試験の素点+期末試験の素点} (小数点以下切り上げ)
つまり，中間試験の素点+期末試験の素点が59.5点の人の成績は60点で，合格になります．
- 得点分布 (中間試験と期末試験の一方でも受験した人に限る)
- 受講者数 (履修登録者数相当) は81で，
90点以上 (S) が10人 (約12%)，
90点未満80点以上 (A) が10人 (約12%)，
80点未満70点以上 (B) が11人 (約14%)，
70点未満60点以上 (C) が9人 (約11%)，
60点未満 (D) が41人 (約51%) です．
- 中間試験と期末試験の一方でも受験した人の総数は69で，
90点以上 (S) が10人 (約14%)，
90点未満80点以上 (A) が10人 (約14%)，
80点未満70点以上 (B) が11人 (約16%)，
70点未満60点以上 (C) が9人 (約13%)，
60点未満 (D) が29人 (約42%) です．
- 期末試験
- 試験問題 (8月7日実施分)
- 採点：1問15点満点，合計60点満点 (0.5点刻み)
- 得点分布
- 受験した人の数は55，平均点は32.20 (60点満点)．
45点以上 (S相当) が10人 (約18％)，
45点未満40点以上 (A相当) が4人 (約7％)，
40点未満35点以上 (B相当) が6人 (約11％)，
35点未満30点以上 (C相当) が13人 (約24％)，
30点未満 (D相当) が22人 (約40％) です．
- 得点掲示 (辞書順に並べています)
| ##### | 29 |
| ^cocoa | 30 |
| 2AoEZ13 | 37 |
| 3k4Tom | 28 |
| 5014 | 35.5 |
| 9GR-G | 29 |
| AA305 | 35 |
| aaa01 | 23 |
| ASMTT | 28 |
| AYUS | 48.5 |
| AZ56X | 46.5 |
| CLOCK | 20 |
| deque | 33 |
| dsCTHuT | 45 |
| dvorak | 34.5 |
| fubat | 46.5 |
| graph | 41 |
| Jinki | 19 |
| K0MAE | 33 |
| k2132 | 14.5 |
| ksrln | 23 |
| mashiro | 37.5 |
| mr04v | 43 |
| nbhgyt | 21.5 |
| nits | 56.5 |
| odeko | 41 |
| omake | 33.5 |
| opqrs | 30 |
| plqsk | 34 |
| pochi | 55 |
| pupa | 29 |
| riost | 37 |
| sgmsp | 30 |
| SSIN | 11 |
| t54cl | 26.5 |
| tk960 | 45 |
| tmr26 | 33.5 |
| tolip | 18.5 |
| venge | 60 |
| YDTMG | 32 |
| ysuec | 15 |
| zzzuec | 16.5 |
| おいでませ | 30 |
| 太陽神 | 33 |
| 遅延評価 | 20.5 |
| とり天もたき | 41 |
| なつやすみ | 48 |
| ネチガエタ | 11 |
| ひよこ | 51 |
| みみみとみ | 15 |
| もうだめぽ | 39.5 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評
- 総評：試験としては，講義内容が理解できているかできていないか，言語表現が分かっているか分かっていないか，試験準備がしっかりとできているかできていないか，ということがよく分かるものになった気がします．
- 問題1：彩色の問題．演習問題と同じ問題．よくできていました．
「クリークが存在する」といっておきながら，どこに存在するのか示していないものは点がありません．それでは，「○○細胞が存在する」といっておきながら，どこに存在するのか示していないことと同じです．科学とはそういうものです．
- 問題2：線グラフではないことの証明．思いの外できていませんでした．
典型的な間違いは，3つの辺a,b,cがあって，a,bが端点を共有し，b,cが端点を共有し，a,cが端点を共有する場合に，a,b,cも端点を共有するとしてしまうことです．これは必ずしも正しくはありません．また，図にあるグラフの部分グラフが線グラフではないからといって，図にあるグラフが線グラフではないとも言えません．いろいろと注意が必要です．なお，証明自体の記述は2,3行で済みます．
- 問題3：凸多面体に関する問題．演習問題と同じ問題．できている人とできていない人の差が大きな問題でした．演習問題と同じ問題なので，もっとできていてほしかったですし，そもそも何が問われているのか理解できていないと思われる答案も多くありました．
- 問題4：選択問題．Aの方が多く選択されているような気がします．実際，Aを選択したのは35名，Bを選択したのは14名でした．以下に述べる通り，Bの方が簡単だと思ったのですが，取り組んだ皆さんはそうではないと判断されたようです．
- 問題4A：連結度に関する問題．実をいうと，これは昨年度の期末試験に出して，誰も出来なかった問題を少し簡単にしたものです．それでも全然できておらず，完全に正解できたのは1人だけでした．(惜しい解答が2つほどありました．) 数学的帰納法で証明することは割と難しいです (可能ではありますが)．s,t連結度が0になる場合をなぜか考えていない答案も多かったです．s,t連結度が0の場合には，s,t分離集合から頂点を選ぶことができないので注意が必要です．
- 問題4B：二部グラフのマッチングに関する問題．実をいうと，これは演習問題8.5とほぼ同じです．そうだと思って見直してみて下さい．この演習問題を既に解いたことがある人なら，それに気づけば難しくなかったと思います．
- 中間試験
- 試験問題 (6月12日実施分 | 6月20日実施分)
- 採点：1問15点満点，合計60点満点 (0.5点刻み)
- 得点分布 (6月12日実施分，6月20日実施分合わせて)
- 受験した人の数は6月12日と6月20日を合わせて69，平均点は35.14 (60点満点)．
45点以上 (S相当) が20人 (約29％)，
45点未満40点以上 (A相当) が13人 (約19％)，
40点未満35点以上 (B相当) が7人 (約10％)，
35点未満30点以上 (C相当) が7人 (約10％)，
30点未満 (D相当) が22人 (約32％) です．
- 得点掲示 (辞書順に並べています)
| #ARCH | 44 |
| ^yuno | 43 |
| 119229 | 17 |
| 1411010 | 36 |
| 18254 | 19 |
| 19810 | 17 |
| 19hours | 34 |
| 21NOM | 30 |
| 44t28m | 48 |
| 632W9 | 36 |
| a2bst | 26 |
| aaa37 | 17 |
| arisaka | 30 |
| AYUS | 57 |
| bgqnm | 47.5 |
| bytnh8 | 44 |
| CH0FU | 47.5 |
| deque | 43 |
| dth8q | 49 |
| dvrok. | 31.5 |
| gangi | 23 |
| gcbzd | 44 |
| here | 11 |
| hsrln | 18.5 |
| hymkk | 14 |
| kakwe | 30.5 |
| KIGRS | 40 |
| knct | 50 |
| M2l7P5 | 55 |
| MAKSR | 46 |
| mfa44 | 36 |
| MinMn | 11 |
| monoT | 25 |
| mro4v | 38 |
| nbZHENG | 59 |
| nits | 44 |
| o2o1o | 41.5 |
| obake | 42 |
| odeko | 30 |
| OMRIC | 51.5 |
| orien | 23.5 |
| plqsk | 46 |
| pochi | 47 |
| rzsmi | 23 |
| saito | 46 |
| SAME8 | 12.5 |
| tarmac | 46 |
| tk960 | 45 |
| TMGYK | 40.5 |
| tulip | 47.5 |
| uabtf | 49 |
| wtnb7 | 18 |
| ysuec | 15 |
| ZaYbCX | 21 |
| zerop | 19 |
| zzzuec | 24 |
| 単位きて | 38.5 |
| 単位を私に | 26 |
| 遅延評価 | 41.5 |
| とり天 | 51.5 |
| ネチガエタ | 40 |
| ひよこ | 51.5 |
| むずかしい | 41 |
| 難しかった | 19 |
| 柳田格之進 | 38 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 6月12日実施分の講評
- 総評：平均点は高いですが，分散は小さいように感じました．40点以上取れている人が多いですが，一方で，50点以上の人もあまりおらず，10点未満の人はいません．(昨年度の場合は，満点の人もいましたし，0点の人もいました．) あまり点がとれなかった人も期末試験で十分挽回できると思いますので，しっかりと準備をしてきてください．また，点がとれている人も期末試験では油断をしないようにして下さい．以下，各問題に対するコメントです．
- 問題1：次数に関する問題．よくできていました．
(b) の方ですが，「辺数が6だから，存在する」というのは理由になりません．辺数が6であるというのは必要条件であるだけであって，十分条件ではないからです．
- 問題2：最大性論法を用いる問題．思いの外よくできていました．
数学的帰納法で証明しようとしてる人も割といましたが，大体不正解でした (正しい証明ではありませんでした)．数学的帰納法で証明していて正解になっている人は，実際証明の中で最大性論法を用いていました．
- 問題3：最大流と最小s,tカットに関する問題．よくできていました．
問(a)はs,tカットとその容量の定義が分かっているのか，という確認のために出しているのですが，あまり分かっていないということがよく分かりました．感覚や直感で理解をするのではなく，定義を通して理解して下さい．
- 問題4：最小重み完全マッチングと最大重みマッチングの関係を答える問題．ほとんどできていませんでした．
これは「定義に基づいて考える」とか「論理的な手順に従って証明を行う」という，基本的な能力が身についているか見ようとしている問題なのですが，なかなかできていません．「重みが反転するから，最大が最小になる」といっても，それは証明ではありません．一方では「完全マッチング」を考えていて，もう一方では「マッチング」を考える，と，違う対象を考えているわけですから，重みの大小が変わるだけでは話が終わりません．例えば，「max{...}」や「+1」がなければ，この2つが同値であることは証明できませんし，正しいとも限りません．演習問題と同じ問題なので，もっとできていてほしかったです．
- 6月20日実施分の講評
- 総評：こちらは受験者数1なので，「でき」については記載しません．
- 問題1：
最大流に関する問題．
流れとカットを見つければよいです．
- 問題2：
次数に関する問題．
演習問題にある問題なので，素直にやって下さい．
- 問題3：
マッチングに関する問題．
完全マッチングが1つしかないことの証明を上手く行うことが重要です．
- 問題4：
木に関する問題．
最大性論法でなくても，数学的帰納法を用いて証明することもできます．
公式シラバス
こちらをご覧ください
履修上の注意
『グラフとネットワーク』は，『数理解析』(情報・通信工学科)，『数理解析第一』(情報工学科)，『離散数学第二』(情報通信工学科) の読替科目です．
これらを履修した人 (つまり，単位を取得した人) は『グラフとネットワーク』を履修できません．
スケジュール (予定)
- 4/10 (1) グラフの定義と次数：数理
- 4/17 (2) 道と閉路：数理
- 4/24 (3) 木：数理
- 5/1 (4) マッチング：数理
- 5/8 (5) マッチング：モデル化
- 5/15 (6) 最大流：数理
- 5/22 (7) 最大流：モデル化 (1)
- 5/29 (8) 最大流：モデル化 (2)
- 6/5 (9) 連結性：数理とモデル化
- 6/12 中間試験
- 6/19 (10) 彩色：数理
- 6/26 (11) 彩色：モデル化
- 7/3 休講
- 7/10 (12) 平面グラフ：数理
- 7/17 海の日
- 7/24 (13) 平面グラフ：モデル化
- 7/31 授業等調整日 (たぶんやらない)
- 8/7 期末試験
過去の講義
注意：内容や説明法は毎年少しずつ変わっています
過去の試験問題
注意：内容や説明法，試験範囲は毎年変化しています．
[Teaching Top]
[Top]
okamotoy@uec.ac.jp
