グラフとネットワーク
電気通信大学情報理工学域I類 (情報系)
2019年度前学期
金曜3限 (13:00-14:30)
教室：西2-101
岡本 吉央
ショートカット：
講義資料 |
コメント |
試験・成績 |
公式シラバス |
スケジュール |
過去の講義 |
過去の試験問題
講義資料
- 7/26 (13) 平面グラフ：モデル化
- 7/19 (12) 平面グラフ：数理
- 7/12 (11) 彩色：モデル化
- 7/5 (10) 彩色：数理
- 6/28 (9) 連結性：数理とモデル化
- 6/21 (8) 最大流：モデル化 (カットの視点)
- 6/14 (7) 最大流：モデル化 (割当)
- 5/31 (6) 最大流：数理
- 5/24 (5) マッチング：モデル化
- 5/17 (4) マッチング：数理
- 4/26 (3) 木：数理
- 4/19 (2) 道と閉路：数理
- 4/12 (1) グラフの定義と次数：数理
コメント
- 7/26 (13) 平面グラフ：モデル化
- コメントありがとうございました．今回が最終回でした．期末試験には，しっかりと準備をして，臨んで下さい．
-
いままでありがとうございました。
---
こちらこそありがとうございました．
-
ありがとうございました。
---
こちらこそありがとうございました．
-
半年間ありがとうございました。
---
こちらこそありがとうございました．
-
半年間ありがとうございます
---
こちらこそありがとうございました．
-
半期ありがとうございました
とてもおもしろい授業でした．
---
こちらこそありがとうございました．
-
半年間ありがとうございました。
---
こちらこそありがとうございました．
-
4か月間ありがとうございました．離散数理工学も履修しようと思っています
---
こちらこそありがとうございました．後学期もぜひよろしくお願いします．
-
この講義を通じてグラフ問題の知識と論述力を鍛えることができたと感じます。また後期も余裕があればよろしくお願いします。ありがとうございました。
---
そんなに簡単な内容ではなかったと思いますが，最終回までお付き合いいただき，ありがとうございました．
-
おつかれさまでした．
---
お疲れ様でした．
-
お疲れ様でした！
---
お疲れ様でした．
-
授業ありがとうございました．お体 ご自愛下さい
---
ありがとうございます．ご心配をおかけして，すみません．(-_-;
-
講義中具合が悪そうだったので心配になりました。お体に気を付けてください。
---
ありがとうございます．ご心配をおかけして，すみません．(-_-;
-
前期の講義ありがとうございました．お体に気をつけて下さい．
---
こちらこそありがとうございました．
-
お疲れ様でした。お大事に。
---
お疲れ様でした．
-
今日はすっ転んでねんざしました。電通大はすべりやすかったり段差が多いように思います。
---
お大事に．
バリアフリー化はなかなか進まないですね．古い建物ほど，バリアフリー化が進んでいないかと思いきや，新しい (あるいは最近改装した) 建物でも，どうしてこうなってしまったのだろう，と思う部分があったりします．人間の行動でカバーできる部分もあると思うので，ご協力いただければ幸いです．
-
試験がんばります
---
しっかりと準備をしてきてください．
-
期末試験さん対戦よろしくお願いします。
---
私の名前は「期末試験」ではございません．
-
期末試験はどうか簡単な問題を……。
---
達成目標に沿って試験の出題は行われます．よろしくお願いします．
-
対戦よろしくお願いします。焼肉を食べたい気分です。いいお店知りませんか。
---
私はあまり焼肉を食べませんが，よく「調布食肉センター」を勧められます．いかがでしょうか．
-
いろいろと大変でしたが何かと楽しい講義でした。
---
それはよかったです ;-)
-
演習問題を毎回解くのは大変でしたがその分考え方をしっかりと決められるようになったので良かったと思います。
---
演習問題をうまく活かせていただいたようで，よかったです :-)
-
もう一度この講義を履修したいような気持になりました。でも再履することにはなりたくないです。
---
それは複雑な心境ですね (-_-;
-
7月が一瞬で溶けました．
8月はレポートも実験もないのでもう少しゆったり時間が進むといいなと思います．
前期の間、ありがとうございました．
---
そうですね．しっかりと休めるとよいですね．
-
生協でトマトの無料配布が行われていました。学内でのとれたてだった分おいしかったような気がします。
---
おそらく，本当においしかったのだと思います．:-)
-
天気の子、よかったです。
---
明日，観に行きます！
-
8月2日に提出するレポートを返却していただくことはできますか。
---
8月2日に提出していただいたレポートは8月5日以降にお返しします．
-
以上，以下，未満はいいのですが，$x > 6$ を口で説明するとき，いつも困ります．私は「$x$ は $6$ より大きい」と読んでいますが，先生はどう読んでいますか．
---
私も「$x$ は $6$ より大きい」と読んでいます．
-
講義で扱っている証明の流れがわかりやすかった。最大性論法や帰納法などの方法がプログラミングでいう関数よびだしのようにもちいられていて証明が理解しやすかった。
---
証明法はできる限り類型化しようと思っています．そうすることで，自分が何か新しいことを証明しなくてはならなくなったときに，考えるための引き出しからうまく道具を出せるようになると思います．
-
平面グラフのモデル化の例がわかりやすかったです。
---
時間がわりと余ったので，五色定理の証明も紹介できたかもしれません．次の機会のときに備えて考えておきます．
-
追加問題13.4でMinas GeraisとDistrito Federalの境界が1次元的とありますが，1次元的に接することを許すといくつでも同じ点で接することができて平面グラフでない場合が出てきそうです。
例：
この4県はE地点で1次元的に接していて，双対グラフは以下のようになる．
---
「1次元的に接する」ことの説明をしていなかったので，誤解を生んでしまいました．すみません．
「点で接する」ことは「1次元的に接する」ことを意味しません．点で接する場合，それは「0次元的に接する」ことになります．「1次元的に接する」とは，接している部分が長さを持っていることを意味します．そのため，いただいた例では，AとB，AとC，BとD，CとDのみが1次元的に接しています．
なお，0次元的に接しているときにも辺を与えるようにして作ったグラフはmap graphと呼ばれていて，それについては別の研究があります．
-
トーラス上での平面彩色 (トーラス面彩色？) は7色だそうですね。
クラインの壺や他の2次元多様体ではどのようになるのでしょうか？
---
2次元閉曲面上に辺交差なく描くことのできるグラフの染色数については，よく研究されています．Heawood予想 (今となっては定理) というものがあり，それによれば，クラインの壺を例外として，他の2次元閉曲面については，オイラー標数を用いて簡単に染色数を与えることができます．
- 7/19 (12) 平面グラフ：数理
- コメントありがとうございました．次週が最終回となります．
-
コメント
---
コメントありがとうございました．
-
ありがとうございました．
---
こちらこそ．
-
今日は最初はすごく人数が少なかったですね。
---
最後でも人数が少なかったですが ;-)
-
テストが近付いてきて怖いです。
---
なぜか私も怖いです ;-)
-
試験範囲に中間前の内容は含まれるのでしょうか？
---
含まれません．第6回の最初から第13回の最後までです．
-
いつも電車を使わないのもので、2限休講とは知らず大学に来てしまいました。つらいです。
---
そんなときは図書館などで自習すればいいのです ;-)
-
京王線が登校時に運転を見合わせていたので二駅分徒歩で行ったら休講でした。
---
「チクショー一週間」でしょうか．
-
来る途中で自転車のチェーンがはずれて悲しくなった。
---
「チクショー一週間」でしょうか．
-
起きたら午前が休講になっていたらしくびっくりした。
---
起きた時刻によって，びっくり度合いは違うかもしれませんね．
-
暑くなってきました。
---
そうですね．夏ですね．
-
雨の予報が続きますね。
---
もうそろそろ梅雨が明けてほしいと思ってます．
-
今日公開なので早速「天気の子」を観ました。昨日の今日で心の痛くなるニュースも多いですがそれを払拭するような新海監督の演出は素晴らしいと思いました。
---
私も観たいと思ってますが，まだ観てません．(-_-;
-
先生は毎年夏に必ずこれをやる．という行事はありますか
---
研究室で合宿にいっています．
-
コカコーラとペプシだとどちらが好きですか (全く飲まない場合はそう言っていただければ．)
---
どちらもあまり飲まないです．自分で選択して購入することはまずないです．
-
最近追加問題難しいですね。
---
分からないところは是非質問して下さい．
-
ジョルダン曲線定理...
を証明中で使いますね。
---
その通りです．
-
「離散数学」でオイラーの公式についてちょっと学びましたが今回改めて学ぶとどのような考えで証明されていたのかより理解できるようになった気がします．
---
そうですね．証明をすると理解が深まりますし，自分で証明しようとしてみる更に理解が深まります．
-
高校の時，証明なしにオイラーの公式がでてきて気になっていたので解決できて良かった．
---
それはよかったです :-)
-
文字がたくさん出てきて混乱してしまいそうでした。
---
たぶん，オイラーの公式の証明のことだと思います．来年は違う証明を紹介することにするかもしれません．
-
また握手補題が出てきて有能かよってなりました．
---
ですよね :-) 私もそう思います．
-
正多面体が5つしかないことの証明につながるとは思っていなかったので驚きました。
---
こういった「思わぬつながりがある」ということを紹介するのが，この講義の目的なので，それがお伝えできてよかったです．
-
正多面体の証明がすごかったです。
---
似たような問題が演習にありますので，ぜひ取り組んで下さい．
-
正多面体が少ししかないことは以前から不思議に思っていたことだったけれど、グラフによって証明されるとは驚きです．
---
グラフの用語には多面体の用語から来ているものがあります．「頂点」や「辺」はまさにそれです．多面体を見てグラフを思い浮かべるという発想はかなり自然なのだと思います．
- 7/12 (11) 彩色：モデル化
- コメントありがとうございました．
-
ありがとうございました
---
ありがとうございました．
-
お疲れ様です
---
こちらこそお疲れ様です．
-
朝早く起きてタスクを処理しようと思っても当日朝になると二度寝してしまい何も達成できない日々が続きます。
---
早く寝ましょう ;-)
-
来週もよろしくお願いします。
---
こちらこそよろしくお願いします．
-
食あたりになって大変でした．
---
お大事に．
-
ストレスが全部食に向かいます。体重はそこまで増えないのでまだ大丈夫そうですが出費がかさんでしまうのが厳しい所です。
---
食欲がなくなるよりはよいと思います．出費を増やさないように，満足感のある食事ができるといいですね．
-
スライドをみていると，ピザを食べたくなりました．
---
食欲を喚起してしまい，すみません ;-)
-
暑いと思っていたら秋のように寒くなったので大変です．
---
季節の変り目は体調を崩しやすいので，注意して下さい．
-
夏コミの原稿が忙しいです。趣味も程々にした方がいいのかもしれません。
---
何事もバランスが大事ですね．
-
丁度夏季休業まで30日くらいになりました。今年度も時の流れは早いです。
---
確かにそうですね．この授業もあと2回となりました．
-
そういえば、そろそろオープンキャンパスですね。今、忙しいから夏休みにやってほしいですけど…。
---
世間的にはもう夏休みなのです ;-)
-
かだいとテストが....
---
「....」で省略されている部分は何だったのでしょうか？
-
英語で話せるようになりたいと思うのですが、話す力はどのように鍛えればよいでしょうか．
---
よく，留学すると話せるようになると言いますが，私の経験上，留学したからといって簡単に話せるようにはなりません．留学期間が1年ぐらいとなって，はじめて話せるようになると思います．また，留学先として英語圏はあまりお勧めしません．英語圏の人は英語を容赦なく話すので，割と厳しいです．ヨーロッパや英語が通じるアジア (例えば香港やシンガポール) だと，話す方も手加減をしてくれるので，かなりコミュニケーションがとりやすいと思います．留学に関しては東2号館の1階で情報が得られると思います．
-
ICPC国内予選がんばるぞい！
---
ぜひ頑張って下さい :-)
-
「最強のふたり」を観ました。様々なディスアドバンテージがあってもそれを気にせず一人の人物としてお互いを評価する2人の関係がとても理想的だなと思いました。
---
すみません，私は観ていません．今度機会があれば観てみます．
-
いつか私にもこのモノクロな毎日を彩色してくれる人は現れるでしょうか？ (ミスチルの歌詞みたいですね…)
---
『彩り』ですね :-)
-
ジョブスケジューリングとガベレージコレクションは関係がありますか？
---
「ガベレージコレクション」は「ガベージコレクション」だと見なします．
講義で扱ったジョブスケジューリングと普通のガベージコレクションは関係ないと思います．ちょっと私には関係が見つけられないです．
-
「$\omega(G) = \chi(G)$ → $G$ は区間グラフ」といえますか？
---
これは言えないです．講義で扱った頂点数4の閉路は区間グラフではありませんが，クリーク数と染色数が一致するものになっています．
-
与えられたグラフが、区間グラフであるか、や単位円グラフであるか、と簡単に判別する方法はあるのでしょうか？
---
区間グラフについては，線形時間で判定する方法 (アルゴリズム) が知られています．特に，この論文では，ある種の幅優先探索を6回行う事で判定するアルゴリズムが考案されています．
一方，単位円グラフについては，簡単な方法は知られておらず，実際，この論文で，NP完全問題よりも難しい (と思われている) 問題であることが証明されています．
-
内容が少なめだったからかついていけた気がします．
---
ぜひ演習問題にも取り組んで下さい．
-
今回の定理・性質などは，数学的に証明しようとすると難しいですが，直感では理解できました。
---
まずは，直感で理解するところから始めて下さい．
-
言葉で説明するのが難しそう。
---
そうですね．絵を描いて考えるときは直感に訴えていますが，それを言葉で表現することはとても重要なので，実践して下さい．
-
最後が難しかったです．
---
ちょっと，彩色の部分は説明の仕方がよくなかったのではないかと反省しています．来年度に活かします．
-
よくこんな色々なことを思い付くなと思った。
---
それがこの講義で紹介したいことです．まずは先人の行ってきたことを学んで，次に，それを自分でもできるようになる，ということまで進められれば完璧です．
-
前回の演習で難しいところが所々あったので彩色のところは特に頑張って勉強したいと思いました。
---
分からないところは，どしどし質問して下さい．お待ちしております．
- 7/5 (10) 彩色：数理
- コメントありがとうございました．
- [重要]
レポート (テスト) で彩色の問題が出たときに色ボールペンを使った説明をしてもよろしいですか？
---
可能です．しかし，それによる不利益に関する責を私は負えませんので，その点はご理解ください．
-
宿題の範囲を間違えたのでしょんぼりしています．
---
しょんぼりっくリンクですね．;-)
-
最近天気がよくない日が続いて洗濯するのに困っています．
---
洗濯する日を選択できないのですね．
-
講義ありがとうございました．お体にはきをつけてください．
---
お気遣い，ありがとうございます．:-)
-
最近息苦しくなってせきがよく出るのですが何かの病気でしょうか？
---
私は医師ではないので，診断できません．大学内にも保健管理センターがあるので，ぜひ相談に行ってみて下さい．
-
先週は熱を出して死んでいました
---
今週は授業に出てこられているので，死んではいませんね ;-)
-
ここに書くことを考えてきたのですが、何を書きたかったのか忘れてしまいました
---
それは残念です (-_-; また次回お願いします．
-
ビアホール行ってきます。お酒好き。
---
そういう季節になりましたね．どうぞどうぞ :-)
-
おもしろい内容でした
---
次回もお楽しみに．
-
最近，昼でも眠い日が多くて困っています．
---
夜にしっかりと寝ましょう．:-)
-
心の健やかさは大事ですね。
---
そうですね．心の健康が体の健康と関連することもあると思います．
-
MICS実験のレポートが大変です...
---
なんでもやりっぱなしにしておくのはよくないので，しっかりとまとめられるようにして下さい．
-
暑いのは良いのですが雨で湿度が高いと汗をかくので苦手です。
---
その気持ちは分かります ;-)
-
バイトのシフトを減らして学習にあてたいのですがもっとお金は欲しいというジレンマ
---
ジレンマやトレードオフがあるときに，最もよいバランスを考える，というのは，最適化の基本の1つです．勉強して，ぜひ身につけて下さい．
-
中間テストは一番早かったのですが期末テストは一番遅くなりそうです。
---
期末試験は学事暦どおりに計画し，実施します．
-
テストを8/2に行う事を考えたことはありませんか。
---
ないです．
-
最近 (発展) が無いんですね．
---
確かにそうですね．次回はありますので，お楽しみに．:-)
-
ギリシャ人なんか凄そう。
---
ギリシャに数回いったことがありますが，街中のいくつかのオープンカフェでみんなバックギャモンをやっていて，その光景は面白かったです．
-
「いま、会いに行きます」を観ました。僕も時を越えて会いたい単位があります。
---
叶わぬ願いですね (-_-;
-
頭パンクしそうでしたけど耐えました．
---
頭パンク，といえば，『スキャナー』という映画のワンシーンを思い出します．(グロ閲覧注意です．)
-
ワンピースに「ドン・クリーク」というキャラがいます。貪・クリーク。彩色が得意そうですね。
---
ドン・クリークさんはクリーク海賊団のドンなのですね．「クリーク (clique)」には「派閥」とか「一派」という意味があるので，「クリーク海賊団」という名付けは，同意反復のようで，ちょっと気持ち悪いです．
-
クリークと完全グラフは違うのですか？
---
グラフの中の部分グラフで，完全グラフとなっているものの頂点集合がクリークです．一言で言えば，クリークとは完全部分グラフの頂点集合です．クリークは頂点集合であることに注意して下さい．逆に，クリークを頂点集合として持つ部分グラフは，必ず完全グラフになります．
-
Grötzschグラフについて調べたところハミルトン路を持つということで，探してみました。ハミルトン閉路は持つのでしょうか？
---
次のようなハミルトン閉路があるようです．どうでしょうか？
-
彩色という名前はとても直感的で分かりやすいけれど、なぜ色なのかと思いました．
---
伝統的に，集合をいくつかの部分に分割することを彩色ということがあり，その伝統に則っています．
-
地図は4色あれば同色が隣り合わずにぬり分けられる，というのを思い出しました。
---
これは最終回 (第13回) で扱います．お楽しみに．
-
オープンラボでクリーク数を早く求めるアルゴリズムを研究している人がいました。クリーク数求めるのは、すごく時間がかかるらしいですね。
---
そうですね．クリーク数を計算する問題は難しい問題 (NP困難な問題) であることが知られています．
-
3彩色 ;)
---
確かに3彩色可能ですね ;-)
-
ガリレオというドラマに出ていて、印象的だった彩色問題が実際に講義に出てきて少し感動しました．
---
離散数学が出てくる映画として，『グッド・ウィル・ハンティング』があります．マット・デイモンが演じる主人公が易々と解いてしまう廊下の黒板の問題はグラフ理論の典型的な問題です (が，前提知識がなければもちろん難しいです)．
-
今週から話題が変わりましたが、相変わらず興味深いです。
---
次回も彩色の話を続けます．お楽しみに．
-
レジスタ割当で彩色が考えられるのは面白いと思いました。
---
そうですね．レジスタ割当は彩色の応用としてよく現れるので，コンパイラを設計する人にとっては，避けて通れないものです．
-
いろいろな弱双対性のおはなしが講義に出てきましたが，これらを一般化したようなものはあるのでしょうか．証明のしかたがなんとなく似ているような気がしたので，もしかしたらあるのかも，と思いました．
---
これは重要な視点ですね．答えは「あります」になります．それは「線形計画法の弱双対定理」です．この講義でいろいろな弱双対性を紹介していますが，それはすべて「線形計画法の弱双対定理」の特別な場合です．また，「線形計画法の弱双対定理」の証明は，この講義で行っている弱双対性の証明をそのまま線形計画法に焼き直すと得られます．これは後学期の『数理計画法』で扱いますので，そのときに似ている点と異なっている点に着目して下さい．
-
学生に対応した頂点と研究室に対応した頂点をつくって学生が行きたい研究室に弧をつくって最大流求めたい。
---
ぜひやってみて下さい ;-)
-
先生は、所属は情報系でもプログラミングという行為自体や言語にはそこまで惹かれないほうですか？
---
「そこまで」というときの比較対象に依存しますが，私は「情報系＝プログラミング」だと思っていないので，その意味では「そこまで惹かれない」と言ってもよいかもしれません．日本評論社から出ている『数学ガイダンス2018』という本に「情報系の数学」という記事を私が書いたのですが，そこを見て頂ければ，私が「情報系におけるプログラミング」をどのように思っているのか，ということが冒頭に書いてありますので，ぜひご覧ください．(私の研究室に来ていただければ，コピーを配っています．)
- 6/28 (9) 連結性：数理とモデル化
- コメントありがとうございました．
-
コメントありがとうございました．
---
コメントありがとうございました．
-
ありがとうございました
---
こちらこそありがとうございました．
-
タピオカミルクティー飲みたい。
---
「パンケーキ食べたい」みたいなものでしょうか．
-
来週もよろしくお願いします。
---
次回は少し毛色の違う話題になります．お楽しみに．
-
新しい言葉が多くて脳が追いついていかなかった。
---
Oh, no.
-
今回でてきた証明はどれも理解するのに時間がかかりそうだと思いました
---
しっかりと復習をしてください．
-
Mengerの定理で、同じ弧を共有しないものの最大数がs,t弧連結度と等しいことがあまり納得できなかったので帰ってよく考えます．
---
分からない部分は質問していただいて構わないので，直接聞いて下さい．直接聞くことがもっとも手っ取り早いと思います．
-
モデル化問題とくのつかれました。
---
お疲れ様です．
-
実験課題がたまってきて、つらいです．
---
お疲れ様です．
-
お疲れ様です
---
お疲れ様です．
-
上手にs,tカットができません。何かコツがあるのでしょうか？
---
最大流が分かれば，補助ネットワークを使うことで，最小s,tカットが自動的に求まります．
-
最大流を使うもの、多いですね
---
そうですね．この半年の講義では，最大流の扱いに割と重きを置いています．「流すことに対応させる」という考え方はよく使えるからです．
-
今回の講義を応用して運休につよい旅行日程をたてたいです．
---
ぜひやってみてください！
-
s, t点 (弧) 連結度を求める際に最小カットモデルを考えずにMengerの定理を用いればその値がわかるという解釈で良いのでしょうか？
---
はい．その通りです．
-
大域点連結度について、任意の $s,t$ に対し $\{s,t\} \in E$ (または $(s,t) \in A$) のとき、$\kappa(G) = |V|-1$ と定義していましたが、こう定義すると何か嬉しいことはありますか？ なぜ $|V|-1$ なんでしょうか．
---
嬉しいことがあります．例えば，完全グラフにおいて，2つの頂点 $s,t$ の間に ($s,t$ 以外の) 頂点を共有しない$|V|-1$個の道が存在することになりますが，これは点連結度の $|V|-1$ と一致し，Mengerの定理が完全グラフでも成り立つことが分かります．
-
弧連結度と最小カットの双対性証明で除去する弧は、それがカットとなるような極小のもの、ということで合っていますか？
必要以上にt→s方向の弧を取り除くと、カットの容量よりおおきくなってしまう気がします。
---
極小なものだけを考えれば十分である，という意味では正しいです．
-
今回のプリントのpp 12, 17, 25, 29にある「自然数 $k \geq 0$」とは，「自然数 $k \geq 1$」のことですか？
---
これは $k\geq 0$ でよいです．ただ，$k=0$ の場合「つまり」の後に書いてある $k-1$ を真面目に考えると $-1$ になってしまい，意味を成さなくなるので，$k=0$ の場合は「つまり」の後に書いてあることは適用しない (考えない) と思って下さい．別の言い方をすれば，非連結なグラフは 0辺連結 (0点連結) ですが，1辺連結 (1点連結) ではないと思って下さい．
-
カール・メンガー、メンガーのスポンジのメンガーかなと思って調べたら別のメンガーさんがでてきました。しかもこのカール・メンガーさんはカール・メンガーの父らしいです。一体何故...。
---
このカール・メンガー (Karl Menger) はメンガーのスポンジのメンガーのはずです．カール・メンガーの父はカール・メンガー (Carl Menger) ですが，父は経済学者だそうです．
-
頂点を分割して弧で考えるというのは初めに考えついた人はすごいなと思いました．
---
そうですね．一般に，頂点が関わる問題は，辺 (弧) が関わる問題よりも難しいことが多いです．
-
最近時間の経過が早い気がします。20歳以上になるともっと早く感じるのでしょうか？
---
ジャネの法則というらしいです．
-
昨日の夜の気候の、生温くて気持ちの悪さが好きでした。
---
分かる気がします．;-)
-
暑くて溶けそうです。
---
分かる気がします．:-)
-
先日ついに冷房をつけてしまいました。むし暑くて無しで生活できません
---
扇風機も併用するとよいと思います．
-
先生の家族構成は？
---
これは明かしてよい個人情報か分からないので，お伝えできません．
-
小さいころのあだ名は？
---
覚えてないですし，たぶんなかったと思います．
-
血液型は？
---
これは明かしてよい個人情報か分からないので，お伝えできません．
-
好きな女性のタイプは？
---
これは相手がいることなので，私の判断でお伝えすることはできません．
-
しゅみは何ですか？
---
DVDで映画を見ることです．
-
最近のマイブームは？
---
DVDで映画を見てます．
-
好きなマンガってありますか？
---
マンガはあまり読まないですが，大昔にデスノートは全部読みました．
-
先生にとって一番かけがえのないものとは、何ですか？
---
自分自身です．自分が自分であることは何にも変えられません．
- 6/21 (8) 最大流：モデル化 (カットの視点)
- コメントありがとうございました．
-
近所のペットショップにいる大きな鳥が疲れきっていて，精神を病んでいそうで見るも哀れです．どうしたらなぐさめられるでしょうか．
---
『E.T.』のカエルの実験のシーンを思い浮かべますね．
-
最近，腱しょう炎がひどいです．この間のテストのカンペを作ったときにとどめを刺されました．
---
お大事になさってください．
-
国際関数型言語学会プログラミングコンテストの開幕まで5時間を切りました。チームが組めずに1人ですがたのしみです。
---
ぜひ楽しんで下さい :-)
-
来週までマックのポテト全サイズ150円です。安い。
---
私としては，もう少し太い方が好きです．
-
好きな飲み物って何ですか？
---
最近は，ドトールでロイヤルミルクティーを飲んでいます．
-
お疲れ様です
---
こちらこそ，お疲れ様です．
-
中間試験の結果がそこそこ良かったのでほっとしました。
---
期末試験も油断せずに取り組んで下さい :-)
-
中間の結果が良かったので期末も頑張ります。
---
はい，よろしくお願いします．
-
中間試験の答えは教えてくれますか
---
直接聞いて下さい．
-
このままだと不可になりそうなので今日からちゃんと勉強します．
---
はい，まず演習問題に取り組むとよいと思います．
-
中間試験は思ってたよりできてる?みたいなのでよかったです。期末試験はどうなるのか分かりませんがもっといい点とれるようにがんばりたいです。
---
どうなるか分からない，というのは確かだと思います．しっかりと復習をして下さい．
-
期末の日程はいつ決まりますか。
---
最終的には，教務課から連絡 (掲示) があります．一応，8月9日にしていただくように要請はしています．
-
Konig-Egervaryの定理を調べると岡本先生ばかりでてきて驚いた
---
これには私も驚いています :-)
-
先生はグラフを自作しているとおっしゃっていましたが、何を使って描かれているのでしょうか．
---
IPEです．フリーのドローイング・エディタです．
-
写真好きです。
---
裏に込められた意味は「実物は嫌い」ということでしょうか？ (-_-;
-
私はこの画像の領域分割について真に驚くべき方法をみつけたが、この余白はそれを書くには小さすぎる。
---
つまり「おいらの方法」ということですね．
-
カット問題が画像処理に活用できるのはおどろきでした。
---
皆さんにおどろきを提供できて，よかったです．:-)
-
画像処理に最小カットが使えると思いついた人、この世のもの全部グラフに見えてそう…
---
「この世のもの全部○○に見える」というのは，専門家にとって重要だと思います．私も，世の中のほとんどのものは最適化やアルゴリズムに見えています．皆さんも，それぞれ「○○」に入るものは違っていて問題ないので，このような視点を作り上げて下さい．
-
画像処理の実験とてもおもしろかったです．
---
プログラムを授業中に動かしたのは，今回が最初でしたね．皆さんもぜひ試してみて下さい．
-
実際に書かれたコードでの実験が興味深かった．意外と実行に時間がかかるんだなと思った．(pythonの勉強に使いたいのですが、よろしければ、共有などは考えておりませんでしょうか)
---
講義資料の「Jupyter Notebook」の項目で公開しています．どうぞ．
-
グラフカットを自分で動かしてみたい。
---
インターネット上の画像ではなく，自分のローカル・ディスクにある画像でも実験できますので，やってみて下さい．
-
画像関係に興味がなかったが、実演面白くて興味がでた
---
実験をお見せして，よかったみたいですね :-)
-
画像にも応用がきくのは面白いと思った。
---
そうですね．実を言えば，画像処理は最適化問題の宝庫です．画像に関する多くの問題が最適化手法を使って解決されています．
-
最大流の考え方が画像の加工にも応用できるというのはかなり衝撃的です。このような発想力を培いたいです．
---
画像をグラフと見なす，という考え方はかなりメジャーになっています．
-
画像の領域分割の所は特に興味深かったです。
---
画像の領域分割のはなしは，今年新たに加えた内容なのですが，楽しんでいただけたようでよかったです．:-)
-
画像処理の件で背景は必ずしも1つのカテゴリーの色だけではないはずです。(例えば、海の背景なら、海は青系、砂は白)。そのような時は、今回の授業のやり方では、処理をやりにくいことはないでしょうか？
---
その通りだと思うので，実際にやってみました．どうでしょうか？
(画像は https://www.sloanerealty.com/ocean-isle-beach-vacation-rentalsより．)
-
ここ最近の授業では最大流や最小カットの話が多いですが，色々な問題をモデル化してみると，強双対性の便利さを改めて実感させられます。
---
そうですね．次回もまた最大流の話がでてきますので，強双対性の便利さを感じて下さい．
-
最大流問題としてモデル化するのは面白いと感じますが、モデル化した時点で最大流問題を解かずとも答えがわかってしまうとなんだか萎えてしまいます。(前回の優勝可能性判定では「残り対戦数」が「他チームがあとどれだけ勝ってもいいか」の数値をこえた時とか…)
---
たしかにそうですね．授業で使っている例はあまりよくないかもしれません．ただ，実際の応用では，もっと規模が大きな問題を扱うことになり，その場合には，授業で使っている例ほど簡単にわからないことも多いと思います．
-
露天掘りの問題を、最大流問題に還元して解こうとする発想はすごいと思いました。自分はまだまだ、問題の本質を見極める能力が足りないように感じます...
---
私もこの発想はすごいと思います．しかし，これは1970年代に既に知られていたことなのです．学問の蓄積がいかに重要か，考えさせられますし，そのような蓄積の歴史を経て，私たちがそれを超える何かを生み出していかなければならないわけです．
-
ろてんぼりの最大流をみつけるのがとても大変そうだと思いました．
---
目で見つけるのは，確かに大変ですね．授業で扱っている例は小さいので，頑張って増加道法を動かすか，じっと睨んで見つけるか，どちらかをして下さい．いずれにしても，最小s,tカットを同時に見つけて，最適性を保証することが重要です．
- 6/14 (7) 最大流：モデル化 (割当)
- コメントありがとうございました．
-
天気がようやく良くなったのでたまっていた洗たくができそうです．
---
雨の間は，するかしないかという選択すらできなかったですからね．:-)
-
明日は雨らしい．
---
しかも，大雨らしいです．
-
暑かったり涼しかったりして服を選ぶのが難しいです。
---
季節の変り目は体調を崩しやすいのでご注意ください．
-
暑いより寒い方が好きなので段々嫌な季節になってきました…。軽装な分、洗濯は楽ですが。
---
これが日本の四季なので，慣れましょう．:-)
-
きょうはありがとうございました．
---
こちらこそありがとうございます．
-
梅雨ですか？雨は嫌いです．
---
私は梅雨ではありません．
-
中間試験さん対戦ありがとうございました。
---
私は中間試験さんではありません．
-
中間試験の結果はいつ頃出ますか？
---
採点が完了し次第，ご連絡します．
-
中間あまり良くなかったので、期末までに積極的にレポート出していきたいと思います．
---
はい，よろしくお願いします．
-
テストの結果があまり良くありませんでした。
---
それは残念です．
-
中間試験の大問4が難しかったです。
---
気付けば3行ぐらいで終わります．
-
テストで自分が解けなかった問題について、後学の為にどのように解けばよいのかを学びたいのですが、どうすればよいでしょうか。
---
直接聞いて下さい．演習の間，何も質問がないので，私は時間を持て余しています．よろしくお願いします．
-
2019年度グラフとネットワーク中間試験：難化
---
そうなんか．
-
中間試験がボロクソでした．単位をとれる気がしません．
---
期末試験で60点をとればよいのです．
-
マックのポテト、おいしいですよね．
---
私としては，もう少し太い方が好きです．
-
難しいです。生協のチーズタッカルビ風パンおいしい。
---
そんなパンがあるのですね．温めて食べるものなのでしょうか？
-
食べ物の好き嫌いはありますか？
---
これは私の弱点なので，お伝えしたくありません ;-)
-
最近コーヒをよく飲みます
---
「コーヒ」と書くと，「コンピュータ」とか「ルータ」みたいで，とても工学的な感じがします．
-
先生は犬と猫どちらかを飼わなければならないとしたらどちらになさいますか？
---
できればどちらも飼いたくないのですが．
-
なかなか難しくなってきた気がします．がんばります
---
今日は，前回までの内容をたくさん使ったので，その部分を思い出すのに時間がかかったかもしれませんね．しっかりと復習をしてみて下さい．
-
流れのあたりから定義がたくさんあって混乱してます
---
定義を理解することは重要なので，まずはそこから始めて下さい．
-
証明で理解できなかった部分があったので復習してきます．
---
はい，復習しても分からなかったら，ぜひ質問して下さい．
-
解説とても分かりやすいです．
---
ありがとうございます．分からない所がでてきたら，ぜひ質問して下さい．
-
最大流の問題がパイプの配管設計以外に役立つことが分かった．
---
そうですね．重要な着眼点だと思います．「パイプの配管設計」のように，どう考えてもグラフや流れの概念と関係があるものをモデル化できることは想像しやすいと思いますが，今日の講義で扱ったような問題も最大流問題を通してモデル化し，解くことができるというのは，想像しにくかったと思います．それだからこそ，モデル化の考え方をこの講義ではお伝えしたいのです．
-
「最大流問題としてモデル化」はどこまで書いたらモデル化できたことになりますか？
例えば、sからtへの有向グラフを書けて、その弧に容量を割りふれた状態 (スライドp.10) など。
---
それを書いた上で，元の問題の解答と最大流問題の解答がどのように関係しているのかも述べて下さい．
-
電通大で必修科目や選択科目を落としまくってる人がこれからの履修計画をするときに、最大流のモデル化を使えば留年が確定してるかどうか確かめられますかね？
---
考えてみると面白いと思いますね．ただ，モデル化する際に注意しないといけないことが1つあります．それは，例えば，「選択科目を○○単位以上取得しなくてはならない」というような条件は，流れの方で考えると，「ある特定の部分を流れている総量が△△以上でなくてはならない」という形でモデル化されることです．流れに対する容量制約は「流れは△△以下でなくてはならない」というものなので，「以上」と「以下」という両立しない制約を考える必要がでてくることになります．「△△以上でなくてはならない」という制約を考えることは不可能ではありませんが，モデル化する際に注意する必要があります．
-
オアシスの問題は、次のような
二部グラフの最大マッチング問題ととらえることも出来るのでしょうか ($|A|\neq |B|$ なので完全マッチングとはなりませんが…)。
---
完全に正しいです．
注意点が1つあります．このようなグラフを作ると頂点数が「最大救護可能人数の和＋遭難者の総数」になります．これだと，例えば，オアシスの救護可能人数が1万人とかそういう場合では，頂点数が1万ぐらいになってしまい，計算にとても長い時間がかかってしまうかもしれません．一方で，授業で紹介したモデル化では，頂点数は「オアシスの総数＋遭難者の総数」ぐらいになりますので，そこまで頂点数が膨大になることはなく，早く計算が終了することが期待できます．(アルゴリズム理論的に言えば，「擬多項式時間」と「多項式時間」の違いということになるのですが，それはちょっと進んだ内容になります．)
-
せっかくなので今日の講義をきいたあとに二部グラフの最大マッチングをやりたかったです．
---
情報・通信工学科では，比較的前提知識を必要としないJ8課題を先の方でやることになっていました (例えば，「論理設計学」は3年前学期の科目だったので，J1から始めるわけにはいかなかったのです)．いま，I類となった後では，前提知識が学習済みである課題は増えたので，スケジュールを組み直してもよいのかもしれませんが，そういうことを始めると，全体のバランスが崩れるかもしれないので，慎重にならないといけないですね．
-
最大流問題の図がその名前に即していて分かりやすかった。
最大流問題に限らずですが、こういったものはアルゴリズムが出来てからそれに即して名付けられるのか、その名前のイメージを元にアルゴリズムが考案されるのかどちらなのでしょうか。
---
普通は，問題を解くためにアルゴリズムを考えるわけなので，問題が先にできています．
-
日本プロ野球のように引き分けがあるルールだと優勝可能性判定問題はどのくらい難しくなるのでしょうか
---
引き分けの扱い方により変わってきます．勝ち点を与える方式で，勝ちには2点，引き分けには1点，負けには0点を与えるとして，最終的に勝ち点が最も大きいチームが優勝するとする場合は，講義で考えた方法と同じように「勝ち点2点を2チームに割り当てる」という考え方ができるので，最大流問題としてモデル化できます．日本プロ野球の場合，勝率で順位を決めますが，この勝率は「勝ち数/(勝ち数+負け数)」なので，引き分けがある場合に，計算がややこしくなります (比を扱うことは大抵の場合でややこしくなります)．私の見立てでは，最大流問題としてモデル化できないような気がします．
-
今プロ野球は交流戦なので12球団で優勝可能性を探すともっと楽しそうですね。
---
交流戦での優勝可能性，ということですね．交流戦の順位は勝率で決定されるそうなので，上のコメントと同じように，ややこしくなると思います．
-
DETが優勝出来る可能性が0だなんて知りたくなかった…
---
いわゆる「マジックナンバー」とか「クリンチナンバー」というのはこの手の話題と関係があり，そこでも最適化技法が使われています．
-
今回のデトロイトの優勝不可能性確認では
tに入る流れの合計＝1+5+7+13=26＜27＝sから出る流れの合計
というグラフ使わずとも分かる強い条件が成り立っていて、あまり良い例ではありませんでしたね...
---
その通りだと思います．ぜひ演習問題もやってみて下さい．
-
「フィールド・オブ・ドリームス」観ました。(丁度MLBの話でしたね。) 自分も何か目標や決意を持って、それを崩さず生きていきたいです。
---
日本だと「黒い霧事件」というのがありましたね．野球がアメリカでいまなお国民的スポーツとして捉えられているのに対して，日本での野球に対する捉えられ方はだいぶ変わってきているような気がします．
-
図を積極的に用いて証明するのはありでしょうか？
---
図と文章をうまく使い分けられるとよいと思います．図だけではあいまいな場合が多くなります．一方，文章だけでは分かりにくくなります．バランスが重要だと思います．
-
証明ばしばしできる男になりたい
---
しばしばそのような思いを持つようにして下さい．
- 5/31 (6) 最大流：数理
- コメントありがとうございました．来週は中間試験です．しっかりと準備をしてきてください．
-
明日先生の研究室見学しに行きます．
---
よろしくお願いします．
-
冷房がちょっと寒かったです。環境のためにも温度を少し上げて欲しいです．
---
確認したところ，冷房ではなく送風でした．
-
教室がめちゃくちゃ寒かったです．
---
直接言ってもらえれば，そのときに確認できるので，そうしていただけると助かります．
-
最後の方、少々教室が寒かった。
---
私からも伺えばよかったです．
-
エアコンがよく効いてすこし寒かった
---
私からも伺えばよかったです．
-
お疲れ様です
---
ありがとうございます．
-
特にありません
---
それでも構わないので，この紙を提出し続けて下さい．:-)
-
この紙に書くことが思い浮かばない程度には自分は話題のない人間だということに気付いてつらいです
---
その場で考えても思いつかないかもしれないので，1週間かけて，書くことを準備してきてください ;-)
-
ありがとうございました。
---
こちらこそありがとうございます．
-
ありがとうございました．
---
こちらこそありがとうございます．
-
先週はうっかり休んでしまいました。心健やかに生きたいです。
---
お大事に．
-
分かりやすかったです．
---
分からなくなったら，質問して下さい．よろしくお願いします．
-
前回の演習5.7の中にある「部集合」というのが何かわからなかった。
---
これは第4回講義資料の32ページに書いてある通りです．
-
テスト難しそうでこわいです。
---
しっかりと準備してきてください．
-
試験がんばります．
---
しっかりと準備してきてください．
-
題名：単位をください (翼をくださいよりパロディ)
歌詞：♪いま〜私の〜ねが〜いごとが〜かな〜う〜な〜らば〜単位〜
が〜ほし〜い♪
---
しっかりと準備してきてください．
-
中間テストがんばります
---
しっかりと準備してきてください．
-
中間のことを考えると夜も寝られません。
---
寝て下さい :-)
-
寝不足ぎみなので，よい解消法を教えてください
---
メリハリを持って，「寝るときは寝る」と決めるとよいと思います．スマホをいじりながら寝る，とか，そういうことはしない方がよいと思います．(個人の感想です．)
-
テストの採点基準はどのようになっていますか。部分点はありますか。
---
部分点はあります．
-
今朝から手荒れが酷く，手がカサカサです。家事は水仕事が多いので気をつけていても悪化してしまいます…
---
ゴム手袋を着けるとよいと思います．
-
パスタをお弁当箱に詰めて持ってきたら案の定麺がカチカチになってました。
---
「チキショー」でしょうか？
-
毎回証明に穴がないか不安になります。
---
気持ちはわかります．そのために，レポート提出制度があると思って下さい．
-
過去の演習問題を解き直すと以前よりもきちんと記述できるようになってきた気がします．
---
それは素晴らしいです．成長している証だと思います．
-
分かりやすい説明で理解しやすかったです
---
分からなくなったら，ぜひ質問をして下さい．
-
先生の好きなお菓子は何ですか。
---
よく「ルマンド」といってる気がします．「アルフォート」も好きです．
-
「ニュー・シネマ・パラダイス」を観ました。30年前の作品ですがノスタルジーというものの魅力はどの世界でも変わらないものですね。
---
そうですね．名作と呼ばれるものには，そう呼ばれるだけの理由があるものだと思います．
-
毎回質問に全部答えるのは、大変ではないのですか？
---
はい，大変です．;-) しかし，これによって私はかけがえのないものを学ぶことができます．とても重要なのです．
-
数学は確かに無理数も完全か不完全か，もうスリムに化した吐くガウス
---
すみません，ちょっと，何を意味してるかわからなかったです．(-_-;
-
尾も白いに気付くまで時間がかかりました
---
気付かれることはあまり想定せずに書いているので，気にしないでください :-)
-
最大流問題は馴染みがないこともあり、理解に時間がかかった。
---
はじめて遭遇する概念は難しいですよね．しっかり復習をして，理解して下さい．
-
大学の単位は流量保存制約に従わないようにしたいです
---
私も祈念いたします．
-
スライドp6のグラフにおいて，「頂点部分集合 S={s,b} は s-tカットであり，cap(S)=9である．」は正しいですか？
---
はい，その通りです．
-
$\displaystyle \sum_{u:(u,v)\in A}$ を $\displaystyle \sum_{u \in N_G(\{v\})}$ と書いても通じますか？
---
考え方はよいですが，少し工夫が必要になります．
有向グラフの場合は，弧の始点と終点を区別するので，$N^+_G(v)$ や $N^-_G(v)$ という記法を使います．$N^+_G(v)$ で $v$ を始点とする弧の終点となる頂点の集合，$N^-_G(v)$ で $v$ を終点とする弧の始点となる頂点の集合を表します．このとき， $\displaystyle \sum_{u:(u,v)\in A}$ は $\displaystyle \sum_{u \in N^-_G(\{v\})}$ となります．
-
テストで、$f((u,v))$ などを $f(u,v)$ と表記しても良いでしょうか？
---
よいです．そのような省略表記は一般的に認められていると思います．
-
増加道法は実験で2部グラフの最大マッチング探索アルゴリズムとして登場したのですが、これはすべての辺の容量を1とした最大流問題として解いているということに気付きました．
---
その通りです．これは次回詳しく扱います．
-
増加道法によるアルゴリズムが最大流最小カット定理の無理数バージョンでの証明に使えないのは、増加道法が永遠に終了しない場合があるからでしょうか？
---
はい，その通りです．ただし，そのような例を見つけるのは，そんなに簡単ではないです．
-
最大流-最小カットの関係は直感だと正しそうなのに証明すようとすると大変で、意外でした．
---
大変だと見えるのは，私の説明がよくないか，あるいは，(人類全体として) 我々が最大流と最小カットの関係を深く理解していないか，のどちらかのせいだと思います．
-
今までの講義の中でいちばん興味深かったです (アルゴリズムの部分が)．
次回の証明が気になります．実際にこのアルゴリズムを実装するのは大変でしょうか
---
アルゴリズムの実装はそれほど大変ではないと思います．MICSの3年生にとっては，後学期の実験第二のテーマとして，実装をすることがあるかもしれません．
-
離散数学や離散アルゴリズムや離散最適化に関わる研究をしている研究しようと思っている人は、この科目は余裕を持ってクリアできなければならないのでしょうか？ (ぶっちゃけると、この授業の演習問題を解くのにとても苦労しているような人は上記のような研究をするのには適性が無いと思ってよいのでしょうか？)
---
適性がないかどうかは分からないです．はじめは誰でもできないものです．できないことをできるようにするのが，勉強だと私は思います．
-
グラフは楽しいのですが、どうも身の周りで活用することが難しいです．やはり研究でなければ活用は難しいでしょうか？
---
視点に慣れることが重要かもしれません．同じ事象でも，異なる視点から見ることで，違った発見をもたらすことがあります．この授業では，そのような「慣れ」について鍛えていると思って下さい．
- 5/24 (5) マッチング：モデル化
- コメントありがとうございました．
-
ありがとうございました、
---
こちらこそありがとうございました．
-
おもしろかったです
---
すみませんが，尻尾は生えていません．
-
しゃべり方が理系っぽくておもしろい
---
すみませんが，尻尾は生えていません．
-
今回の授業は具体的でおもしろかったです。
---
今回ははじめてモデル化を扱ったので，そのフレーバーを味わってください．
-
今日の話はとても面白かったです。
あいまいな質問になってしまい申し訳無いのですが、ある問題に遭遇したとき、それを数理モデル化して解けるかどうかはやってみないと分からないのでしょうか？
---
やってみないと分からない，と考えてよいと思いますし，もう少し細かく言えば「解ける」ことが何を意味するのかにもよると思います．「解く」ことの意味は人によって違ったり，分野によって違ったりすることもあります．
-
身近なゲームの話でわくわくした。
---
私はわくわくさんではありません．
-
こういうことを考える先駆者はすごいと思います。
---
そうですね．私もそう思います．おそらく，重要なことは，数学という道具を手元に置いておくことだと思います．そうでないと，こういう発想には至りません．私たちは試験に合格することや単位を取得するために勉強しているわけではないことを肝に銘じないといけないと思います．
-
夏が来ましたね
---
まだ梅雨の時期が過ぎていないので，夏が来たとまでは言えないような気はします．
-
最近は暑すぎますね
---
それは同意します．;-)
-
テストがんばります．
---
しっかりと準備をしてきてください．
-
次回の授業は中間の範囲外ですか？
---
授業内でアナウンスした通りです．
-
テストで略字等は使用可能でしょうか．
---
通じると思ったら使って下さい．通じないと思ったら使わないでください．コミュニケーションとはそういうものだと思います．
-
再提出の時、一度出した問題ならば新しい紙に書いて提出しても大丈夫ですか。あるいは
---
大丈夫ですが，そのときには，前に提出した分も付けて下さい．
-
モデル化することで色々な問題が解けるようになることが面白かった。ただそれを言葉で説明するのは難しかった。
---
言葉で説明するのが難しいと感じることができるのは重要だと思います．それだからこそ，日本語の運用能力を上げる努力がいると思います．誰にも当てはまることだと思います．
-
考え方を上手く表現するのが難しい
---
上手く表現できるように，練習をしていきましょう．
-
実際の問題を解決する例を知り、理論に対する理解が進んだように思います。
---
そうですね．一つ気をつけてもらいたいのは，講義で扱っているのは，実際の問題がどう解決されたのか，という過去のはなしであって，皆さんが今後行わなければならないのは，まだ解決されていない問題をどう解決するのか，という未来のはなしであるということです．それを念頭に置いて下さい．
-
「小さい紙」という形容詞＋一般名詞が固有名詞のように扱われ得るのが興味深いと感じた
---
これは意識的にそうしています．実をいうと，この手の紙には「リアクションペーパー」という名前が付けられている場合があります．しかし，そのような名前を使えば使うほど，このような概念は陳腐になる気がしますし，私の意図は曲がって伝わる気がします．そのような名前は気にせずに，学生の個々人が自らのためにうまく活用することが重要だと思っています．そのため，「小さい紙」という，個性のない呼び方をしています．
-
スライドのグラフはどのようなソフトで描画していますか．よろしければおしえてください．
---
Ipeです．
-
頂点数1の木はそれそのものが葉、という認識は間違いですか？
---
正しくないです．木における葉の定義は，次数が1である頂点のことです．頂点数1の木において，頂点の次数は0なので，それは葉ではありません．
-
二部グラフのマッチングの図を書くのは大変です．
---
私も大変だと思います．間違いのないように描いて下さい．
-
結婚定理の証明はなんとなく理解できたが長かったので、ちゃんと証明できるよう練習したい。
---
復習して，冷静に見直すと，それほど難しくないことが分かります．覚える必要はないので，まずは理解して下さい．
-
結婚定理の証明が完全には理解できていないが、その使い方は少し理解できたように感じる。
---
まずは，流れを理解するようにして下さい．
-
今回の問題の方が前回よりも把握しやすかったです．(簡単というわけではありません！！ しかし頑張ります...)
---
簡単であると錯覚してしまうのはよくないので，演習も通して，しっかりと理解して下さい．
-
ボードゲームに関心があるので楽しい授業でした．
---
それは良かったです :-)
-
3次元4目並べに関して，中学校の技術の授業で，下の図のようなおもちゃを作りました。
16本の棒に入れていく。たて・よこ・ななめに4つ同じ色がそろうと勝ち。先手・後手が交互に玉をいれる。
「立体四目並べ」というのですが，このゲームにおいても引き分けになるのでしょうか？
…たてには必ず下からつめて玉を配置しなければならない。
---
まず，講義は3次元4目並べは引き分け，といってしまったのですが，正しくは先手勝ちでした．訂正します．
そして，このゲームですが，これは「Score Four」として知られているものと同じに見えます．このゲームが引き分けで終わるのか，先手が勝つのか，後手が勝つのか，知られていないと思います．先手が必ず有利であるとは簡単に言えない気がします．似たゲームに「Connect Four」というものがありますが，これは先手必勝であると (計算機による探索で) 知られています．
-
4目並べの最適な戦略を発見するのに完全マッチングを用いるのは一見突飛な発想に思えたけど、先手と後手でペアをつくるという観点でとらえると自然に…見えない…
---
慣れてくれば，自然に見えてくると思います．:-)
-
斜めありの3次元5目並べは未解決問題となっていますが、それはまだ研究されてないために未解決なのですか？それともされていてもまだ未解決ですか？
---
私の感覚では，あまり研究されていないように思います．しかし，関連する問題は研究されています．最近でも，例えば，7x7と8x8の盤面における (斜めありの) 5目並べに関する論文がでてます．
-
$d$ 次元 $n$ 目並べの計算量オーダーは $O((n^d)!)$ ...!? 途方もないですね...
---
そうですね．この手の探索をうまく行う方法は『ゲーム情報学』の講義で扱うことになっていると思います．
- 5/17 (4) マッチング：数理
- コメントありがとうございました．次回は残った続きからやります．
-
お疲れ様です
---
こちらこそお疲れ様です．
-
ありがとうございました
---
こちらこそありがとうございました．
-
今回もありがとうございました。
---
こちらこそありがとうございました．
-
ありがとうございました
---
こちらこそありがとうございました．
-
ありがとうございました
---
こちらこそありがとうございました．
-
平成振りですね。
---
そうですね :-)
-
今日暑いですね。
---
これからどんどん暑くなっていくと思います．
-
服装を失敗してしまったので外はとても暑くかんじました。
---
季節の変り目は悩ましいですね．
-
お腹がすきました。
---
昼食をとってからきてください．
-
9連休ありましたが8日間バイトでした。心が休まらないですね。
---
何だか，その気持ちは分かる気がします．
-
令→木ではない
和→木ではない :(
大正→木 :)
---
「令」は森でしょうか．
-
「クレヨンしんちゃん モーレツ！オトナ帝国の逆襲」見ました。平成もいつか懐かしい時代になるのでしょうか。
---
そうだと思います．30年後に2019年を振り返ると，とても昔のことのように思えるでしょうね．
-
他の科目を確認した所、この科目の中間試験が一番早そうです。
---
この科目では私の都合で中間試験をしています．すみません．
-
毎回、目標を箇条書きしてくれるため、それを元にしてノートを取れるので良い。
---
これは意図的に行っています．ぜひ活かして下さい．
-
定義を理解するにも大変になってきた
---
定義を理解しようとする姿勢は重要です．大変でも努めて下さい．
-
間の雑談がおもろいのでもっと聞きたい。
---
時間が足りなくなるので，あまりできません ;-)
-
楽しく聞けました。
---
それはよかったです :-)
-
今回は比較的分かりやすい回だったと思います。
---
ちゃんと理解しているか確認するために，演習問題にも取り組んで下さい．
-
実験たのしいです。
---
それはよかったです．
-
実験で増加道のアルゴリズムを作ったので，それと関連付けるとおもしろいです。
---
増加道については，後の講義でも扱います．
-
実験の増加道法でも似てるようなこと書いてあって少しつながりました。
---
増加道については，後の講義でも扱います．
-
マッチングに関する色々な性質が面白いと感じた。
---
今回は離散最適化についてはじめて扱ったのですが，同じような話題が今後は続いていきます．
-
頂点被覆がマッチングの最大性を保証するなら，逆にマッチングが頂点被覆の最小性を保証する，ということもありそうです．頂点被覆を探す方が簡単そうなので使い道があるかは怪しいですが．
---
ご指摘は正しいです．使い道は大いにあります．
-
$|M| \leq |C|$ を使って最大マッチングの辺数が7本だと分かった場合、同じ7本だけど違う辺の組み合わせというのはありえるのでしょうか？ つまり、最大マッチングの定理はあくまで本数のみを決めるものだという理解でよいのでしょうか．
---
その理解で100％正しいです．最大マッチングが複数存在する場合はあります．
-
Hallの結婚条件が難しかった。
---
そうですね．しっかりと噛みしめて下さい．
-
結婚定理で頭パンクした
---
次回，復習からもう一度やります．
-
結婚条件......。
---
あまりよい名前ではないと，私も思います．
-
結婚定理の証明が理解しきれてないので復習しようと思います
---
次回，続きをやります．
-
専門実験で二部完全マッチングを少し教えてもらいましたが、マッチングの話はさらに奥深いことがわかりました。
---
そうですね．かなり奥深いです．マッチングだけで1年間講義できます．
-
Hallの結婚定理より，$|S| \leq |N_G(S)|$ で，$|S| < |N_G(S)|$ となるイメージがわかないです．すべて $|S| = |N_G(S)|$ になる気がします．
---
例えば，講義スライドの36ページの右側にある二部グラフでは，$S \neq A$ のときに $|S| < |N_G(S)|$ となっています．確認してみて下さい．
-
Hallの結婚定理は二部グラフに対するものであったが，一般の無向グラフに拡張された定理はあるのでしょうか。
---
あります．Tutte (タット) の定理と呼ばれます．この講義では扱いませんが，基本的な定理の1つです．
-
弱双対性はどう "弱い" のでしょうか。弱ではない双対性とは (あれば) どのようなものなのでしょうか。
---
弱いものがあるのは，強いものもあるからです．強いものは「強双対性」と呼ばれます．後の講義で扱います．
-
教室移動の時間を考えると時間割と教室割り当てにもっとよいマッチングがある気がします．
---
ご指摘のとおりだと思います．そういう着眼点が研究になったり，ビジネスになったりします．実際，「時間割作成」は大きな産業で，いろいろな会社がそのためのソフトウェアを販売して，実際に使われています．
-
証明をする際に、どこまで自明としてよいのか悩むことがあります．何か基準みたいなものはありますか？
---
「自明なことは何もない」と思うのがよいです．「〜は自明である」という文は書く必要がないですし，むしろ書かない方がよいです．「自明である」ということばは，論証をごまかしている印象しか与えません．それよりは，1つ1つのステップに論拠を添えることをお薦めします．
証明は書き手と読み手の対話だと思って下さい．読み手が説明を求めたら，書き手は答える必要があるもの，という感覚です．対話をスムーズにするためには，書き手が論拠を明確にしておくとよいです．それが上で書いたお薦めにつながります．
-
簡潔な証明が未だにできません。練習してできるようになる気がしないです。
---
簡潔な証明を行う必要はありません．まずは，正しい証明を行なえるようになって下さい．証明法や証明の書き方は一通りではありません．まずは正しい内容を書くことを目標にしてみて下さい．それを推し進めていくと，簡潔に証明が書けた方が正しい内容を伝えやすくなることが分かってくると思います．その段階まで進めることができれば，この授業で何かを学んだことになると思います．
-
復習問題に挑みましたが、まったくわからず、スライドを観ながら考えて書いてみました。勉強法としては正しいのでしょうか？
---
勉強法は人によって異なるので，正しいかどうかという判断は私がするものではないと思います．それで何か能力が獲得できるかどうかをまず自分で判断してみて下さい．講義としての評価は私が試験で行うことになります．
-
宿題が難しくて大変でした。提出したレポートに記されていないもんだい (解けなかったもの) 新たに再レポに含めて提出することはできますか？
---
すみませんが，これはできません．各回には締切があります．締切後の初提出は見ないことにしています．
-
修正を受けたレポートをその部分だけまとめて提出してみてもらっても構いませんか？ また、一部しか解けなかった演習問題の回を残りも含めて次回に提出してもいいでしょうか？
---
前者は再提出なのでOKです．後者は初提出なので不可です．よろしくお願いします．
-
先生の丸つけのやり方はアメリカ式ですね。コナンで見ました。
---
結果的にそうなっていますね．○という記号は，どこに対して○を付けているのか分かりにくいという欠点があると思います．一方，チェックマークは，そこまではチェックしたという点が分かりやすいと思います．
-
グラフ理論を扱う研究室はどのくらいありますか。
---
これは言うのが難しいです．まず「グラフ理論を扱う」とは何なのかという定義が人によって違います．ちなみに，私の狭い定義では，私の研究室でグラフ理論はやっていません．この講義もグラフ理論の講義ではありません．皆さんがイメージしている「グラフ理論」は私の思う「グラフ理論」と違うかもしれません．
それには目をつぶるとして，自称「グラフ理論を扱う研究室」はいくつかあると思います．研究室公開やOPAL-RING，ラボサーチを使って自分で情報を得るとよいと思います．
- 4/26 (3) 木：数理
- コメントありがとうございました
-
ありがとうございました。
---
こちらこそありがとうございました．
-
ありがとうございました！
---
こちらこそありがとうございました！
-
今回もお疲れ様です。3週間後にまた
---
割と開きますので，しっかりと復習をしておいて下さい．
-
何とかなると思っていたら、案の定 (?) わからなくなりました
---
ですよね ;-)
-
GWたのしみです
---
五月病にならないようにご注意ください．
-
GWの予定はないです。
---
別にそれでよいと思います．無理に何かをしようとする必要はないと思います．
-
ゴールデンウィークはどうしてそう言うのでしょうか？
---
映画業界が言い始めたそうです．
-
今日は目玉焼きとベーコンとトーストを食べて幸せな気分になりました。
---
いいですね．私はカリカリのベーコンよりも，ふっくらとしたベーコンの方が好きです．
-
昨日，五年間くらいずっと気になっていた近所の甘納豆屋さんに行って甘納豆を買いました。とてもおいしいです．
---
甘納豆は本当に納豆なんでしょうか？
-
昼に寿司を食べたらおいしかった上に540円でした。(鯉寿司ってところです)
---
鯉寿司さんはたまに行きます．驚くほど安いですよね．
-
春は来てますか？
---
今日は寒かったですね ;-)
-
きゅうけいがちょうど良い。
---
今回はもう1回休憩がほしいぐらいでした．
-
最近，疲労がなかなか抜けず困っています．
---
何か1つのことをやりすぎると，疲れるような気がします．バランスよくいろいろなことをやるとよいかもしれませんね．
-
授業中にどうしようもなく眠くなってしまうことが、よくあるのですが、そのようなときに眠らないで乗りきるよい方法はありますか？
---
飲み物を少し含むとよいと思います．
-
「フォレスト・ガンプ」を観ました。フォレストのように自分の考えることを信念としてひたむきに取り組めるような人間になりたいです。
---
まさに，トム・ハンクスの全盛期，といった作品ですよね．オープニングはあまり気に入らないのですが，その後はグッとストーリーに引き込まれた記憶があります．
-
Amazon' はともかく ' video、てどういうことなんでしょうね。
---
「prime」にはいろいろな意味がありますね．;-)
-
最初に仮定する (半ば結論ありきで) ので帰納法なんですかね？
---
「『演繹』と『帰納』」という二分において，数学的帰納法は演繹である，ということはよく指摘されます．いわゆる「帰納的推論」と「帰納法」は違うものなので，用語法に注意して下さい．
-
数学的帰納法の間違いの話はとても納得できました．
---
数学的帰納法の証明を正しく書くことは意外と難しいので，正しく数学的帰納法が適用できるようになって下さい．
-
証明の良し悪しがはっきりとは分からなかった。
---
強調しておきますが，スライドの23ページと24ページに書いてある証明はどちらも正しいです．しかし，22ページにあるものは正しくありません．これがはっきりと分かると，数学的帰納法が正しく理解できていることになります．
-
証明が多くて大変
---
そうですね．今回は証明が多かった気がします．もう少し内容を絞った方がよいかもしれません．
-
今回は、けっこう速かったですね。GWで復習がんばります。
---
はい，しっかりと復習をして下さい．
-
証明を理解するのが難しかったです。
---
数学的帰納法による証明は，書く分量が多くなる傾向があると思います．文章として書くことはもちろん重要なのですが，その前に，証明の着想をしっかりと理解して下さい．
-
証明の難しさを改めて感じました。
---
証明するときには文章を書くので，まずは証明として書かれている文章が理解できるようになって下さい．
-
授業をきいて、ギ問に思ったことが授業内で解決したのでGWにもちこさずに済みそうです．ありがとうございます．
---
それはよかったです．:-)
-
具体例を提示してくれる授業スタイルはとても分かりやすくて助かります。
---
例は重視しています．分かりにくい概念も例を通して考えると分かりやすくなるからです．
-
数え上げ論法，最大性論法，数学的帰納法の使い分けが難しいと感じます．
---
使い分けなくてもよいです．使えるものは何でも使おうとしてみる，という姿勢の方が良いと思います．講義でも証明を行っていますが，証明は1通りでしか行えないわけではありません．講義で行っている証明はいくつかある証明の中の1つであると思って下さい．そのような意味でも「模範」的な証明というものは存在しないと思います．現世に存在している証明よりもよい証明というものはいくらでも存在する可能性がありますし，何をよい証明であると見なすのかという価値観も千差万別です．
-
p26の「木G=(V,E)，辺e∈Eに対し，eはGの切断辺である」の証明について、下のようなものも正しいですか？
eの端点をu, vとする．
eがGの切断辺でないと仮定すると，uからvへと至るe以外の道Pが木Gに少なくとも1つ存在する。
しかし，辺eと道Pを合わせたものはGにおいて閉路となり，Gが木であることに矛盾する。
ゆえにeはGの切断辺である．
---
はい，正しいです．
-
今回、多くの命題が、「木の任意の頂点u, vにはただ1つのみ経路が存在する」という命題を用いることで、帰納法が必要なくなる気がしました。
---
その通りだと思います．しかし，「木の任意の頂点u, vにはただ1つのみ経路が存在する」という命題を証明すること (より正確に言えば，その証明を正しく書くこと) は案外難しいです．試してみて下さい．
-
頂点数1のグラフについて、連結の定義 (任意の2頂点を結ぶ道がある) から頂点数1だから，木と言えるのは不思議だと思った．
---
定義を正確に理解する，ということが重要であることの一例ですね．イメージで「木」というものを捉えていると，頂点数1のグラフが木であるかどうか，分からなくなると思います．
-
有向グラフにおける「木」もあるのでしょうか？下のようなものなど？
---
これは有向グラフにおける木と呼んでよいです．描いてもらったものは，「外向木」(がいこうぎ) と呼ばれるものです．すべての弧の向きを逆にすると「内向木」(ないこうぎ) と呼ばれるものになります．
-
別の講義でカット、カットと交差する辺、カットを侵害しない辺集合の概念を扱っていましたが、今日のグラフとネットワークの講義でこれらに関する理解が深まったと感じています。
---
それはよかったです．:-)
-
情報数理工学セミナーの存在をすっかり忘れていたので告知していただいてとても感謝です。
---
次回は5月24日です．よろしくお願いします．
-
次数の合計。合計の次数。
---
どちらも正しい日本語表現だと思いますが，私は「次数の合計」の方を好んで使っていると思います．
-
今回は演習問題が多く，全部終わりませんでした...。続きはGW中にやりたいと思います．
---
はい，連休中に復習をして下さい．
-
今回レポートを忘れてしまったので、次回もってきて次回分も含めて見ていただくことは可能でしょうか．
---
残念ながら，可能ではないです．毎回締切があるので，よろしくお願いします．
-
がんばって考えて解いたつもりでしたが、半分ぐらいしかOKがなかったので自信がもてません……
---
すぐに解けるようになるわけではないと思うので，落胆するほどのことではないと思います．レポートは再提出もできますので，活用して下さい．
-
握手補題そのものの証明をする問題でない場合、握手補題を事実として使っても良いですか？
---
「良い」だと思って下さい．
-
演習問題を解くときにまず自分の論理の力が足りていないと感じることが多いのでそちらの方もきちんと学習していかないといけないなと思った。
---
そうですね．まず，数学というのは文章を論理的に読み書きすることだという認識を持つことが重要だと思います．
-
スケジュールの調整により、この講義を聴講できるようになる見込みがつきました。演習問題を解くことで離散数学の知識と運用力を身につけたいと考えています。
---
それはよかったです．演習問題に取り組むことは重要ですので，積極的に活用して下さい．
-
ありがとうございました．最大性論法を用いる証明に関して、話を聞くと納得できるのですが、自力で書ききる自信がないです...。
---
「証明の着想」が得られているならば，それを文章にすることは，ある程度の技術を必要とします．皆さんは，絵を描いたり，音楽を奏でることについて，発想だけでなく，技術も必要であることに疑いを持たないと思うのですが，文章を書くことについてもそれは同じです．その観点に立てば，数学の証明を書くという行為は論理的な文章を書く技術を磨く一環としてとても役立つものだと思っています．その技術を身につけられるように勉強できるとよいと思います．
-
前回レポートの感想ですが最大 (小) 性論法はとても有用だと分かりました
---
最大性論法は離散数学の証明技法としてよくあるものなので，使えそうなときにはどんどん使ってみて下さい．
-
自分はMI/CSコースの者ではないので、興味はあるものの、実力が追いついてない状況です。復習問題をしっかり解けるレベルにした方が良いか、もしくは、補足問題は解けるようになるべきか、教えて頂きたいです．ちなみに、学部4年のため、聞けるような友達もいません…。
---
復習問題の方が補足問題よりも難しい場合はあります．どの問題でも構いませんが，まず例を考えて，問題が何を言っているのか理解するところから始めて下さい．そして，例から証明の糸口を見つけて，それを文章にする，という流れを体感して下さい．復習問題に対しては，その流れが講義資料に載っている場合も多いので，それを参考にしながら追体験してみて下さい．
-
今週は個人的な提出物を完成させるために何度か徹夜してしまいました。先生は徹夜をしてしまうタイプですか。
---
徹夜は，してしまうというより，気付いたらしていた，という方が多かった気がします．最近はしません．
-
演習問題2.8.3で、一般のk (k≧5) についての反例が出せなかった...
---
一般のkについて考えるときには，何かしらの規則性を見出す必要があると思います．頂点数k+1の閉路を含まないためには，グラフに何を課せばよいのか，ということを考えてみて下さい．
- 4/19 (2) 道と閉路：数理
- コメントありがとうございました．
-
休憩時間があるのはありがたいです。一度に理解しようとがんばり続けると少し頭がパンクしやすいので。
---
私も休憩時間が欲しいので，そのようにしています．;-)
-
休憩があるのは助かります．
---
休憩の過ごし方は自由なので，好きな方法で活用して下さい．
-
資料印刷し忘れました (ToT)
---
次回は忘れずに，よろしくお願いします．:-)
-
花粉症がつらいです．
---
私も花粉症が辛いですが，最近はおさまってきました．
-
教室が暖かくて眠い
---
休憩のときに窓を開けるようにお願いすることがあるかもしれません．その際は，ご協力をお願いします．
-
あたたかくなってきたので、嬉しい
---
そうですね．夏が近づいてきましたね．
-
良い天気
---
サザエさんですね．
-
ありがとうございました．
---
こちらこそありがとうございます．
-
来週もよろしくお願いします
---
こちらこそよろしくお願いします．
-
特にありません
---
何もなくても，このように書いて出していただけるとありがたいです．
-
どうも朝が苦手です
---
早く寝て下さい．
-
がんばる
---
がんばってください．
-
字が大きく、読みやすくて助かりました．
---
前の方の席も空いてますので，ご活用下さい．
-
今日はうどんを食べて幸せな気分になりました。
---
生協や西食堂のうどんのだし (というか塩分) が私には濃いです．もう少し薄い方が好みです．
-
弁当を作ってみたりしているのですが、冷凍食品の方がおいしいことが多々あります。その最たる例がハンバーグなんですが、ハンバーグをひき肉から作ったものを弁当にした場合、時間が経つと肉が固くなって肉団子のようになってしまい、あまりおいしくありません。ですが、市販の冷凍食品は弁当の具材などに用いられることも想定して作られているため、冷めても柔らかくおいしかったです。文明すごさを感じました。
---
冷凍食品はいろいろなことを考えて作られてますからね．私たちが目にしているものは，どれも，最先端技術の結晶なのだということを感じますね．
-
私はお菓子のプレーンはバニラ味とイコールにならないと思いますが，先生はどう思われますか．また，アイスの「プレーン」とは何だと思いますか．
---
もちろん「プレーン≠バニラ味」だと思っています．そもそも「バニラ」というものを知らない人は，「白＝バニラ」と勝手な思い込みをしている可能性もあると思います．私自身はバニラビーンズのつぶつぶが見えるぐらいのバニラアイスクリームが好きなので，はっきりと区別しています．アイスクリームのプレーンというものがあるかどうかわかりませんが，それはバニラを混ぜる前のものだと思います．敢えて言えば「ミルク味」でしょうか．
-
ゴールデンウィークに静岡と北海道に行く予定です．
---
ぜひ楽しんで下さい (^^)
-
「今夜、ロマンス劇場で」を観ました。映像的にも演出的にもきれいな邦画でとても良かったです。
---
ありがとうございます．興味がでてきました．
-
英語のリスニング能力を上げるオススメの方法を教えて下さい。
---
洋画を吹き替え無し・英語字幕で見ます．DVDだとそれができる場合もあります．最近の映画は割と早くしゃべるので，手始めは昔の映画の方がよいかもしれません．
-
最近、ゲームプログラミングが楽しいです。
---
それは素晴らしいです．アシスタントの学生もゲーム作りが好きらしいので，話してみて下さい．
-
締切がすぎた演習問題でも解法が思いつけば、先生に確認しに行ってもよろしいですか？
---
演習の時間などに直接聞いて下さい．レポートは提出していただいても締切を過ぎたものは見ませんので，あしからずご了承ください．
-
MIプログラムの懇親会お疲れ様でした。多くの教員の方と話すことができてとてもよかったです。
---
私も多くの学生と話すことができて，よかったです．
-
先日のMIこんしん会、とても楽しかったです。アイスワインごちそうさまでした．
---
お越しいただきありがとうございました．
-
MI懇親会ありがとうございました．ワイン美味しかったです．
---
こちらこそ，ありがとうございました．
-
すでについていけるか怪しいなと思った
---
そうですね．難しいところもあるので，しっかりと復習して下さい．
-
証明があまり理解できなかったので、復習して理解したい
---
証明できるようになることが達成目標の1つなので，しっかりと復習して下さい．
-
よくりかいできた
---
それはよかったです．分からないところがでてきたら，質問して下さい．
-
分かりやすかったです．
---
それはよかったです．分からないところがでてきたら，質問して下さい．
-
当たり前のことを話しているようで理解に難しい点があった
---
ボーっとしていると突然難しくなったりするので，ご注意ください．
-
色々な単語が出てきたので定義をしっかりと理解したいと思った。
---
そうですね．数学理解の基本は定義と記法の理解ですから，定義をしっかりと理解して下さい．
-
用語の定義が大切だと思いました．
---
用語の定義は大切ですが，覚える必要はありません．忘れたときに調べて思い出せるように整理しておくことが大事です．
-
$\delta(G)$ これの意味はなんでしょうか
---
無向グラフ $G$ の最小次数ですね．第1回講義資料の40ページをご覧ください．
-
$\displaystyle \sum_{\{u,v\}}(\deg_G(u) + \deg_G(v))$ の意味が少しわからなかった。
---
前回の演習問題ですね．すべての辺$\{u,v\}$ に対して $\deg_G(u)+\deg_G(v)$ の和を取ります．辺 $\{u,v\}$ というのは，端点を $u,v$ とする辺のことです．無向グラフの定義 (第1回講義資料26ページと27ページ) をご覧ください．
-
頂点を同一円上に並べて隣り合う頂点同士を反時計回りに弧を結んだ場合は有向閉路といいますか？
---
はい，有向閉路といいます．
-
有向閉路の定義について、「隣り合う頂点同士を時計周りに弧で結ぶ」とありますが，時計周りであることに何か意味はありますか？
---
大きな意味はありません．時計回りでも反時計回りでも構いません．向きが揃っていれば，どちら回りでも構いません．
-
道を"みち"って呼ぶのはたしかにしっくりこないイメージがあります。音読みしない理由が気になります．最初に訓読みで広まったからでしょうか．慣習とはいえ不思議です．
---
私も歴史的経緯は知らないのですが，グラフの用語は訓読みだったり，湯桶読みだったり，重箱読みだったり，標準的な数学の用語法から外れた読み方や訳語の充て方をすることが多い気がします．そのため，この講義では「用語集」を作っています．
-
どうしてもできない場合の対処法を教えてほしいです (演習)
---
質問して下さい．メールでもよいです．そのときに，どこまで考えたのか教えて下さい．考えたことに応じて，こちらからヒントのようなものをお伝えすることもできます．
-
急に難しくなったような気がします．
---
実際，難しくなってると思います．しっかりと復習して下さい．
-
後半の話がむずかしかったです。
---
まずは用語の理解をするところから始めて下さい．
-
最大性論法の理解が難しかった。
---
演習問題に取り組んで，理解を深めて下さい．
-
証明がいまいちわからなかった。
---
証明の着想から実際の証明を書き下すところに移る部分が唐突だった気もします．説明の仕方がよくなかったかもしれません．
-
最大性論法のときの "$v_1$ に隣接する頂点はすべて $P$ の頂点" というところが非自明なように思いました。
---
その通りだと思います．本来は，もう少し文章を書いた方がよいと思います．演習問題として取り組むときに，その部分をぜひ書き下してみて下さい．
-
なぜ無向グラフは頂点数1にならないのでしょう？
---
頂点数1の無向グラフはあります．例えば，第2回講義資料の7ページにある $K_1$ は頂点数1の無向グラフです．
-
証明に「握手補題より〜」という形で $\displaystyle \sum_{v \in V}\deg(v) = \frac{2|E|}{|V|}$ が成り立つものとして扱っても大丈夫ですか？
---
握手補題そのものを示すことが目的でないならば，大丈夫です．
-
定理のイメージはつかめるのですが、それを証明するとなるとどう証明したらいいのかわからなくなってしまいます。
---
そうですね．それを身に付けるために「証明技法」を取り上げています．イメージを文章にまとめるためには，技術が必要です．日本語 (に限らず言語) を用いて表現するためには技術が必要なのです．まず，それを認識して下さい．皆さんは技術者の卵だと思うのですが，技術者の仕事の多くの部分は文章を書くことです．どんな文書を書くことにも，まず作法があり，「作法に則って，伝えるべきことを伝える」という当たり前のことができるようになってほしいのです．
-
感覚的な理解は出来たが、それを証明として書き表すことができない．
---
感覚的な理解ができていれば，それは第1ステップをクリアしていると思います．それをうまく証明として書けるように訓練をしましょう．
-
前回の演習問題はなんとなくできたのですが、文章を書くのが苦手で時間がかかりました。やはりテストで不利でしょうか。
---
不利かどうか，という視点で答えれば，それは不利です．しかし，文章を書くというのは必要な技術なので，身についていないのでしたら，これをよい機会だととらえて，しっかりと身に付けて下さい．
-
1回目の演習問題は解答を書くのに一晩かかりました。無理矢理にでも自分の言葉で書き連ねるのは難しいですね。
---
それが難しいと認識できたことがまず素晴らしいです．慣れれば，もう少し効率よく書けるようになると思います．
-
今まで習ってきた数学の証明と違い、どこまで厳密に書けば良いのか難しい．また、式変形などない分、そもそも証明の糸口を得るのが難しそう．
---
今まで習ってきた数学の証明も同じだと思います．式変形というのは論理的に文章を書いていること (を式という表現を使って行っていること) と同じですし，どこまで厳密に書けば良いのかということの判断は式変形でも難しいです．重要な点は，証明と言うものは文章であって，文章と言うのは自分の考えを読み手に伝えるものである，ということです．それは式変形でも同じです．レポートとして証明を提出していただければ，少なくとも私に皆さんの考えが伝わっているのかどうかは私が指摘できます．そのようにレポートを活用していただければよいと思います．
-
授業終了間際、追加問題2.9-1を解いていました．文だけだとよく分からなかった所でしたがとりあえず例を考えたら一瞬で理解できました。これを文にするのが難しいのでしょうが．．．
---
例を通して考えることは重要ですので，励行して下さい．
-
考察できるようになりたいです．
---
そうですね．今回の授業では，数学的な考察というものの例をお伝えしたつもりです．この視点はとても重要なので，活かしてみて下さい．
-
二部グラフは実験でやったのですが，日常生活において何が二部グラフで表せるか考えるようになりました。
---
素晴らしい心がけですね．二部グラフを使ってモデル化をする例は5月に登場しますので，お楽しみに．
-
先週のコメントに返信しますと、彩色問題を学んだのは「計算理論」です。そちらでは計算量問題やNP完全の側面から学びました。
---
なるほど．ありがとうございます．この講義では，彩色を使って問題解決を行う方法を少し扱うことになります．そこでも『計算理論』の話題に少し触れます．
-
明後日、DB試験を電通大で受けてきます。なんとなく、IPAの資格の中でいえばもっとも離散数学との関連性がつよいように感じます。
---
確かに関連性が強いと思います．データベースは離散数学やアルゴリズムの宝庫です．そういう視点でデータベースに関する勉強をしてみると，違った一面が見えてくるかもしれませんね．
- 4/12 (1) グラフの定義と次数：数理
- コメントありがとうございました．いただいたコメントとその回答は以下のように掲載されます．
-
よろしくお願いします．
---
よろしくお願いします．
-
よろしくおねがいします
---
よろしくお願いします．
-
これからよろしくお願いします。
---
よろしくお願いします．
-
今年度もよろしくおねがいします (再履)
---
よろしくお願いします．
-
半年かんよろしくおねがいします。がんばります。
---
よろしくお願いします．
-
去年に引き続きよろしくお願いします
---
よろしくお願いします．
-
今年もよろしくお願いします。
---
よろしくお願いします．
-
半年間よろしくお願します
---
よろしくお願いします．
-
面白そうな内容でしたので，受講します。よろしくお願いします。
---
よろしくお願いします．
-
単位取れるように頑張ります。
---
はい，よろしくお願いします．
-
難しそうですが、おもしろそうです
---
実際，難しそうでおもしろそうだと思います．よろしくお願いします．
-
来週もよろしくお願いします。
---
こちらこそよろしくお願いします．
-
今日は曇ですね。
---
そうですね，夜はかなり寒かったです．
-
くもり時々晴れ
---
これは天気予報ですね :-)
-
今日は寒いですね
---
はやく暖かくなってほしいです．
-
4月なのに寒いですね...。
---
そうですね．はやく暖かくなってもらいたいです．
-
おいしいご飯の炊き方を教えてください
---
最近の炊飯ジャーの機能はとても豊富なので，それを使うだけでおいしいご飯が炊けるそうです．
-
お昼を食べ過ぎると少し眠く集中できないですね
---
朝食をしっかりとって，昼食を少なめにするとよいと思います．
-
生まれてはじめて弁当を作りました。ごはんにウィンナーと卵焼きを入れただけですが、とてもおいしかったです。
---
すばらしいです．同じものばかりだと飽きてしまうので，バリエーションが付けられるとよいですね．
-
ねむいれす．
---
「ねむいです」なのか，「眠いless」で実は眠くないのか，どちらか分かりませんでした．
-
おつかれ様です．
---
ありがとうございます．実際，疲れています．
-
年とって，腰が痛くなってきた．正直，辛い
---
わかります ;-)
-
滑舌が悪く早口で、私も耳が良い方ではないのでうまく聞きとれません。一言一言はっきり話していただければ幸いです。よろしくおねがいします。
---
ありがとうございます．できる限り注意します．なお，ヒップホップを聴くと，聞きとりやすくなるそうです．
-
もっと講義を聴きたかったのですが...途中で失礼します。
---
途中退室する場合は，他の学生に迷惑とならないよう，ご配慮ください．
-
今のオレは，最高にやる気に満ちている。
---
ぜひ，演習もやってください．
-
$\mathcal{A}\mathcal{B}\mathcal{C}$
---
筆記体やギリシア文字の書き取りは少し練習しておくとよいと思います．きれいに書けるようになります．
-
今回の授業は概ね全ての範囲理解できた。
---
油断しているとすぐに分からなくなるので，ご注意ください．
-
とても分かりやすかったです
---
油断しているとすぐに分からなくなるので，ご注意ください．
-
すごく分かりやすかったです。
---
油断しているとすぐに分からなくなるので，ご注意ください．
-
説明が分かりやすかったです。
---
分からないときは，遠慮なく質問して下さい．お願いします．
-
用語や表記法について詳しく説明してくれていたので分かりやすかったです
---
用語や表記が正しく使えることは達成目標の1つなので，気をつけるようにしています．
-
ロボ子さんかわいい
---
おめでとうございます．
-
演習問題出していただけるのありがたいです！
---
演習を行うことは大事なので，しっかりと取り組んでみて下さい．
-
演習する時間があるのが良い。
---
演習の時間は質問の時間でもあるので，どしどし質問をして下さい．
-
レポートに書く答案の順番は自由でしょうか？
---
はい，順序は問いません．
-
レポートはルーズリーフでもよいですか？
---
はい，よいです．
-
レポートはどのように提出、受取すれば良いのでしょうか？
---
講義終了時に提出して下さい．提出した次の回の講義で返却します．
-
個人的に貴研究室への志望を考えているのですが、バイトの都合上、どうしてもグラフとネットワークをとれなくなる公算が大きいです。そこで、2点質問があるのですが (1) このことは貴研究室への配属時に不利になるでしょうか？ (2) この講義を取らないことになった際に演習問題の採点だけお願いすることは可能でしょうか？
---
ありがとうございます．2つ質問があるので，分けて答えます．
(1) 卒業研究の配属について何も決まっていませんが，昨年度の状況はこちらからご覧いただけます．参考になるかどうかわかりませんが．
(2) まず，演習問題は誰に対しても採点されないので，その点は誤解のないようにお願いします．レポートは講義終了時に提出することになるので，講義に出席せずにレポートを提出することは難しいと思いますし，私から返却することも難しくなります． -
演習問題は、問題へのアプローチ (結論の導き方) が思いつかなかった際に、考え方だけ書くことにしてもよろしいですか？
---
はい．どう考えて，どこまでできたのか，書いていただければよいです．
-
期末の範囲は中間から最後まで，最初から最後までのどちらになりますか？
---
それは決まっていません．試験が近づいたらお知らせします．
-
期末試験は講義の全範囲から出ますか。それとも中間試験の後の範囲だけから出ますか。
---
それは決まっていません．試験が近づいたらお知らせします．
-
試験は証明問題が多いんですか？
---
何を証明問題と呼ぶのか分かりませんが，演習問題として取り組んでいただいている問題のようなものが試験で問われます．
-
試験の説明に「全問に解答する」とありますが，どれか1つでも解答しなかったら試験の点は0ですか？
---
0ではありません．解答を書いていないものは，白紙解答であると見なされるので，解答したことになり，「どれか1つでも解答しない」という状況は生まれないことになります．
-
テストの平均は50以下になるようにしているのですか？
---
「している」の解釈は2通り考えられますが，まず1つ目．試験の採点後に調整を行い，平均点が50以下になるような措置は施しません．そもそも調整をするということはしません．そのため，例えば，受講者全員が試験で90点以上をとれば，全員秀です．
次に2つ目の解釈．試験問題を作成する際に平均点が50以下になるようにしているかどうか，という観点です．これの回答は「そうしない」です．試験問題はシラバスに書いてある (あるいは第1回の講義で説明した) 達成目標が達成できているかどうかを主眼に置いて作成します．そして，半分できれば合格 (つまり120点満点中，半分の60点がとれれば合格) となります．これもシラバスに書いてある評価基準のとおりです．
もう1つ注意点ですが，この講義の過去がどうであったか，ということは気にしすぎないでください．私は今年度の状況に合わせてこの講義を行います．その意味で，毎年進め方や内容は変わります．いままでどのように行われていたのかを気にしすぎると，それまでとの違いにとまどう可能性があります．
-
なんとなく、証明を説明できるけど、数式を用いた証明が苦手です。
---
数式で証明する必要はなく，ことばでうまく説明ができれば十分です．ただし，時と場合によっては，数式を用いる方が説明が簡素になることもあります．うまく使い分けができるとよいと思います．
-
早くトランプマジックの種が知りたいです
---
とりあえず，まずは自分で試してみて，うまくいくことを感じて下さい．
-
過去に他の科目で彩色問題を学んだことがありましたがなかなか難しかったのでこの講義も気を抜かないよう頑張ります。
---
どの科目だったか教えていただくことはできますか？ 私も興味があります．
-
数え上げによる証明とはどのような証明のことですか？
---
すみません，ちゃんと説明していなかったような気がします．等式や不等式を証明する際，何かを数えることで証明するという手法です．今回の場合は，握手補題の証明で石の総数を数えていたのがそれに該当します．
-
握手補題の「握手」とは何ですか
---
無向グラフの頂点を「人」だと思って，2人が握手をしたとき，その2人を表す頂点同士を辺で結ぶ，という方法で無向グラフを作ったと想像して下さい．このとき，辺の総数は握手をした回数の合計になります．握手補題は，これの2倍が，各人が握手した回数 (これは対応する頂点の次数と等しい) の総和となることを意味しています．この解釈から，「握手補題」と呼ばれます．
-
握手補題の証明における $M \in \mathbb{R}^{V\times E}$ の $\mathbb{R}^{V \times E}$ とはなんの行列ですか？
---
すみません，これもちゃんと説明していなかったです．行の添字集合が $V$ で，列の添字集合が $E$ である実行列をすべて集めた集合を $\mathbb{R}^{V \times E}$ と書きます．つまり，$M \in \mathbb{R}^{V\times E}$ と書くと，行列 $M$ の行添字集合は $V$ であり，列添字集合は $E$ であることになります．
-
接続行列において、$\mathbb{R}^{V\times E}$ という書き方がよく分からなかったです。$\mathbb{R}^{|V| \times |E|}$，もしくは $\mathbb{R}^{|V\times E|}$ とは違うものなのですか？ ($\mathbb{R}^{n}$ の右肩に集合が来ることにピンときません…)
---
前の質問の回答の続きになります．例えば，$\mathbb{R}^{3 \times 2}$ と書くと，これは3行2列の実行列をすべて集めた集合になりますが，その行添字は1, 2, 3であり，列添字は1, 2であることを普通の数学では仮定します．しかし，そうではなく，行添字や列添字に自由な記号を使いたい場合には，$\mathbb{R}^{V \times E}$ のような書き方をします．これは行列だけでなく，ベクトルでも使えて，$\mathbb{R}^{3}$ とすれば，3次元実ベクトルをすべて集めた集合ですが，$\mathbb{R}^{V}$ とすると，添字集合を$V$ とするベクトルをすべて集めた集合になります．
プログラミングに慣れている人向けに説明すれば，$\mathbb{R}^{3}$ のような書き方は配列に対応していて，$\mathbb{R}^{V}$ のような書き方は Python なら辞書，Ruby ならハッシュ，C++ ならmap のような機能をもったものに対応していると思って下さい．
-
$M \in \mathbb{R}^{V\times E}$ など $V \times E$ のところが集合なのにまだ慣れていない
---
使える記法なので，使い慣れると便利さが分かるようになると思います．
-
入次数がdeg-で出次数がdeg+なのは少し直感に反している気がします．(入ってきて何かが増えそうなので入次数は+では...？と思ってしまいます．)
---
確かに分かりにくいと思います．覚えなくてもよいので，忘れたり，混乱したときに，調べて思い出せるようにして下さい．
どうしても覚えたかったら，乾電池を想像するとよいかもしれません．乾電池を有向グラフの頂点だと思って，プラス極から電流は出ていき，マイナス極から電流は入ってきます．
-
昨日「グリーンブック」を観ました。アカデミー賞を取っただけあって面白かったです。
---
観たいですが，映画館は苦手なので，DVDになるのを待ちます．
試験・成績
- 中間試験と期末試験により，成績の評価を行います．
- 成績 = min{100, 中間試験の素点+期末試験の素点} (小数点以下切り捨て)
- 得点分布 (中間試験と期末試験の一方でも受験した人に限る)
- 受講者数 (履修登録者数相当) は61で，
90点以上 (S) が9人 (約15%)，
90点未満80点以上 (A) が4人 (約7%)，
80点未満70点以上 (B) が10人 (約16%)，
70点未満60点以上 (C) が8人 (約13%)，
60点未満 (D) が30人 (約49%) です．
- 中間試験と期末試験の一方でも受験した人の総数は54で，
90点以上 (S) が9人 (約17%)，
90点未満80点以上 (A) が4人 (約7%)，
80点未満70点以上 (B) が10人 (約19%)，
70点未満60点以上 (C) が8人 (約15%)，
60点未満 (D) が23人 (約43%) です．
- 期末試験
- 日程：8月9日(金) 第3時限 (13:00-14:30)
- 教室：西2-101 (いつもの教室)
- 持ち込み：A4用紙1枚分 (裏表自筆書き込み) のみ可
- 出題範囲：第6回講義の最初から第13回講義の最後まで
- 形式：
- 演習問題と同じ形式の問題を4題出題する
- その中の2題は演習問題として提示されたものと同一である
(ただし，「発展」として提示された演習問題は出題されない)
- 配点：1題15点満点，計60点満点 (0.5点刻み)
- 試験問題
- 得点分布
- 受験した人の数は39，平均点は34.5 (60点満点)．
45点以上 (S相当) が9人 (約23％)，
45点未満40点以上 (A相当) が6人 (約15％)，
40点未満35点以上 (B相当) が7人 (約18％)，
35点未満30点以上 (C相当) が5人 (約13％)，
30点未満 (D相当) が12人 (約31％) です．
- 得点掲示 (辞書順に並べています)
| 43298 | 46 |
| 815883 | 34.5 |
| 021CD | 36 |
| asddf | 33 |
| CRBYS | 42.5 |
| DpNG2No | 28 |
| fakeru | 25 |
| hb64 | 60 |
| HY5-3 | 43 |
| loser | 35 |
| MAGRT-2 | 37 |
| MWMWM | 1 |
| qoxop | 42 |
| Ranch | 3 |
| RBASS | 34.5 |
| sauce | 45 |
| synerr | 24 |
| Talisman | 29 |
| tirol | 18 |
| vnuius | 36 |
| wa726 | 43.5 |
| Wmb2u | 46.5 |
| X1115 | 58 |
| zabesu | 52 |
| μ'sic | 26 |
| 井沢ジョー | 36.5 |
| 観用植物君 | 39.5 |
| くろくしろ | 17 |
| しょうゆ | 22 |
| ペヤングソース焼 | 42 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評
- 総評：しっかりと勉強した人とそうでない人の差が出たように感じました．何となく何かを書けば合格する，とか，そういう考え方は今後捨てた方がよいと思います．また，字や絵は丁寧に書いて下さい．ある答案で，3文字で書かれているように見えたある部分が読み取れず，そこを解読しようと試みるだけで15分費やしました．結局，解読できなかったので，その部分は0点にしました．このようなことは，書き手にとっても読み手にとっても不幸です．気をつけて下さい．以下，問題ごとの講評です．
- 問題1：流れとカットの性質に関する問題．演習問題と同じ問題．
平均点は5.21．
ほとんどできていませんでした．4問中，最もできていない問いでした．
演習問題と同じ問題なので，準備してほしかったです．
式ではなく，ことばで説明しようとしている答案は，たいてい間違っていました．(正しければ，ことばで説明してもよいのですが，ことばで説明しようとするときに正しいものは少なかった，という意味です．) また，関係のないことを書いても，点はありません．
- 問題2：次数制約付き向き付けに関する問題．演習問題にない問題．
平均点は9.19．
できている人とできていない人の差がおおきな問題でした．できている人は何も問題なくできています．できていない人は，基本的な理解ができていないか，ただ単に勉強していないか，のいずれかだと思います．s,tカットの容量というものが何であるのか理解できていない答案がいくつかありました．
- 問題3：彩色に関する問題．演習問題にない問題．
平均点は12.85．よくできていました．
グラフの描き間違いには注意して下さい．描き間違いがある場合には，軽微な減点としています．
- 問題4：凸多面体と平面的グラフに関する問題．演習問題と同じ問題．
平均点は7.69．
できている人とできていない人の差がおおきな問題でした．「すべて挙げよ」と問われているので，すべて挙げていない答案や挙げたものがすべてであることを確認していない答案は減点されています．
- 中間試験
- 日程：6月7日(金) 第3時限 (13:00-14:30)
- 教室：西2-101 (いつもの教室)
- 持ち込み：A4用紙1枚分 (裏表自筆書き込み) のみ可
- 出題範囲：第1回講義の最初から第5回講義の最後まで
- 形式：
- 演習問題と同じ形式の問題を4題出題する
- その中の2題は演習問題として提示されたものと同一である
(ただし，「発展」として提示された演習問題は出題されない)
- 配点：1題15点満点，計60点満点 (0.5点刻み)
- 試験問題
- 得点分布
- 受験した人の数は54，平均点は34.2 (60点満点)．
45点以上 (S相当) が10人 (約19％)，
45点未満40点以上 (A相当) が8人 (約15％)，
40点未満35点以上 (B相当) が8人 (約15％)，
35点未満30点以上 (C相当) が10人 (約19％)，
30点未満 (D相当) が18人 (約33％) です．
- 得点掲示 (辞書順に並べています)
| +refle+ | 41 |
| 24歳学生 | 48 |
| 68530 | 28 |
| 781CD | 45 |
| 7ザップグラネト | 40 |
| 8225681. | 30 |
| A7cQ5 | 41 |
| ABABb | 25 |
| acdzb | 20 |
| aifzg | 38.5 |
| aimrf | 30 |
| AlIcE | 31 |
| asddf | 34.5 |
| BKWUS | 23 |
| blank | 40 |
| CRBYS | 31 |
| czfbh | 9 |
| DpNG2no | 24 |
| ears | 33 |
| eatjh | 34 |
| GaOTx | 22 |
| GTMIL | 39 |
| hui4 | 50 |
| jinguj | 33 |
| kaniX | 36 |
| kanww | 37 |
| M4641 | 45 |
| MAGRT | 42 |
| MDpNG | 18 |
| Mebius01 | 24 |
| meiur | 17 |
| MNHY3 | 56 |
| Muri-Syoumei | 38 |
| MWMWM | 37.5 |
| poe^q^ | 35 |
| pwsat | 28.5 |
| qoxop | 48 |
| radar | 28 |
| RBASS | 44 |
| re53 | 42 |
| rokah | 60 |
| SAIRI | 26 |
| skcpj | 12 |
| syamu | 46 |
| tabami | 54 |
| Tmrwk | 25 |
| triosk | 16 |
| xdzjl | 30 |
| xpfh0 | 24 |
| zabesu | 43 |
| あけいうち | 30 |
| 徳川ゆめの | 55 |
| にゃんぱす | 36 |
| むA8魚D | 24 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評
- 総評：得点分布としては，割ときれいな形になりました．演習問題と同じ問題はもっとできていて欲しいと思いましたが，問題2も割とできていたように思いました．
- 問題1：タイル貼りに関する問題．演習問題と同じ問題．
平均点は12.9．
よくできていました．頂点部分集合を選ぶとき，それは二部グラフの片側から選ばないといけないことに注意して下さい．
- 問題2：木に関する問題．演習問題にない問題．
平均点は9.19．
小問1は割とできていましたが，小問2のできは大きく分かれました．
小問1は大きく分けて2通りの解答が見受けられましたが，数学的帰納法で小問1を解くと，小問2に対して手の付けようがなかったかもしれません．数学的帰納法の場合，m=0から始まることに注意して下さい．一方，小問1で握手補題を用いた解答をしていると，小問2もすんなり解答できると思います．
- 問題3：閉路に関する問題．演習問題と同じ問題．
平均点は9.44．
これは演習問題と同じ問題なので，もっとできていてほしかったです．
小問1が全くできていない人は，おそらく講義内容を理解していないと思います．小問2は任意のkに対して反例を作らなければなりません．特定のk (例えば，k=2のとき) だけの反例では，問いに答えたことになりません．
- 問題4：切断辺に関する問題．演習問題にない問題．
平均点は2.65．
これはほとんどできていませんでした．
たくさん書いてあっても，的外れである場合，1点もありません．
例えば，最小次数が2以上であるから，すべての辺が閉路に含まれる，と書いてある答案はたくさんありましたが，これはシンプルに正しくありません．(反例があります．)
公式シラバス
スケジュール (予定)
- 4/12 (1) グラフの定義と次数：数理
- 4/19 (2) 道と閉路：数理
- 4/26 (3) 木：数理
- 5/3 休み (憲法記念日)
- 5/10 休講 (海外出張)
- 5/17 (4) マッチング：数理
- 5/24 (5) マッチング：モデル化
- 5/31 (6) 最大流：数理
- 6/7 中間試験
- 6/14 (7) 最大流：モデル化 (割当)
- 6/21 (8) 最大流：モデル化 (カットの視点)
- 6/28 (9) 連結性：数理とモデル化
- 7/5 (10) 彩色：数理
- 7/12 (11) 彩色：モデル化
- 7/19 (12) 平面グラフ：数理
- 7/26 (13) 平面グラフ：モデル化
- 8/2 授業等調整日 (授業を行わない)
- 8/9 期末試験
過去の講義
注意：内容や説明法は毎年少しずつ変わっています
過去の試験問題
注意：内容や説明法，試験範囲は毎年変化しています．
[Teaching Top]
[Top]
okamotoy@uec.ac.jp
