グラフとネットワーク
電気通信大学情報理工学部情報・通信工学科
2015年度前学期
月曜2限 (10:40-12:10)
教室：西2-101
岡本 吉央
ショートカット：講義資料 | コメント | 試験・成績 | 公式シラバス | 履修上の注意 | スケジュール | 過去の講義
講義資料
- 8/3 (14) ラムゼー理論
- 7/27 (13) 平面グラフ：モデル化
- 7/13 (12) 平面グラフ：数理
- 7/6 (11) 彩色：モデル化
- 6/29 (10) 彩色：数理
- 6/22 (9) 全域木：数理とモデル化
- 6/15 (8) 最大流：モデル化 (2)
- 6/1 (7) 最大流：モデル化 (1)
- 5/25 (6) 最大流：数理
- 5/18 (5) マッチング：モデル化
- 5/11 (4) マッチング：数理
- 4/27 (3) 木：数理
- 4/20 (2) 道と閉路：数理
- 4/13 (1) グラフの定義と次数：数理
コメント
- 8/3 (14) ラムゼー理論
- コメントありがとうございます．1学期間お付き合いいただきありがとうございました．
- 講義の内容から
-
ラムゼー数はKNの2分割でしたが，3分割や4分割のときを考えるものは研究されているのでしょうか？ R(k,l,m)とかR(k,l,m,n)とかです。また3分割だったら，Simやクリークゲームも3人対戦になる？
---
そのようなものも研究されています．その場合のゲームも3人対戦や4人対戦になりますが，ゲームとしての側面はあまり研究されていません．3人以上が登場するゲームの解析は途端に難しくなるのです．
-
あと一手で勝利はチェスだとチェックですね。
---
その通りですね．将棋だと王手，ということですね．
- 半年間のまとめ
-
半年間ありがとうございました。
---
こちらこそありがとうございました．
-
4ヵ月間ありがとうございました．
---
こちらこそありがとうございました．
-
1学期間，ありがとうございました．テスト頑張ります．
---
こちらこそありがとうございました．試験はしっかりと準備してきてください．
-
これまでありがとうございました。
---
今後も機会があるかもしれませんので，またよろしくお願いします．
-
3年前期でいちばん一番たのしみだった講義で，一番たのしかった講義でした。演習問題もたくさん添削していただき，ありがとうございました！
---
こちらこそありがとうございました．
-
シケン勉強がんばります
---
勉強だけでなく，試験も頑張って下さい．
-
キマツガンバリマス...
---
答案をすべてカタカナで書くのは止して下さい ;-)
-
バナナはお好きですか？ (テストがんばります)
---
特に「好きだ」ということではないですが，食べることはできます．
-
試験勉強しなきゃ…
---
はい，持ち込むことができますし，それを想定して問題を作っているので，しっかりと準備をしてきてください．
-
楽しい授業を半年間ありがとうございました．
---
こちらこそありがとうございます．
-
ややこしかったですが，面白かったです。
---
確かにややこしい部分はあったと思いますが，しっかりと復習をして，理解して下さい．
-
グラフを使った様々な考え方を学ぶことができました．今後に生かしていこうと思います．
---
はい，今後に生かせるよう，よろしくお願いします．
- 7/27 (13) 平面グラフ：モデル化
- コメントありがとうございます．期末試験の範囲は今回の内容までです．しっかりと準備をしてきてください．
- 順不同です．
-
実験第2でrubyを使うと書いてあるのを見ました．難しそうです．
---
どんなプログラミング言語を使うのか，ということは本質的ではありませんし，難しくありません．皆さんは既にプログラミングに関する素養を持っているので，そこから，今まで使ったことのない言語を用いることは難しくありません．今後皆さんが必要とするプログラミング言語 (に限らず，自然言語も含めて言語) は何であるか分かりません．必要となったときに素早く勉強できるような基礎勉強を今はしているのだと思って下さい．
-
地球を3Dモデルのように平面グラフで描写して、ちょうどよいところで開いてつぶしたら地図ができる…！？
---
その通りです．地図の作り方は古くから大きな研究分野で，「地図学」として現在でも盛んに研究されています．
-
地図を見て思い出しましたが、都道府県レベルでも飛び地があるらしく、埼玉県新座市の中に東京都練馬区の区画があるそうです。ただ、日本の場合は隣接しあっているところにしかなさそうなので彩色問題には関係なさそうです。
---
講義では意識的に触れないようにしていましたが，飛び地の存在は地図の彩色を難しくしますね．ご指摘ありがとうございます．
-
3つ以上の面が同じ点で1次元的に接することはありますか？
---
安心して下さい，平面上でそれはないですから．
-
平面的グラフが6彩色可能は証明があっという間で驚きました。
---
6彩色については証明が簡単なのですが，6を4にしようとするところで大きな努力が必要となるわけですね．
-
美術館の監視について、定点カメラをイメージして聞いていたのですが、例えばドローンのような移動カメラを扱う例はあるのでしょうか。視界や移動コストなどの要素も加えると面白そうな気がしました。
---
あります．ロボットによる監視やモニタリングは重要なテーマです．また，その移動を前もって決めておくのか，環境の変化に応じて移動も変化させていくのか，その変化も中央制御的に行うのか自律分散的に行うのか，など，いろいろなバラエティーがあります．また，視界の考慮はセンサによるモニタリングをモデル化するときにも出てきます．
-
今回の美術館定理や四色定理のように，よく使う定理すべてに名前が付いていると調べやすいのですが，"|E| ≦ 3|V|-6 の定理" や "外平面的グラフが3彩色可能" とかには名前はないものでしょうか。
---
その2つについては知らないです．もしかしたらあるのかもしれませんが，聞いたことはありません．
-
この講義は説明を聞いているときは、わかりやすく理解した気になって楽しいが実際に演習問題をやると全く解けなくて悲しい。
---
それが重要なポイントだと思います．わかった気になるのは簡単ですし，分かった気になることに重点を置く授業の構成もできると思いますが，それでは目的が達成できないので，演習問題を通してしっかりと理解していただきたいのです．演習問題は一人でやらず，他の人と一緒にやるか，レポートや講義の後半の時間を活かして，質問をしながらやっていく，というスタイルが重要です．もう講義は終わってしまうのですが，そういうものだったのだと思って下さい．
-
12.6の説明ができない^^;
---
説明ができるようなグラフを構成することがポイントです．説明のしやすさを考えると，nがちょっと大きい (例えば，50ぐらい) の場合を考えた方がよいかもしれません．
-
8/3にレポートをたくさん出したいです。なにとぞ……
---
はい，お待ちしております．
-
期末試験が近いので，たまっている再提出の問題がんばります。
---
はい，お待ちしております．
-
レポートの締切りとテストラッシュが怖いです．
---
おそらく，パトラッシュも怒ると怖いです．
-
つらい
---
ストレッチしましょう ;-)
-
さいきん いそがしいよね
---
そうだよね
-
うんざりするような暑さですが，先生は泳ぐならどこへ行きたいですか？海？プール？それとも……
---
それとも，の後に何が続くのか気になりますが，何年か前に死海にいって泳いでいたら死にそうになったので，海はもういいです ;-)
-
夏っぽい服装ですね
---
冬には冬っぽい服装になります．春と秋が苦手です．
-
暑いですね…早く夏休みになりたいです。
---
夏まゆみになりたいのか思って，一瞬驚きました．(^^;
-
半年間ありがとうございました。来週はテスト勉強の進み具合など見て、行けそうであれば参加します。
---
こちらこそありがとうございました．授業も出席をとるものではありませんし，自由に来ていただければ問題ありません．
-
ここで学んだことを，日常生活のふとした疑問にも生かしていこうと思いました．
---
はい，是非励行して下さい．初回の講義でも扱いましたが，現実世界のいろいろなものがネットワークとしてモデル化できます．そのような視点を是非大事にして下さい．
- 7/13 (12) 平面グラフ：数理
- コメントありがとうございます．来週は祝日のため講義はありません．
-
グラフを描き方でとらえるのは新しい考え方で難しいです。
---
いままでの講義の内容とは味わいが違ったと思います．離散数学にはいろいろな側面があるので，難しくもありますが，それだけ深みがあるわけです．ぜひ楽しんで下さい．
-
今回の授業の「オイラーの公式」のオイラーさんと，複素数の方で出てくる「オイラーの公式」のオイラーさんは同一人物なのでしょうか？ (複素数のは勘違いでしたらすいません)
---
おいらはオイラー．すみません．気を取り直して，同一人物です．
-
$e^{i\theta}$
---
いいの，あいしーた，じょぅ．
-
グラフGが球面上で辺の交差なく描画可能 ⇔ Gは平面的グラフ (?)
---
正しいです．いわゆる「ステレオ投影」を考えれば証明できます．
-
問題が12回目なのに11になってました。
---
ありがとうございます．修正しました．
-
グラフとネットワーク(12)の演習問題のナンバリングが12ではなく11になっているような……。
---
ありがとうございます．修正しました．
-
11.7のヒントなどあれば下さい．
---
番号を修正した後の12.7のことだと解釈します．講義スライド27ページのような数え上げを行って下さい．そのとき，「各行における1の数が3以上」ではなく，どうなるか，考えて下さい．
-
演習問題を考えていくのが段々と難しくなってきました．しっかり復習しておきたいです．
---
そうですね．しっかりと復習をして下さい．
-
凸多面体の定義が知りたいです。凸多面体でない多面体はどのようなものがあるのでしょうか．
---
ややこしいので3次元の場合だけ考えて，直感的な定義をします．有限個の多角形の辺同士を隙間のないように貼り合わせてできる図形の中で，貼り合わせた場所には2つの多角形しか現れていないものが多面体です．それにへこんだ部分が無い場合，凸多面体と呼ばれます．正確な定義をしようとするとかなり難しくなります．wikipediaのページに詳しい説明と例があります．
-
三年になったばかりと思っていたら、もうこんな時期ですね 期末の勉強頑張ります．
---
光陰矢の如し，ですね．試験の準備も怠らず進めて下さい．
-
夏休み楽しみ^^
---
そのまえに期末試験があるので，しっかりと準備をして下さい．
-
前期の終わりが見えてきました．
---
そうですね．実験第二のガイダンスがあるので，そのまま後期につながっていくということを感じて下さい．
-
梅雨雲も消え、鮮やかな木陰が映る時期になりました。できるなら外出したい所です。
---
そうですね．連休があるので活かして下さい ;-)
-
急に暑くなって，とても眠たかったです。すみません。
---
台風も近づいているので注意しないといけませんね．
-
いきなり暑くなったなあ．
---
体調管理に注意して下さい．
-
おいしさランキング
ピーチティー＞アップルティー＞レモンティー＞ストレートティー＞＞＞＞＞＞＞ミルクティー
ピーチこそ至高
---
ありがとうございます．今度試します．生協ですよね？
-
離散数学では岡本先生のDJ姿見られると聞きました。ずるいです！
---
ずるくないです！ 講義のコメントにしたがってやっているだけです．
-
最近，江戸川乱歩のアニメをやっていて，生協でも特設コーナを設けるなどプチブームがおこっていますが，先生は江戸川乱歩をお読みになったことがございますか？
---
探偵小説は読んだことないと思います．読んだことがあるという記憶がありません．
- 7/6 (11) 彩色：モデル化
- コメントありがとうございます．期末試験の日程について，都合が悪い人は私まで連絡を下さい．詳細はこのページの一番上にあります．
- 天候について
-
5, 6日くらい連続で雨で太陽の光が恋しいです．
---
まさに，Rainy days and Mondays always get me downですね．
-
雨が続いてイヤになってきます…。
---
尾形大作ですね．
-
梅雨ヤバイ！！
---
これはGLAYでしょうか．
-
そろそろ梅雨明けですね．
---
そうですか？ 関東の梅雨明け，平年では7月21日だそうです．
- 講義について
-
単位円を見て台風が3つ発生したのを思い出しました。
---
講義について，かと思ったら，天候について，でしたね ;-)
-
円グラフときくと下を思い浮かべる
---
英語ではpie chartと呼ぶことが普通ですね．いわゆる棒グラフはbar chartで，折れ線グラフはline chartです．グラフときいて上のようなものを思い浮かべるのは日本人だけかもしれません．
-
この図を見て「カビみたいだな〜」と思いました。すみません。
---
たしかにそう見えますね ;-)
-
独語でKrieg (クリーク) というのがあってこっちが語源だと思っていました。意味は"戦争"で，なんとなく色どうしが戦ってるようにみえるし，それっぽいです。
---
英語のcliqueなんですね．数学においてドイツ語をそのままカタカナにすることはあまりないと思います．例もおもいつきません．
-
色数は「いろかず」と読むんですね。「しきすう」だと思ってました。
---
まず「いろかず」という読みはあるようです (デジタル大辞泉には載っています)．そして，この分野では「色」を音読みでは「しき」とは読まず「しょく」と読むことになっています．ちなみに「しき」は呉音で，「しょく」は漢音のようです．それで，色数を「しょくすう」と読むかといわれると，私は聞いたことがありません．
-
完全二部グラフが区間グラフであることはない，ということでしょうか
ここまで書いて反例を見つけてしまいました…。
$A=\emptyset \cup B=\emptyset$ のとき
または
「$|A|=1 \cap |B|=1,2$ または $|B|=1 \cap |A|=1,2$」のとき，区間グラフになりました…。
それ以外では反例はないですよね…？
---
「$A=\emptyset \cup B=\emptyset$」ではなくて「$A=\emptyset \lor B=\emptyset$」と書かなくてはいけませんね．同じように「$|A|=1\cap |B|=1,2$」も「$|A|=1 \land |B|=1,2$」でなくてはなりません．
それはおいておいて，$|A|=1$ の場合は $|B|$ が何であっても区間グラフになります．試してみて下さい．
-
単位円グラフについて
ある頂点vの隣接頂点の中で同じ色を持つものは6未満ではないのですか？ (vの円の周りに6つの円を接するように配置するとその円同士で接してしまうように思います．) 6を含めるのはなぜですか？
---
ご指摘の通りです．6を含めるのは，その方が証明が簡単だからです．接している状況を正確に理解して，記述するのは割と大変です．
-
単位円グラフに書きなおすことでかえって見にくくなりそうな気がしました．
---
描くことは重要ではありません．実際，コンピュータの中では描いて処理するわけではありませんし．重要なのは，グラフであると見なすことです．そうすることで，グラフに関するいろいろな考え方が応用できるようになるのです．
-
今日のスライド，色と形がちがくて，区別しやすかったです。○，△，□，× (←これは前回の) を使ってくださりありがとうございます。
---
こちらこそ，指摘していただいてありがとうございました．
-
コメントに対応してスライドの頂点の表記を変えるようなフットワークの軽さは良いと思います
---
そのためのコメントです．活用して下さい．
-
スライドがとてもみやすくなっていました．ありがとうございます．
---
他に，みやすくなるような提案があったらお願いします．
-
毎度演習問題で表記ミスなどの凡ミスをしてしまうので，気を付けて見直す習慣をつけたいです
---
「表現する」ということの難しさだと思います．慣れと同時に注意力や集中力，そして，論理性や客観性など，いろいろなことに気をつけないといけないですからね．
- その他もろもろ
-
ディベートで大失敗しました。笑って下さい。
---
(^-^)
-
いつもpdfをブラウザ見てる。いい感じのブラウザ上で見れるPDFビュアーがほしい．
---
使っているブラウザに依存しますね．いろいろとあるようなので探してみて下さい．なお，私は常にダウンロードしてます．
-
なでしこ残念でしたね
---
残念でしたね．大きな実力の差を見せつけられた気がしました．
-
問題なし。
---
問題があった場合，指摘をよろしくお願いします．
-
海の日を利用して，テスト勉強を頑張ろうと思います。先生の海の日のご予定は？
---
出張です．
-
最近ねむいzzz
---
そのまま永眠しないように気を付けて下さい．
- 6/29 (10) 彩色：数理
- コメントありがとうございました．提出数が減っています！ このコメント欄は私の生きがいなので，みなさんしっかり提出して下さい．
- 色と図について
-
色弱なのでwebにあがっているものもふくめて，スライドの赤と緑の区別が難しいです。辺はむずかしそうですが，頂点は1, 2とラベルを書いたり，○，□，△など使ってほしいです。
---
ご指摘ありがとうございます．いわゆる「ユニバーサルデザイン」になっていないことは重々承知していたのですが，あまり深く考えていませんでした．頂点については○，□，△などを使ってみたいと思います．
-
資料の中身を見ずに白黒で印刷したら色が分からなくなって困った。
---
分かりやすくなるようにしました．
-
線が見えないか心配していらっしゃいましたがもう少し太くしてみては？
---
太かった図もあったのですが，一部太くなっていなかったので心配しました．太くしておきました．
-
青と紫の判別は難しいです…
---
私にとっても難しいです．色の数が足りないのです．
- 講義内容について
-
今日のグラフは今までと違ってカラフルだなと思いました．
---
色を塗るという話題ですからね．
-
電通大の学部1年から4年における時間割も辺彩色を用いて作成しているのですか？ もしくはもう既にそういったソフトがある？
---
電通大については知らないのですが，時間割作成は1つの産業になっていて，いろいろなソフトが売られています．特に，小学校，中学校，高等学校で使われているようです．使われている技術は単純ではありませんが，その根幹には彩色のような考え方が使われています．
-
4色で地図を塗り分けられると聞いたが，これの証明はグラフでできるのか
---
その事実についてはあとの方の講義で扱います．証明はしませんが．
-
日本の各都道府県を彩色したくなりました。
---
してください！ 地図の彩色は後の講義であつかいます．
-
大きさが偶数の閉路しか持たないグラフは2彩色可能ですか？
---
正しいです．大きさが偶数の閉路しか持たないグラフは二部グラフなので，2彩色可能です．
-
以前除雪車の問題などありましたが，この分野はどのような職種で使われることが多いのでしょうか？プログラミングと違って少しイメージしづらいです。
---
「この分野」がどの分野を指すのかによりますが，どこでも使われます．プログラミングがイメージできるなら，プログラムの中のどこでも使われています．今日，コンパイラの話を出しましたが，コンパイラの中で使われているので，プログラムの中で使われていると思ってよいです．
- その他
-
中間していま人数がグラフより多いのですが…？
---
すみません，まず書いてある文字が読めませんでした．「中間していま人数」の部分にはおそらく違うことが書いてあるのだと思うのですが，読めませんでした．どう頑張っても「中間していま人数」としか読めず，結局意味不明でした．
-
今更ですが，最後の1回の講義の内容の提案です。ちょくちょく名前や写真が上がっていた人たちに関するお話など是非ききたいです。
---
すみません，私自身，あまり人間に興味がないので，それは難しいです．
-
すごい個人的ですがサイトのPDFのリンクを<a href="..." target="_blank">にして新しいタブで見れるようにしてほしい
---
全部そうしました．試してみて，うまく動くか確認して下さい．
-
どうでもいいですが学生の間ではSplatoonという彩色しまくるTVゲームが流行しているみたいです。
---
「学生の間では」なのですね．(^^) このようなゲームにどのような技術が使われていて，なぜ人々がひきつけられるのか，ということを考えてみて下さい．
-
J1レポートがキツくて授業中ねてしまったのですが、夢の中で演習問題を解きおわってました。起きたら演習問題始まりました。カナシイ…
---
なんかオカルトのようですね．
-
実験がつらい．
---
当然です (^^) はりきってやりきりましょう．
-
インターンとTOEICでいろいろ大変だった。
---
お疲れ様です．
-
上手く説明しようとしても結局伝わらないという場面がよく出てくる時があります．気を付けたいです．
---
ラーメン二郎で複雑な注文をして，鍛えて下さい．
-
雨がきらいなので梅雨が早くあけてほしいです．
---
同感です．
-
がんばれ なでしこJAPAN！
---
朝早く起きたら，ちょうどオーストラリア戦をやってて，ちょうどゴールがはいりました．なんか得した気分になりました．
-
まだ自分が3コースの研究室でどこに行きたいのかわからなくて苦しいです．
---
焦らなくてもよいですが，情報収集は念入りに行うとよいと思います．
- 6/22 (9) 全域木：数理とモデル化
- コメントありがとうございました．中間試験の採点が終了しましたので，素点などを確認して下さい．
- 改組，カリキュラム関係のご意見
-
改組は利点が良くわかりません。
---
ここでは答えられないので講義のときにコメントします．
-
科の変更、キャリアなど 電通大は迷走しすぎている。
---
ここでは答えられないので講義のときにコメントします．
-
インターンシップコースってどうしてなくなるのでしょうか．
---
ここでは答えられないので講義のときにコメントします．
-
改組は利点が良くわかりません。
---
ここでは答えられないので講義のときにコメントします．
-
電気通信学部から情報理工学部へ変更して4年でまた変更するのはかんべんしてほしい…。
---
ここでは答えられないので講義のときにコメントします．
-
セキュリティ分野が、現I科、また新I類から独立しているのは、分類として妥当なのでしょうか？ 入学の段階で、専攻がせばまってしまうのはあまり良くないような気がします。
---
詳しいことはここでは書けないので、講義のときにコメントします．ただ，現体制で，「J科にいかなければセキュリティができない」というわけではありません．I科の中にもセキュリティを扱っている研究室はあります．
-
この研究室は本当に4コースのものなのか？ということがある。
---
コース分けは大まかなものです．「○○コースだから△△でないといけない」という狭い見方ではなくて，広くとらえることが大事だと思います．
-
提案になるかは分かりませんが，先生方が学生が勉強したことのあるプログラミング言語を把握していないようなので困ります。2年次までの授業ではC言語しか勉強していないので3年次の授業で他の言語を使って説明されても理解できません。
---
言語自体の説明は授業で (詳しくないかもしれませんが) されていると思いますので，それに従って下さい．
-
全体的に名前が長すぎるように感じるので短くしてほしいです。履歴書などを書く時に苦労するので…。
---
確かにそうだと思います．詳しいことはここでは書けないので，講義のときにコメントします．
-
学部の名前をコロコロ変えるのは自信がないみたいでかっこわるい。やめてほしい。ドーンとかまえてほしい．
---
ここでは答えられないので，講義のときにコメントします．
-
そもそも前の改組が100周年に向けたものだったような．改組の際は、2年前期に計算機を使う実習を増やして欲しいです．
---
2年前期に計算機を使う実習が増える予定です．
-
1年次の段階から学科別の科目を履修できるようにしてほしい．コース別実験の内容を理解するための科目を，実験と同学期に履修している現状は都合が悪い
---
それができるためには，入学したとき既に学科 (改組後は類) へ所属していないといけないのですが，改組後，前期日程で合格して入学する学生は類に所属しないことになっています．なんでそうなのか，ということはここでは書けないので講義のときにコメントします．
-
I科の3,4コースはまったく同じ授業なので，コースを分けないでもよいのではないだろうか．
---
いろいろな事情で分かれています．いまの体制の前，旧J科のときにはコースではないですが講座という概念がありました．それは今のコースよりも細かい分け方でした．
-
建設的な意見でなくて申し訳ないですが，I類II類III類という名称は東大や東工大のマネしてるみたいでダサいと思う。
---
こういう率直な意見は貴重です．ありがとうございます．
-
改組後のカリキュラムがどうなっているかさえ知らないので、調べてみて書きたい事が出たら来週書こうと思います．参考資料等あったら教えて下さい．
---
参考資料を出していいのか私は判断がつきません．すみません．カリキュラムはほとんど決まっています．出せる段階になったらお知らせします．
-
教育のありかたについての意見とは違いますが，数学科の図書室 (東1号館) の貸し出し期間が教員については無期限なのが不満です。また，借りられている本への予約など，割り込める制度もないのです。
---
おそらく，それは教員の研究用図書が図書館に登録されているだけなのだと思います．つまり，それは開架に並ぶ普通の図書とは違う扱いになっているのではないでしょうか．特に，東1号館の図書室を東3号館にある図書館と同じように学生が使うことは想定されていないと思います．大学として蔵書を管理するため，東1号館の図書室の図書も図書館で管理され，所蔵が明らかになっているだけなのだと推測します．
- 中間試験について
-
救済小テストしてほしいです…
---
ありません．そもそも120点満点でやっているのですから，その時点で十分に救済されています．それに加えて何かを行うということはありません．
-
中間テストの答案を返却してほしい．
---
中間テストではなく中間試験ですね．返却はできません．異議申し立てがあったとき，私が確認できなくなるからです．
-
なぜ希望者のみに点数だけを知らせる形式をとったのですか？
---
質問が2つに分かれているので，それぞれに答えます．「点数だけを知らせる」のは答案を返却できないからです．「希望者のみに」というのは，希望しない人には知らせなくてもよいからです．
-
かなりの部分点を頂けたみたいで予想外の点数に一安心しました。
---
期末試験もありますので，あまり安心ばかりしていないように注意して下さい．
- 最終回に対するリクエスト
-
最終回：もっと多くのアルゴリズムが知りたいです．
---
この講義ではアルゴリズムをあまり扱いませんが，検討します．
-
追加問題で正答率の悪かったやつの解説とか？
---
これはしません．レポートとして提出して下さい．
-
最終回、試験に役立つ内容にしてほしい．
---
試験に役立つように，演習問題のレポートを返却します．
-
最終日にやってほしいこと：未解決問題 (この授業に関係する) に挑む回
---
それだと試験が難しくなりすぎるので，私も皆さんも困ります ;-)
-
この講義の内容で様々なゲームを見せて頂きました。最終回では「応用すればこんなゲームもできる」という斬新なものをしてほしいです。
---
「斬新なもの」っていうのは難しいですね (^^; 考えてみます．
-
最終回は、グラフを使った必勝法がある他のゲームを取り上げて欲しい．
---
斬新なものでなければいろいろとあるので，それを検討してみます．
- 演習問題について
-
証明問題を見るのが嫌になってきました．
---
「問題」だと思うから嫌になるのだと思います．
-
8.5が難しかったです。ヒントなどあれば教えてください。
---
「数え上げによる証明」を考えて下さい．グラフ $G$ の最小頂点被覆を1つ考えて，それを $C$ とします．$C$ が行に対応し，$E$ が列に対応するような行列を考えてみて下さい．
- 講義の感想，コメント
-
全ノードへの通信経路の決定に全域木を使うと聞いてまずIRCが思いうかびました．
---
IRCは全域木を使っているようですね．その他にも全域木を使っているプロトコルは多く存在するようです．
-
資料中の「全張木，生成木」が「金成木」に見えました．金欠ではないはずなのですが．
---
どれだけあっても足りない，ということなのでしょうか (^^;
-
アルゴリズムと帰納法の関係が面白かったです。
---
別の言い方をすると，アルゴリズムの正しさなどを証明するときに数学的帰納法を使うことが多いのです．
-
数週間前に課題でCommon Lispで再帰関数ばかり実装していたのですが，ちょっと帰納法の証明を考えているっぽかったです。
---
そうですね．再帰的な思考はとても重要なので，しっかりと身につけて下さい．
-
"一方が経路をつくらないときもう一方が経路をつくる"のは証明しなくてもいいのでしょうか．
---
本当は証明しなければなりませんが，講義では直感的な説明にとどめました．
-
もしかして○×ゲームにも必勝法が存在するのでしょうか…
---
はい，存在します．ツェルメロの定理というものがあり，2人で行うゲームにおいて，1人だけが知っている情報がなく，サイコロのような偶然性を使わないならば，「先手必勝」か「後手必勝」か「引き分け」か，必ず決まります．おそらく，詳しいことは『ゲーム情報学』の講義で扱われると思います．
-
最近はパズルの話が絡んでくるので、楽しいです．後輩に楽しい講義の1つとしてすすめようと思います．
---
たとえば，皆さんがご家族と大学の話をする機会があって，「どんなことを勉強しているの？」というときの題材としても使えるかもしれません．ぜひ試して下さい．
-
パズルの中にも数学的な戦略を見つけられるということを改めて実感しました．
---
そうですね．「必勝戦略」と呼ばれるものは大体数学的な考え方に裏打ちされています．(そうでないと見つけることが難しいので．) この講義ではその中でもグラフを用いてモデル化できるものを紹介しています．
-
身近なゲームで、ある場面から勝つことは出来るのか考えてみたいです
---
いろいろなゲームがあると思うので，ぜひ試してみて下さい．
-
2人またはそれ以上で遊ぶゲームをたくさん紹介して下さい。
---
ゲームを紹介することがこの講義の目的ではないんです (-_-; でも，題材としてよいので，また出てくるかもしれません．
- その他
-
講義中腹痛やばかった．
---
ストレスでも腹痛になるそうなので，気をつけて下さい．
-
---
日曜日に休んで，月曜日に活動して下さい ;-)
-
4時間も寝たのにとても眠いです．
---
では，もっと寝てきてください．(^^;
-
愛用のシャーペンがなくなった。期末がんばります。
---
私は最近もっぱらボールペンをつかっていますが，ペンシルパズルをやるときは2Bとか濃い目の芯をいれたシャープペンシルを使います．
- 6/15 (8) 最大流：モデル化 (2)
- コメントありがとうございました．中間試験の採点についてはもう少々お待ちください．
- 中間試験について
-
はやく中間テストの点が知りたいです
---
すみません，次回までには採点を終わらせる予定です．
-
中間試験の結果発表はどのぐらいの時期になりますか？ 気になって夜も眠れません。
---
次回までには，と思っています．安心して寝て下さい ;-)
-
テスト クラス全体的な出来を教えて頂きたいです．
---
採点が済み次第，このページ上で報告します．
- 天候，気候について
-
最近涼しくなってきた…と思ったら暑くなってきました…。涼しくして下さい！！ (＃`Д´)ノ。°
---
私に言われても困ります (-_-;
-
何台かドライで稼働できませんかね。じめじめして書きづらいです…
---
そうですね．可能ならば，次回はそうしてみましょう．
-
教室がじめっとしてて暑いです．
---
可能ならば，次回はドライもやってみます．
-
今日の教室は快適な温度だった。
---
一方で，このような意見もあるのですね．休憩のときにドアを開けた方がいいのかもしれませんね．
- 講義内容について
-
ちょっと難しかったです。
---
ちょっとならば，大丈夫です．;-)
-
途中で置いていかれ、理解しきれなかった。演習問題など利用して、しっかり復習しようと思います。
---
講義時間の中だけですべてを理解する，ということは想定していないので，復習をしたり，演習に取り組んで，理解して下さい．
-
ますますむずかしくなってきた気がする。
---
いままでの部分を踏まえて講義が進んでいるので，その理解が不十分だと難しく感じるのは当然かもしれません．手遅れになる前に復習をして下さい．
-
授業におくれてすみません
---
私には迷惑が掛かっていないので，謝らなくてもいいです．(^^;
-
体力が尽きました
---
ポーションを飲んで下さい．
-
「結婚可能性が低い」にダメージを受けました。頑張ります。
---
何を頑張るのでしょうか？ (^^)
-
結婚定理のグラフが有向グラフになったら悲しいことになりそう
---
日本の法律において，一方的な結婚はないので大丈夫です．婚姻は両性の合意のみに基づいて成立します．
-
何でHallさんは「結婚定理」という名前をつけたのでしょうか．「Hallの定理」とかでも良かったと思うのですが．
---
Hall自身が「結婚定理」と呼んだわけではないようです．これを「結婚定理」と呼び始めたのは別の人 (Weyl) で，それが広まったのだそうです．
-
勘ですが、結婚可能問題が提唱された時代は、結婚をするとき身分や階級、家柄の違いによる制約が大きかったのかなと思いました。
---
Hall自身が「結婚定理」と呼んだわけではないということは踏まえておいて，定理の発見は20世紀前半 (戦前) なので，階級意識がまだイギリスに根強く残っている時代だったのだというのは確かだと思います．Hall自身がこの定理を考えた経緯は別の数学の問題にあり，「結婚」自身とは関係ありません．
-
最大マッチングって生活の上でどんな時に使われるのでしょうか。
---
「生活の上」ということばでイメージすることが人によって異なるので，質問に答えられていないかもしれませんが，1つは，実験第一J8課題の例を思い出して下さい．他にも割当を行う様々な場面で現れます．
-
日本語は縦書きなので縦方向が行、⇒五十音表は縦が行．英語は横書きなので横方向が行⇒数学は英語基準？で横が行．とするとトランプも横が行でいいと思います。
---
ありがとうございます．今度から心置きなく「行」と言います．
-
UECで結婚定理を利用できるような二部グラフを作ってみたいです！ しかし，I科3,4コースだけで作ると利用できなさそうです…
---
作りましょう！ できたら教えて下さい．
-
イメージを文章に変えられるまで，少しかかる感じです．力をつけていきたいです．
---
まず，確実にできるようにして下さい．慣れてくれば，時間は短くなっていきますが，はじめは時間がかかってもよいです．
-
追加問題8.6のような問題でタイルの大きさが1×2ではなくなってしまった場合グラフを用いてモデル化はできるのですか？
---
モデル化できる場合もあります．例えば，3つの正方形から成るタイル (2種類あります) によって敷き詰められるか，という問題もマッチングの問題としてモデル化できます．
-
予備日はグラフに関するおもしろい話をしてください！！あと中間の採点がんばってください！
---
毎回おもしろい話をしているつもりなので，ちょっと困りました．もう少し具体的な提案をいただけるとありがたいです．
- その他，砕けた内容．
-
前に蛙が雨のように降ってくる場面がある映画を見たことがあるのですが、先生はそのような不可思議な体験をしたことがありますか？ (その映画はしっかり、蛙を踏み潰す音や血などが表現されてて、とても生々しかったです。ちなみに劇中ではなんの説明もなかったです。)
---
『マグノリア』でしょうか？ これは怖いですね．
-
セ・リーグが弱い…。交流戦は毎年パが強いイメージがあります。
---
DeNAが大変なことになってますね．
-
最近，友人の間で "グラフとネットワーク" のことを，"ぐらねっと" と呼んでいて，この呼び方が気に入っています。ただ，ぐら↑ねっと↓ と言うべきか，ぐら↓ねっと↑ と言うべきかなやみます。
---
どっちでもいいです ;-)
-
最近生活リズムが崩れててつらい．
---
夜にちゃんと寝ましょう．重要です．
- 6/1 (7) 最大流：モデル化 (1)
- コメントありがとうございました．次回は中間試験ですので，しっかりと準備してきてください．
- 試験について
-
試験こわい
---
もうそろそろ慣れて下さい．
-
テストがんばるぞ！！
---
はい，しっかりと準備してきてください．
-
テスト ガンバりたい
---
はい，しっかりと準備してきてください．
-
テストがんばります．
---
はい，しっかりと準備してきてください．
-
来週の中間，頑張ります．
---
はい，しっかりと準備してきてください．
-
テスト頑張ります。
---
はい，しっかりと準備してきてください．
-
中間試験の問題は易しくしてください。
---
シラバスの記載，そして，同じですが，講義で述べた達成目標に基づいて，試験を実施し，評価を行うので，そのつもりで臨んで下さい．
- 演習問題と講義について
-
説明がとばしぎみで困った
---
今回はいろいろなことをやろうとして早くなってしまいました．(昨年度はほとんど問題がなかったのですが．) 演習問題を通して，復習をして下さい．
-
問題7.3(1)「最大流問題として定式化せよ」の「定式化」がよく分からないのですが「モデル化」と同じですか？ スライドの11枚目のような図で表せばいいですか？
---
用語が統一されていないようでした．すみません．「定式化」と「モデル化」は同じ意味で使っていると思って下さい．それで，スライドの11枚目のような図で表せばよいです．
-
「最大流としてモデル化」と「最大流として定式化」(追加問題7-3の表現) は違う意味ですか？
---
すみません，同じ意味です．
-
最大流がこんなに利便性があるのは想像以上でした．
---
思いもよらない形で使えるところが面白いですね．
-
最大流問題の解法の便利さが分かりました．
---
ぜひ，皆さんも使ってみて下さい．
-
Fordさんはすごく良い人にみえる。Fulkersonさんは、少し変わっているんだろうな、という印象を受ける。話してみたいのは断然Fulkerson！！
---
少し変わっている人とお話をしたい，ということなのですね ;-)
-
三角関係は無向グラフですか？ 有向グラフですか？
---
「関係」というのは本来有向グラフで表現されるべきものですね．対称性を持つ (対称律を満たす) 関係は無向グラフで表現できます．
-
先生，これなら四角関係ですよ！
---
なるほど，確かに．
-
これならば四角関係が成り立ちます！！！！
---
同じ発想の方がここにも (^^)
-
細かい部分の間違いが多発しがちでした．正しく直しておきたいです．
---
そうですね．日本語の表現から数学的な記法まで，細かい部分も十分に気を配って下さい．
-
解くのに非常に時間がかかりそうです
---
まずは，時間がかかってもよいので，解けるようになって下さい．
-
去年この講義を受けていれば実験のときに苦労しなかったと思った。(最大流問題について)
---
4年生の方ですね．講義と実験が関連を持つことはよくありますが，順番によって，片方が復習の形になります．復習のときに，前に自分でやった内容を思い出して，そのときのことを深く考え直すと，理解がより深まると思います．励行して下さい．
-
DETは勝てないということが証明されてしまい残念です。もしDETがあと1勝していれば…という空想をする場合は，全チームから t への容量1小さくした上で，他チームから1つ選んで，そのチームからtへの容量を1へらしたグラフをすべてつくって，それぞれで最大流をさがすのでしょうか？
---
実際に，DETが他のチームからあと1勝していた状況の勝敗表を作ってみて，そこから同じようにやってみればよいです．他のどのチームからも1回は負けている場合は，書いていただいた通りの方法でできます．
-
MLBの問題ですが，引き分けがあるとさらにややこしくなるのでしょうか？
---
引き分けをどのように扱うのか，ということで変わってきます．引き分けがあっても，勝ち数だけで優勝を決める場合は，実をいうと，同じように最大流問題を使って解けます．勝ち数が同じ場合に，引き分けの多い方が優勝，となると問題はややこしくなり，おそらく最大流問題を使って解けなくなります．
-
例えが野球だったので興味が湧かなかった。(▽∧▽)
---
例えば，サッカーのような勝ち点方式の場合でも，同じような問題が考えられます．また，Jリーグならば「入れ替え戦に進めるか」というものも同じような問題になります．そういう意味で，野球には限りません．
-
11時ちょっと過ぎになるといつもクーラーが切れて暑い
---
そういえば，空調は2時間で自動的に切れるんですね．それでは始まる前にいったん切って，また入れ直すことにしましょう．
-
最近暑くて夏バテぎみです．オアシスで救護されたい…．
---
オアシスの救護可能最大人数は決まっているので，注意して下さい．
- その他
-
今は国際子供の日らしい。
---
はじめて知りました．ありがとうございます．よく調べてみると，国によって「国際こどもの日」(International Children's Day) は異なるようですね．例えば，トルコでは国際こどもの日が4月23日なのだそうです．
-
お魚はなにが好きですか？
---
考えたことありませんでした．なんでも好きです．昔，さかなへんの漢字をたくさん並べて楽しんでたことがあります．鮭鯛鱈鮎鮪鯉鯵鯖鮫鯨鰤鱒鰊鯱鰹鮨鰈鱚鱸鰆鰍鮗とか，ですね．
-
駅から西地区に行くのにすごく時間がかかってしまいます。(歩くのがおそいため)。先生はどのような経路で行き来してますか？
---
日によって違いますが，よく使うのは，電通大通りを通って南門から入り，そのまま中門までたどり着く，という経路です．他には，新しいみずほ銀行の方へ行って，古いみずほ銀行の横を通って，食神の辺りに出る経路も使います．
- 5/25 (6) 最大流：数理
- コメントありがとうございました．残った部分は次回やりますので，資料などは忘れずに持ってきてください．
- 中間試験について
-
試験問題には，(発展)でなければ，復習，補足，追加どれからも出る可能性はありますか？
---
その通りです．
-
テストに部分点はありますか？
---
あります．しかし，部分点を狙って関係のないことが書かれてあっても加点されないので，注意して下さい．
-
中間試験に向けて今から頑張って勉強します。
---
はい，しっかりと準備をしてきてください．
- レポートと演習問題について
-
6回の演習問題について，返却は試験後ですか？
---
試験前に返却できるように工夫します．
-
演習問題で，全ての補足問題に対して考える方向程度でよいのでヒントがほしいです．
---
「対応する講義で習得すべき内容と，今までの講義の中で習得してきたはずの内容を用いて考える」ということがすべての問題に対するヒントです．それをもとにして考えて下さい．
-
再提出しようと思っていたレポートがたまってきました…。
---
たまるとやる気がでないので，もっとたまってしまう前に手をつけて下さい．
-
演習をしていると，どうしても何問かが分からず空欄になってしまいます。改めて解くときに解決しておきたいです。
---
そうですね．よろしくお願いします．
- 講義資料について
-
大学でプリントをプリントアウトしたいのですが，木曜〜金曜ぐらいにアップロードして頂けると助かります…．(難しいならば全然大丈夫です．すいません)
---
初回講義で説明した通り，資料は金曜日の18:00までに掲載されます．
- 講義の内容について
-
フォードとファルカーソンについての話も，また時間があればよろしくお願いします．
---
おそらく時間がないので，すみません．
-
講義で止めた数学者について語ってください。
---
おそらく時間がないので，すみません．
-
水道管の例を聞いたら，最大流の例のイメージがつかめました。
---
イメージは大切なので，イメージをつかみながら考えるようにして下さい．
-
イメージと流れが頭の中で先行してしまい，表現が不正確になってしまいます。
---
イメージを大切にしながら，それをしっかりと日本語として表現することが重要なので，それができるようになって下さい．
-
割ととっつきやすい内容だった
---
演習問題に取り組んで，しっかりと理解できるようにして下さい．
-
最小stカット，最大流，最大流最小カット定理……．最小最大最小最大…ウゴゴゴ．
---
「最大化」と「最小化」，そして，その2つを対にして考えることが重要で，それが最適化という分野の入口になります．身につけて下さい．
-
色づけされた流れの説明図が見やすかったです。
---
本来はあまり色に頼ってはいけないとも思うのですが，便利なので使ってしまいます．
-
流れで時間差は考えないのですか？
---
講義で扱った流れは，定常状態における流れであると思って下さい．つまり，ずーっと水が流れっぱなしの状況です．その場合は，時間差というものが問題になりません．一方，講義で扱わなかったように流れを扱うこともあり，そこでは時間差を考えることがあります．
-
強双対性の証明が難しいのは，線形計画問題にしたときに，カットの方では整数制約がつくからかなとか妄想してました。
---
整数制約がつくから，というわけではありません．整数制約がつかないものは線形計画問題の強双対性となりますが，それの証明もなかなか難しいです．おそらく，後学期の『数理計画法』で線形計画問題の強双対性を扱うと思うのですが，証明は講義でしないと思います．一方，最大流最小カット定理の証明は (容量が整数の場合に限れば) この講義で行うことができる範囲で収まるほどなので，それに比べれば難しくありません．
-
グラフとネットワークの"と"までカタカナで書きそうに…なってしまう…
---
それはいけませんね ;-)
- 普段の生活について
-
西食堂がないと不便
---
新しい西食堂に生まれ変わるまで辛抱して下さい．
-
西地区のごはん事情がきびしい
---
体育館のところで弁当販売が始まってると思います．それも利用してみて下さい．
-
楽にお金が貯まる方法ってありますか？
---
使わなければよいです．
-
TOEICで疲労感。
---
復帰して下さい ;-)
-
時折2限にも間に合わなくなるレベルで眠いです．『春眠暁を覚えず』とは言いますがもう初夏です．朝6時くらいにスッキリと起きられる方法，求む。
---
日中寝てしまうと，夜眠くなくなり，日中また眠くなるという悪循環が生まれそうなので，それをまず打破できればよいのではないでしょうか．
-
おすすめのおかしをおしえて下さい。
---
おかしではないですが，最近，やたらと果汁グミを食べてます．
- 5/18 (5) マッチング：モデル化
- コメントありがとうございました．「モデル化」の内容としては初回でしたが，ちょっと難しかったかもしれません．
- なぜか多かった質問から
-
グラフの描画は何を使っていますか？
---
ipeというアプリケーションを使っています．計算幾何を研究するほとんどの人は標準的に使っています．
-
グラフの図を書く時に使っているツールは何ですか？
---
ipeというアプリケーションを使っています．CEDには入っていないと思います．
-
スライドの例のようなグラフの描画はどのような方法でやっていますか。
---
ipeというアプリケーションを使っています．自動的に描くときにはgraphvizを使っています．
- レポートと演習問題について
-
一度だした演習の再提出は，何週間かあいてしまっても大丈夫でしょうか？
---
はい，大丈夫です．
-
証明で細かいところを指摘されると少しくやしいです (笑)
---
指摘されない，という目標ができたと思うので，目標達成を目指して下さい．
-
使うであろう証明方法をどう適用すればいいか分からず，応用問題 (補足問題や追加問題) で詰まってしまいます．
---
使い方には類型がある程度存在するので，例や復習問題を見ながら，考えてみて下さい．
-
文で説明しなければならないことの難しさを感じます．練習しておきたいです．
---
はい，文章で説明して下さい．皆さんが訓練しなくてはならないことの1つは，文章を書くことです．証明を書くことはその訓練のための方法として優れていると思いますので，演習問題を通して身につけていって下さい．
-
4.10の問題をみていて，最小の極大マッチングというのもあるのだろうかと空想しました。
---
最小の極大マッチングを考えることはできますし，広く考えられています．
-
「反例を示せ」というのは反例を1つでも挙げればよいのでしょうか？反例であることの説明は必要ですか？
---
反例であることの説明があった方がよいです．
-
追加問題4.9のグラフが思いつかなかったです。
---
頂点が奇数であるグラフは完全マッチングを持たないので，それをもとにして考えてみて下さい．
-
J8レポで忙しくて先週の課題できませんでした…
---
この講義のレポートは必須ではないので，提出しなくてもよいです．提出することは推奨しているので，時間のやりくりを上手に行って提出してもらえるとありがたいです．
- 今回の講義に関するコメント
-
Too difficult
---
You are invited to ask any questions! Please do so. No matter how many times you just say "difficult", things don't change.
-
グラフの考え方を実際に応用しているところを聞いているのは楽しかったです．しかし，基礎ができていないと自分で応用することはできないので，まず先週休んだ分を勉強して，しっかり基礎を身につけていきたいと思います．
---
そうですね．「応用」というものは難しいもので，基礎があってこその応用だと思います．
-
応用が入ってきたので、おもしろくなると思います．今までもおもしろかったです。
---
数理モデル化は重要なので，その視点を大切にして下さい．
-
実際の応用例を知ることができ，大変楽しかったです．
---
実をいうと「実際の応用例」というのはもっと複雑です．しかし，複雑な問題を解こうとするときには，それを簡単なものの組合せとして表現することからはじめることが多いので，この講義で扱えるほど簡単なものを考えることにも意味があります．
-
今回の講義は非常に面白かったです。離散最適化？の分野に強くひかれました。
---
数理モデル化の内容はたびたび登場しますので，ご期待ください．
-
初回授業で言っていた「センサーネットワーク」での例も見てみたい
---
はい，あとで出てきます．ご期待ください．
-
久しぶりに面白い内容だったし分かりやすかった
---
久しぶりですみません．;-)
-
面白かった
---
すみませんが，しっぽは生えていません．
-
$\displaystyle \sum_{v \in V}\sum_{e\in E}$ がかわいく見えてきました。
---
おそらく病気です．…冗談です．
-
ごめんなさい ねてしまいました またしても
---
字余りですね．
-
スリザーのグラフを考えるのもおもしろそうだと思いました。
---
はい，ぜひ考えてみて下さい．
-
スリザーの話は面白かったです。
---
たくさん遊べると思うので，試してみて下さい．
-
色々なことを知りすぎてだんだん定義とかがごちゃごちゃになってきました。
---
講義資料が電子的に存在すると怠りがちかもしれませんが，ノートを作って自分で整理するのもよいかと思います．
-
用語と定義が多く大変に感じます．
---
以前から言っていますが，覚える必要はないので，その点は注意して下さい．
-
歩道と道の違いが良く分かりません。道⊆歩道の理解で正しいですか？
---
「⊆」が何を意味するのか不明ですが，直感的に言うと，道は「頂点や辺の繰り返しを許さない歩道」です．言い換えれば，歩道では頂点や辺の繰り返しが許されています．
- その他
-
今日からがんばります。
---
はい，よろしくお願いします．
-
好きな音楽は？
---
最近はやりませんが，本当のことをいうとラテンが好きです．
-
もうすぐセパ交流戦が始まりますが阪神ファンとしては嫌な予感しかしません…。
---
DeNAの勢いが弱まるよい機会かもしれません．ポジティブに捉えましょう．
-
おすすめのお茶を教えてください．
---
最近はコンビニの安いオリジナルブランドのお茶で満足しています．私のレベルでは，それで十分です．
-
牛乳うまい！！
---
牛乳はお茶ではありません．
- 5/11 (4) マッチング：数理
- コメントありがとうございました．次回は今回の残りから始めます．
- レポートについて
-
中間試験，レポートラッシュは大変である
---
おそらくこの時期は毎日がスペシャルですね．
-
レポートの直しはまとめて出しても良いですか？
---
良いですが，あまり溜めることはお薦めしておりません．
-
コメントを見てレポートがんばります。
---
はい，よろしくお願いします．
- 演習について
-
演習がほとんどできていないのですが、これは危ないでしょうか？ テストは演習の追加問題と同レベルのものが出題されるのでしょうか？
---
危ないかどうかは個人に依存するので，それについては何も言えません．自分で考えて下さい．個人に依存しない，初回講義で説明したこと (第1回スライド14ページ) と同じことを述べます．中間試験も期末試験も演習問題と同じ形式の問題が4題出題されます．その全問に解答して下さい．その中の2題以上は演習問題として提示されたものと同一です (ただし「発展」として提示された問題は含まれません)．
-
問題を解いているとどうしてもイメージが先行して文をどう書くか悩みます．改善していきたいです．
---
イメージが先行することには問題ありません．そのイメージをどのようにして文章として表現するのか，ということが大事です．重要な技術なので，鍛えて下さい．
-
証明で，感覚では分かっているけれど言葉にできないことがあります．
---
もしかしたら，「感覚では分かっている」というのは本当に分かっているわけではないのかもしれません．ことばにして，他の人に自分の感覚を伝えられるようになってはじめて，真に分かっているという状況になるのだと思います．
-
証明，文章でなやむのでもう少しなれたい
---
上の皆さんと同じでしょうか．文章を書くことのトレーニングが必要なのだと思います．そのためには，まず，論理的に考えること，特に，1つ1つのステップを積み重ねることによって議論を行うこと，という過程が重要です．もう1つは文章の作法です．文章には書き方の決まりのようなものがあります．それに沿って書かないと，文章は非常に読みづらいものになります．よい書籍の文章は，理路整然としていて，とても読みやすくなっています．それが小説であっても，数学の教科書であっても，そうです．よい文章を読んで，よい文章を書くためのヒントを得ようとしてみて下さい．
-
今週の演習問題がおもしろそうなので出してみようと思います．
---
毎回おもしろい演習問題を出しているつもりなのですが (^-^; ぜひ出してください．
-
「完全マッチング⇒|V|=2|M|」は証明で用いてもよいですか．
---
それ自身を証明せよ，という問題でなければ，用いてもよいです．
-
課題をもっと時間をかけて考えたい。
---
はい，自習の時間をしっかりと取って下さい．自習ということばに反するかもしれませんが，グループで自習をすることをお薦めします．
- 講義の内容や進め方について
-
実験で扱った2部グラフの増加道アルゴリズムを実装するのにとても手こずりました。難しいです。
---
慣れないと難しいですが，難しいぐらいのことをやらないと大学でやる意味がありません．一人でできるならば，一人でやればよいのですから．
-
グループでけんかさせるんじゃなくて2人組を作るんじゃダメなんですか？ｗ
---
「2人組を作る」ということに対して電通大生が共感を持てないのではないかと思いました．……冗談です．
-
おもしろかったです．
---
すみませんが，しっぽは生えていません．
-
実験でよくわからなかった増加道法が理解できてよかった。
---
よかったです．同じ内容を数回繰り返すことで，理解が深くなったのだと思います．
-
J8課題で増加道で上手くいく理由がわからなかったが，今回の講義でわかりました．
---
実は，実験資料の最後に上手くいく理由が書いてあります．もう一度見直してみて下さい．
-
実験では何故最大マッチングを増加道で探せるのかわからなかったのでこの講義でわかってよかったです。
---
J8課題はこの講義をとっていなくてもできるように設計されています．実験は必修，この講義は選択なのですから，そうなっているのが当たり前なのですが，その「当たり前」がなかなか実践されないのは困ったことの1つでもあります．
-
j8実験で行っていた内容をようやく理解しました．
---
これで，満足のいくレポートが書ける，ということですね (^^)
-
道 $P$ に頂点 $u$ をくっつけるときの表記は $P+u$ と書くのでしょうか？ $P,u$ と書くのでしょうか？
---
決まった記法はありません．$P+u$ と書いたり，$P,u$ と書いたり，$Pu$ と書いたり，$P\circ u$ と書いたりすることがあります．決まった記法がないので，この記法を使うときはその前に記法の意味するところを説明するようにしています．
-
頂点被覆による最大マッチングの確認方法が面白いと思いました。
---
とても使える技法なので，ぜひ身につけて下さい．
-
最小頂点被覆はどのように求めるのでしょう
---
最小頂点被覆を求めるのは難しいので，「がんばって」求めます．この辺りは離散最適化の深遠な世界の入口なのですが，講義で扱うには深すぎます (いろんな意味で)．カリキュラムとしては，3年前学期の『グラフとネットワーク」と『アルゴリズム論第一』，3年後学期の『アルゴリズム論第二』と『計算理論』を経て，大学院の講義へと進んで理解を深める，という感じなのですが，そこまで行くにはなかなか時間と労力がかかります．
-
資料の弱双対性では $|M| \leq |C|$ となっていますが，$|M|=|C|$ が必ず成り立つのでなければマッチングが最大であることを示せない場合がありませんか．($M$：最大マッチング，$C$：最小頂点被覆)
---
その通りです．$|M|=|C|$ が成り立たない場合があり，その場合，弱双対性は非力です．一方，$|M|=|C|$ が成り立つ場合，その威力は絶大なわけです．あとの講義で出てきますが，実際，二部グラフにおいては $|M|=|C|$ が必ず成り立ち，そのため，二部グラフの最大マッチングを求めることは簡単に (つまり，皆さんが3年生に実験で実装できるぐらいの難易度で) できる，という仕組みになっています．
-
途中から難しくなった
---
どこからでしょう．
-
今日はねむくなかった。よかった。。。
---
よかったです．毎回そうでありますように．
-
一限があるので、少し眠かったですが、おもしろい．
---
一限があることと眠いことはあまり関係ないと思うので，しゃきっとしましょう．(^^)
-
面白かった おなかすいた 眠かった
---
川柳かと一瞬思いましたが，違いましたね．(^^)
- その他のコメント．くだけたものを含む．
-
日
---
一本足してできる漢字は，目，田，由，甲，申，旧，旦，白，だけでしょうか？ 他にありますか？
-
学校くるの久しぶりでした
---
復帰おめでとうございます．
-
GWはどうでしたか？
---
風邪ひいて，ほとんど何もできませんでした．
-
阪神、最下位に転落です…。
---
なんかDeNAが強いですね．
-
圏論の本の最初を読んだら，メタ圏とかメタグラフというのがでてきて有向グラフにそっくりでした。
---
可換図式ですね．これは有向グラフです．弧の描き方に特色があり，その書き方の違いで，射としての性質の違いを表すので，注意が必要です．
- 4/27 (3) 木：数理
- コメントありがとうございました．来週は祝日で休みとなります．
- 演習とレポートについて
-
握手補題は試験において名前のみで $\sum_{v\in V} \deg_G(v) = 2|E|$ であることを書いてしまってもよいでしょうか。
---
握手補題そのものを証明するという問でなければ，よいです．
-
演習問題に解答の優先順序があると嬉しいです。
---
どれかが重要であり，どれかが重要ではない，ということはないので，順番をつけるのは難しいです．すみません．
-
レポートとしてその日だせなかった一部の問題を後日のレポートにくっつけて提出しても添削してもらえますか？
---
コメントをつける保証はありませんが，くっつけてもらってもよいです．
-
全回提出した質問への回答ありがとうございました．丁寧に書いていただき，非常に分かりやすかったです．
---
もし私の書いたところに分からない部分があるときは質問をして下さい．
-
レポートの添削ありがとうございました。がんばります。
---
はい，「継続は力なり」ということわざもありますので，ぜひ継続して下さい．
-
追加問題の2.8が解けなかった。3回目のレポートはがんばりたい。
---
問題2.8のヒントを出します．問題2.6と同様に，長さ最大の道を考えて，頂点数が$n/2$よりも大きい閉路が$G$に存在することをまず証明して下さい．その次に，存在を証明した閉路の頂点数が$n$でないと仮定すると矛盾が導かれることを示して下さい．
-
演習問題等の問題で書き方にパターン等があれば教えてほしいと思いました．
---
「証明は文章」なので，書き方にパターンがあります．私の『離散数学』ではそれをやるのですが，皆さんの受けた『離散数学』ではそれをやっていないかもしれません．もしやっていない場合は，私の『離散数学』の講義資料をご覧ください (リンクは昨年度の講義を指しています)．
-
頭で想像して図に描き起こすことには慣れてきたが証明の文を書くことは未だに難しい．
---
「証明は文章」なので，慣れが必要ですね．演習問題の中でも復習問題に取り組んでみて，自分の解答と講義資料に書かれている証明を見比べてみて下さい．
-
今までの演習問題で色々と日本語がおかしかったことに気付きました．今後，今回のことも踏まえて，直しておきたいです．
---
意識をしながら日本語を使うことが大事なんでしょうね．励行して下さい．
- 天候と眠気について
-
暑くなってきた
---
そうですね．
-
今日は晴れ⤴ 春の陽気に誘われてzzz
---
だいぶ夏に近づいてきている感覚もあります．
-
眠い
---
しっかりと眠ってから来てください．
-
寝てしまいました。すみません。やる気はあります。
---
やる気をアピールしていただかなくても大丈夫です．(^^; 心配しないで下さい．
-
最近，気温が高くなってきたせいで寝つきが悪くなってきました。だから眠いです。
---
抱き枕をつかうとよく寝れるそうです．
- 講義の内容と進め方について
-
今回は図書館でスライド資料のpdfファイルを印刷しようとしたのですが，何故か1ページ目の上の方でスライドが途切れて印刷することができませんでした．
---
情報基盤センターの演習室ではうまく印刷ができないようです．CEDではうまく印刷ができますので，学内でしたらそちらを利用して下さい．
-
もっと休憩あってもいいと思う．
---
これ以上休憩があると授業ができないので，現状どおりで進めていきます．ご了承下さい．
-
毎回新しい用語がたくさん出てきたり，言葉の使い方の注意があったりして，外国語の講義を受けている気分になってきた．
---
「外国語の講義を受けている気分」という感覚は間違っていないと思います．理工学におけることばの使い方に習熟することが重要で，それによって専門的な思考ができるようになってくると思います．
-
グラフ$G$からある頂点$v$を取り除いて，$G-v$が非連結になるなら，$v$は切断点だとずっと思ってしまいましたけど…
---
正しいですが，それは切断点の定義ではありません．切断点の定義は「連結成分の数が増える」ことです．違いに注意して下さい．
-
道の頂点の次数について$\deg_P(v)$といった書き方はできますか．
---
できます．$\deg_G(v)$という記法では下付添え字$G$によって，考えているグラフを明示しています．それが$P$という部分グラフである場合，$\deg_P(v)$は部分グラフ$P$における$v$の次数を表します．
-
帰納法の2通りの証明についての話は大変参考になりました。
---
間違えやすいところなので，注意して下さい．
-
少しは帰納法の理解が深まった気がする。
---
数学的帰納法は今後もいろいろなところで出てきますので，徐々に慣れていって下さい．
-
間違っている証明の間違っている点を説明されると理解が進む気がしたので良かったです。その説明も，簡単な例 ($\sum_{i=1}^{n}i = \frac{1}{2}n(n+1)$ の証明) と比較してくれたので分かりやすかったです。
---
証明を理解するためには，よい証明と悪い証明の両方を理解するということが重要である場合があります．時間の都合から，授業の中で悪い証明をとりあげることがなかなかできないので，今回は特別にとりあげたということになります．
-
数学的帰納法についてもっと扱ってほしい
---
今後もでてきます．お楽しみに．
-
証明ムズイぞ！！がんばるぞ！！
---
証明というのは重要な技法ですので，ぜひ身につけて下さい．
-
証明はムズい
---
慣れる必要があるので，ぜひ慣れて下さい．証明が書けるか書けないか，証明が理解できるかできないか，ということが，今後 (皆さんの人生の中で) 大きな違いを生んできます．
-
証明サッパリ分からない…
---
まず，何が分からないのか，というところを見定めて下さい．そのようにして，分からない部分を解きほぐす必要があります．そして，その1つ1つを解決していってください．
-
説明がとても分かりやすかったです。木の様々な性質をしっかり覚えたいと思います。
---
覚えなくてよいです．忘れたときに思い出せるように，しっかりと整理しておくことが重要です．
-
帰納法で$|E|=|V|-1$の証明が正規表現のことを思い出しました！
---
どの辺りでそう思いましたか？ 興味があるのでもう少し詳しく教えて下さい．
-
同様にしてって便利な言葉ですよね。
---
そうですね．本当に「同様」である場合のみ使うように，注意して下さい．
-
難しいですがおもしろいです。
---
いままでは「数理」の内容ですが，何週間か後になると「モデル化」の内容もでてきますので，お楽しみに．
-
だんだんこの分野の証明法がくせになってきました。
---
いままで扱った証明法を今後も使っていくので，しっかりと復習をしておいて下さい．
-
じゅぎょうはわかりやすい。
---
演習問題で理解を深めて下さい．
-
内容が分かりやすかった
---
次回は少し趣が違うので，気をつけて下さい．
-
ちゃんと復習しておきます。
---
はい，よろしくお願いします．
-
ややこしかった。
---
冷静になれば，それほどややこしくないはずなので，しっかりと復習して下さい．
- その他．くだけたものを含む
-
niconico超会議に行ってきた。レポートを家に忘れた。
---
2つの文の間に因果関係はありますか？
-
髪，切りましたか？
---
はい，切りました．
-
今日は青のフリースではないようですが…
---
毎日同じ服を着ているわけではありません (^-^)
-
岡本先生の趣味を教えて下さい．
---
趣味ではないかもしれませんが，よくミスタードーナツにいきます．
-
昨日能見投手が約1年ぶりに完封しました！！
---
おめでとうございます．今シーズンは10勝してほしいですね．
-
最近，ワーシャル＝フロイト方を知る機会がありました。便利なアルゴリズムですね。
---
便利なアルゴリズムです．ご存じない方は『アルゴリズム論第二』で扱うと思いますのでお楽しみに．
- 4/20 (2) 道と閉路：数理
- コメントありがとうございました．このコメントが私の生きがいですので，皆さん忘れずに提出して下さい．
- 演習とレポートについて
-
演習問題，ヒントが欲しいときはその旨をかけばヒントをもらえますか？何かしら解いていないとNOですか？
---
どこまで考えたのかは私に伝えようとして下さい．そうでないと，どの方向からヒントを出せばよいのか分からないので．「何もかも分からない」という状況かもしれませんが，せめて「どこが分からないのかは分かる」というところまでは自分で解決して下さい．よろしくお願いします．
-
演習問題の提出はレポート用紙でなければいけませんか？ (例えば，ルーズリーフなどでは駄目でしょうか？)
---
ルーズリーフでもよいです．複数枚ある場合はホチキスなどで留めて下さい．
-
レポートのことをすっかり忘れていました．提出による加点などはありますか？シラバスには中間・期末のみ，と見えますが．
---
第1回講義資料13ページに「レポートは採点されない (成績に勘案されない)」とある通り，加点も減点もありません．
-
自主レポートの提出期限を2週間にしてほしい．
---
すみませんが，この要求には答えられません．1つは試験との兼ね合いです．2週間にすると試験に間に合いません．もう1つは皆さんの勉強の仕方です．演習問題に取り組むことは講義の復習を兼ねているわけですから，次の講義が始まるまでに取り組んでほしいのです．もう1つは私が見ることのできる限界です．ある週に大量にレポートが提出されることがあると，それらを私が見ることもできなくなります．物理的に時間が足りません．現状でもほとんど足りていないので，難しいです．
-
先週に引き続き解答の書き方でつまづきます…模範回答などの配布予定ってありますでしょうか？
---
配布されません．書き方がよく分からない場合はレポートとして提出して下さい．見ますので．また，「『模範』解答」というものはそもそも存在しませんので，ご注意ください．
-
演習問題難しい．夜おそくまで演習問題やってたら授業中ねむくなってしまった…
---
はい，演習問題はそんなに簡単であるとは限りません．独力であまり解こうとはせずに，他の人と相談をしたり私やTAに質問をしたりして，取り組んで下さい．
-
演習問題が少し難しい (日本語が理解できていないだけかと)
---
少し難しいぐらいがちょうどよいと思っています．簡単ならばやる意味はありませんから．
-
レポートをがんばります！
---
はい，よろしくお願いします．
-
日付を間違えて覚えていて，前回の演習を1題しか解けませんでした．次回は可能なかぎり解いてきます．
---
演習問題に取り組むことで理解が深まるので，励行して下さい．
- 講義内容に関する質問や感想
-
握手補題の証明で，行列 $M \in \mathbb{R}^{V\times E}$ と定義していたが，添字に自然数以外を使うのは新鮮な感じを受けた．復習のときにちょっと悩んでしまった．
---
これについては，講義でちゃんと説明していなかったのですが，$\mathbb{R}$の肩に乗っている$V\times E$が添字集合となります．ご指摘ありがとうございました．そういう意味では，$\mathbb{R}^2$というのは$\mathbb{R}^{\{1,2\}}$と同じ集合であると考えてもよいです．
-
有向閉路について，隣り合う頂点同士を反時計回りに弧で結んだものは有向閉路に含まれますか？
---
それも有向閉路です．隣り合う頂点同士を時計回りに結んでできたものと同じ「形」を持つものはどれも有向閉路です．
-
有向グラフの講義を受けていると以前触ったgitのことを思い出しました．
---
バージョン管理は有向閉路を含まない有向グラフとして表現できます．バージョン管理を効率的に行うデータ構造も数多く提案されていて，活発な研究分野になっています．例えば，persistent data structureやretroactive data structureっていう概念があります．
-
オートマトンでも似たような道というのがでてきました．
---
おそらく，オートマトンでは，道において同じ頂点を何度も通ることが許されると思いますが，グラフでは (普通) そのようなものを道とは呼ばないので，ちょっと違いがありますね．ただ，グラフでも同じ頂点を何度も通ることが許されることがあって，それはまた後の講義で出てくる予定です．
-
最大性論法難しそう
---
演習問題を通して身につけて下さい．
-
最大性論法の証明の発想は面白い．
---
面白い発想ですね．アルゴリズムに関する証明や他にもいろいろなところで出てくるので，とても有用です．
-
最大性論法は背理法の1種？
---
その視点は私になかったです．確かに背理法の1種かもしれません．証明全体が背理法であるというよりは，一部分に背理法の考え方を使っている，と考えるのが正しい理解かもしれません．
-
$\ell-1 \geq k-1$⇒$P_k$が存在するという点がぱっと見分かりづらかったので補足してほしかったですが，全体的にとてもわかりやすかったです．
---
補足します．$\ell-1\geq k-1$ならば$\ell \geq k$になります．すなわち，はじめに存在を仮定した道の頂点数は$k$以上になります．そして，その道の中には頂点数$k$の道が含まれているので，全体として，$G$にも頂点数$k$の道が含まれることになります．
-
最大性論法による証明の部分で「$P$が長さ最大の道であることから，$v_1$に隣接する頂点はすべて$P$の頂点である」という文が少しイメージできませんでした．$v_1$は$P$の端点であるので，隣接するのは$v_2$だけではないのですか？ それとも$G$は完全グラフで，$v_1$は他のすべての頂点に隣接しているのでしょうか？ よろしくお願いします．
---
ことばが不足していて分かりにくいので補足します．「$v_1$に隣接する頂点はすべて$P$の頂点である」という部分は「$G$において$v_1$に隣接する頂点はすべて$P$の頂点である」と読んで下さい．$G$とその部分グラフである$P$が登場していて，$G$における隣接性を述べているのか，$P$における隣接性を述べているのか，分かりにくかったと思います．もう1点ですが，「$v_1$に隣接する頂点はすべて$P$の頂点である」という日本語と「$P$の頂点はすべて$v_1$に隣接する」という日本語の意味は違います．注意して下さい．
-
最大性論法の証明法は理解できましたが，論述の方法がいまいち分かりません．
---
第2回講義スライドの20ページを参考にしてみて下さい．
-
記号ばかりで眠くなりそう
---
記号を使って議論を進めていくことは『離散数学』でやっていると思うので，それは前提にしています．休憩のときにリフレッシュするようにして下さい．
-
説明がわかりやすく，楽しいです．休憩が途中で入って良かった．
---
休憩は重視してますので，その時間にゆったりとしたり，背伸びをしたり，ストレッチをしたり，後半の準備として気持ちを整えて下さい．
-
証明の方針をどうするかが，少し難しく感じました．
---
これは演習問題を通して，慣れていって下さい．
-
難しかった．
---
全体的なレベルとして，『離散数学』と『プログラミング通論』が「前もって履修しておくべき科目」であって (そのようにシラバスに書いてあります)，それに関する訓練が十分できている人が対象になっています．そうでない場合は復習をしっかりとして下さい．そうである場合はこの講義の問題なので，分からない点について質問して下さい．質問をしないことは損だと思って下さい．
-
図を用いた説明が多いのはとてもありがたいです．
---
グラフは図でイメージをつかむことが重要なので，図も重視してます．今後もそうしていくつもりです．
-
講義資料にもっと証明の例を載せてほしいです
---
ちょっと時間の関係で，いまの分量になっています．講義の構成は「数理」の回と「モデル化」の回に分かれていて，昨年度の受講者によると数理の回の方が少しきついらしいです．
-
理解できると楽しいです．
---
そうですね．難しいかもしれないですが，難しいからこそ理解できたときのうれしさがあると思います．
-
三冊ある推薦図書のうちどれがオススメでしょうか？
---
どれもお薦めです．ただ，私見ですが，どの本もこの講義より格段に難しいです．注意して下さい．
-
2部グラフにも色んな形があって面白いと思いました．
---
そうですね．描き方によって得られる印象も違うのではないでしょうか．
-
少しスライドが早かった
---
その場合は質問して下さい．演習の時間はたっぷりとあるので，質問をしないと損をしているのだと思って下さい．
-
話がズレたときでもある程度は話してほしかったです．多少気になってました．
---
失礼しました．気にならないようにしていきます．
-
豆知識も面白かった．
---
$\mathbb{Z}$でしょうか？ たしかにWikipediaでもドイツ語のZahlenに由来すると書かれていますね．
-
まだ特に支障もなく理解できていますが，気を抜かず頑張ります．
---
はい，月曜2限というのがあまりよい時限ではないようですが，お互いにしっかりとやっていきましょう．
-
テストは証明が多いのですね．死にそうです．
---
そんなことでは死なないので安心して下さい ;-) 「証明が多い」と思われるかもしれませんが，皆さんがいままで学んできた数学は全部証明です．例えば「方程式 $x^2-2x+1=0$ を解け」というのも証明です．その点は誤解しないでください．
- その他．もっとくだけた内容もお待ちしています．
-
今日も微妙に雨天⤵
---
ですね．夕方から大雨になってます．
-
湿度が高い
---
空調をドライで運転できればよいのですが，まだそのように調整されていないようです．
-
換気してほしいです．
---
そうですね．休憩のときにお願いすればよかったかもしれませんが，雨が入ってくるのも気になりそうでしたね．
-
毎日早く終わると月曜日の気分的には楽
---
確かに楽ですね．時間割や毎日の予定を組み立てているのは皆さんですから，無理のない生活ができるようにして下さい．
-
ニホンゴガムズカシイ。
---
論理を理解する必要がありますね．どんな言語でも変わりませんが，論理的に思考を行い，それを言語化できることが重要です．ぜひ訓練して下さい．
-
思ってたより人減ってなかったです．
---
そうですね．無理に減らすようなことも行わないので，気にしないで下さい．中間試験が行えなそうになるぐらいになったら，教室の変更を検討します．
-
西食堂が無いとこの後の昼食が非常に不便です
---
西食堂は改装されて，新しい業者が入る予定になっている，と聞いています．おそらく1年ぐらいかかると思うのですが，その間は辛抱して下さい．
-
講義ページでコメント全てに返信してるのが良い！！
---
ありがとうございます．このコメントは私の生きがいなので，大事にしています．
-
阪神が弱いです．
---
スタートはよかったんですけどね．甲子園でなかなか勝てていないのが痛そうです．
-
(=^'ω`^=) ニャー
---
ネコの顔が出せずすいません．Unicodeで出せるものもあるようですが，描いてもらったイラストのようなものはありませんでした．ちなみに，Unicodeで出せるネコの顔は，😸 😹 😺 😻 😼 😽 😾 😿 🙀 のようです．
- 4/11 (1) グラフの定義と次数：数理
- コメントありがとうございました．いただいたコメントとその回答は以下のように掲載されます．
- まず挨拶から．
-
半年間よろしくお願いします．
---
よろしくお願いします．
-
半年間ご迷惑お掛けしてしまうかもしれませんが，なにとぞよろしくお願い致します
---
丁寧にありがとうございます．こちらこそよろしくお願い致します．
-
去年取っておらず，4年ですが今年初受講させていただきます．しっかり勉強していきたいです．
---
4年生の皆さんももちろん歓迎しますので，よろしくお願いします．
- 次は，履修登録に関する質問
-
離散落としているのですが大丈夫ですか？
---
履修登録はできます．シラバスでは離散数学を「前もって履修しておくべき科目」としていますので，グラフとネットワークの学習上困難がともなうかもしれませんが，履修が不可能であるわけではありません．
- 次は，進め方に関する質問や要望
-
最低点 (単位の取得可能な点) は変動するのでしょうか？
---
変動しません．中間試験と期末試験で合わせて120点中60点を取得できれば，単位が取得できます．
-
ちょっと早口で初めて聞く用語を聞いているうちに次へ行ってしまい，わからなくなるので，考慮していただけたらと思います．
---
はい，考慮します．また，速いと感じたら，質問して進行を止めて下さい．そうすれば止まります．
-
講義進度が速いと感じます．全回通してこのペースで進むのでしょうか？
---
量が多い回とそうでない回があります．今日は全体の説明もあったので，多い回だったと思います．量が多くない回のペースは遅くなるかもしれません．
-
伝えたいことを黒板に書いてもらえるとうれしいです．
---
私の口からでている言葉は全部伝えたいことなので，すみませんが，それを全部黒板に書くことはできません．特に重要だとおもうことを取捨選択してメモを取って下さい．
-
教室が狭かった．
---
たぶん次回以降出席者が減ると思うので，ちょうどよくなる見込みでいます．
-
天気のせいか教室が寒く，エアコンも暖房に切り替えられず，辛かった．
---
そうでしたね．いまは季節の変わり目なので仕方ないです．お互いに我慢しましょう．
-
傘立てが欲しい．
---
これは私の力ではなんともならないのです．まず，教室の前は狭すぎて傘立てを置けないと思います．置くことができるとすれば西2号館の玄関付近でしょうか．そもそも西2号館の玄関付近に傘立てはないのでしょうか？ もしあるようでしたら，それを利用して下さい．
-
休憩時間入るのは良い配慮だと思いました．
---
はい，休憩は集中力を維持するのに重要だと思うので，適当なタイミングでいれることにします．
-
評判の悪い授業なので評判がよくなるようにしてください
---
私は，15年後の皆さんからの評判しか気にしていないので，今の評判が悪くてもよいと思っています．その意味で，15年後の皆さんからの評判がよくなるように努力しているつもりです．
-
C棟で配布されている教科書リストに「金曜2限 グラフとネットワーク」とあるのはミスですか？
---
はい，ミスです．私は電通大生協の担当の方に「月曜2限」とお伝えして，変更について承知した旨の返信をいただいているので，電通大生協のミスです．すみませんが，「金曜2限」は「月曜2限」と読み替えて下さい．
-
月曜はつらい
---
「月曜だから」というのは理由にならないので，しっかりと来て下さい．
-
この後に実験が控えてるんですが，ヤバそうです…
---
実験が控えていても何もヤバくありません．大丈夫です．;-)
-
月曜は1限から4限まであるので大変になりそうです
---
それは確かに大変ですね．昼休みにしっかりと休んでください．
-
金曜が休みにできるので月曜にうつったことはむしろうれしいです．
---
そういう視点もあるのですね．金曜日に興味のある講義はないのですか？
- 次は，内容に関する質問
-
有向グラフで $(4, 4)$ という自分から自分への孤がありましたが，無向グラフで $\{4, 4\}$ という辺はないのでしょうか？定義だと，要素数2なのでダメですか
---
ご指摘の通り，無向グラフで$\{4,4\}$という辺はありません．$\{4,4\}$という集合の要素数は1なので，辺であるための条件を満たしません．
-
$\sum_{e \in E}M_{v,e}=\deg_G(v)$ がよくわかんない
---
これは1つの頂点$v$に着目したときに得られる等式です．左辺は行列$M$の$v$に対応する行の成分和です．これが$\deg_G(v)$になることの説明については，スライド48ページを今一度見直して下さい．自分で例を作ってみると，それも理解につながります．
- 他，雑多な質問と感想
-
グラフを復習する良い機会になりました．
---
以後，新しいことしかでてこないかもしれないので，注意して下さい．
-
離散数学の知識を思い出さなければいけないと思った．
---
離散数学は「前もって履修しておくべき科目」なのですが，それほど重く使うわけではありません．集合と論理と数学的帰納法が分かっていれば十分です．
-
離散数学の復習の部分が眠たかった…すいません…
---
こちらこそすいません．
-
分かりやすいです．でも演習の答えぜひ欲しいです…がんばりますが…あ，レポートを出してきけば答えてくれるんですね．ありがたいです．
---
ヒントは出しますが，答えるわけではありません．その点は注意して下さい．私が行うことは，皆さんができるようになることを手助けすることなので，その機会をつぶすようにはしないつもりです．
-
答案の書き方がよく分からないので来週のレポートの添削のときにこう書けばいいなど記入して頂けるとありがたいです．
---
はい，証明には書き方があるので，それについてはコメントをつけます．
-
証明の言葉選ぶの難しいなぁ (′・ω・`)
---
皆さんがどのように離散数学を勉強してきたのか分からないのですが，私の離散数学には「証明は文章」という格言が出てきます．文章なので，書き方がわからないと書けないわけです．もしそれが身についていないようでしたら，今一度離散数学を復習して下さい．もし皆さんの受講した離散数学であまり証明についてやらなかったようでしたら，私の離散数学の資料をご覧ください (リンクは去年のものへ張っていますが)．
-
証明方法がかなり特殊だなと思った．
---
離散数学においては基本的な証明技法です．アルゴリズムの解析でもよく出てきます．ぜひ身につけて下さい．
-
vとVを見やすく書き分けるにはどうすればいいですが
---
私は大きさと書体を変えています．vは筆記体のように，Vは活字体のように書いています．また，Vに対して，上にセリフをつけることもあります．
-
用語の読みが今後改正されることはあるのでしょうか．
---
おそらくありません．それも含めて，困っています．
-
意外と字がきれい．今のところ分かりやすい
---
「意外」というところが気になります (^^)
-
今日はガイダンスを含むため時間がなかったので，次回は演習ももう少しじっくり取り組みたいです．
---
次回以降は演習の時間をしっかりととれるように努力します．
-
内容は難しそうですががんばります
---
はい，簡単なことをやっていこうとは思っていませんので，しっかり復習をして，分からないところがあったらどんどん質問して下さい．
-
面白そうだと思ったけど難しそう．
---
「面白い」と「難しい」は両立するので，問題ありません．がんばってやっていきましょう．
-
演習問題が難しかったですが頑張ります．
---
授業中にもいいましたが，演習問題は出来る限り一人でやらずに，他の人と相談しながら取り組んで下さい．
-
1.7以降が難しいです．
---
分からないときは，とりあえず例を作ってみましょう．そして，自分が道具として持っている証明手法を適用するためにはどうすればよいのか，ということを考えてみて下さい．1.7の場合は1.1と同じようにある行列を考えればよいですが，そのとき，行列の各成分をどのように決めればよいのか，考えて下さい．
-
問題むずかしい
---
むずかしいぐらいがちょうどよいと思っていますので，しっかりと取り組んで下さい．具体的な質問をいただければ，もう少し具体的に回答もできます．
-
眠かったです．
---
途中に休憩があるので，そこでリフレッシュして下さい．
-
おもしろい
---
しっぽは生えていません．
-
おもしろそう．
---
しっぽは生えていません．
-
おもしろそう!! (^-`)b
---
ちょっと，紙に書かれていた顔文字と違うものを書いてしまったかもしれません．すみません．
-
スライドが分かりやすく良かった．
---
スライドだけでは理解できないようになっている可能性もあるので，注意して下さい．
-
学生にとても優しい授業だと思いました．
---
ありがとうございます．あまり優しくしているつもりはないのですが (^^)．他の先生方とはいろいろと進め方が違うので困惑することがあるかもしれませんが，よろしくお願いします．
-
3コースの懇親会行きたかったです．課金すれば4コースの人も参加できるようにしてほしい… (笑)
---
すみません．スペースの都合上不可能です．4コースの先生にお願いして下さい．
-
雨天時テンション ⤵ 晴天時テンション ⤴
---
自然現象なので仕方ないですね．来週晴れることを期待しましょう．
試験・成績
- 中間試験と期末試験により，成績の評価を行います．
- 全体の成績
- 成績 = min{100, 中間試験の素点+期末試験の素点}
- 入学年・学科によって，「グラフとネットワーク」の成績が「数理解析」，「数理解析第一」，「離散数学第二」の成績として報告されている場合があります．注意して下さい．
- 得点分布 (中間試験と期末試験の少なくとも一方を受験した受講者のみ対象)
- 受講者数 (履修登録者数相当) は86で，
90点以上 (S) が15人 (約17%)，
90点未満80点以上 (A) が10人 (約12%)，
80点未満70点以上 (B) が16人 (約19%)，
70点未満60点以上 (C) が6人 (約7%)，
60点未満 (D) が39人 (約45%) です．
- 中間試験と期末試験の少なくとも一方を受験した受講者数は77で，
90点以上 (S) が15人 (約19%)，
90点未満80点以上 (A) が10人 (約13%)，
80点未満70点以上 (B) が16人 (約21%)，
70点未満60点以上 (C) が6人 (約8%)，
60点未満 (D) が30人 (約39%) です．
- 中間試験と期末試験の両方を受験した受講者数は72で，
90点以上 (S) が15人 (約21%)，
90点未満80点以上 (A) が10人 (約14%)，
80点未満70点以上 (B) が16人 (約22%)，
70点未満60点以上 (C) が6人 (約8%)，
60点未満 (D) が25人 (約35%) です．
- 中間試験と期末試験の素点の関係 (散布図)
- 読み方：1つの点が1人の受講者を表します．1か所に何点かが重なってる場合もあり，その場合は色が濃くなってます．横軸が中間試験の素点，縦軸が期末試験の素点．原点を通る灰色の点線よりも左上にいる受講者は期末試験の素点の方が中間試験の素点よりも高い人．右下にいる受講者は期末試験の素点の方が中間試験の素点よりも低い人．青い点線は右上から順に，成績がS，A，B，Cとなる境界を表していて，右上にいけばいくほど成績がよくなります．
- 見て分かる通り，割とばらついています．片方で50点近くとっているのに，全体として不合格になっている人がいる一方で，片方で20点とれていないのに，全体として合格になっている人もいます．期末試験で10点台になっている人が必ず中間試験では30点以上になっていることには驚いています．中間試験の結果が悪くなかったので，期末試験に向けた準備がおろそかになったのでしょうか．一方，中間試験が20点台だった人は，おおむね期末試験の方が高い素点を得ているのですが，60点にちょっと足りず不合格になっている場合が多くなっています．
- 期末試験
- 期末試験問題 (8月10日実施)
- 採点：1問15点満点，合計60点満点
- 得点分布
- 受験した人の数は72，平均点は32.81 (60点満点)．
45点以上 (S相当) が14人 (約19％)，
45点未満40点以上 (A相当) が7人 (約10％)，
40点未満35点以上 (B相当) が10人 (約14％)，
35点未満30点以上 (C相当) が10人 (約14％)，
30点未満 (D相当) が31人 (約43％) です．
- 得点掲示 (辞書順に並べています)
| 0714 | 60 |
| 07516 | 27 |
| 0816 | 30 |
| 12a28 | 27 |
| 13q8a | 27 |
| 1921_k | 39 |
| 50058 | 27 |
| 5m5sz | 28 |
| 79t75 | 3 |
| 8102 | 19 |
| a3t= | 60 |
| ahmzp | 51 |
| akqkc | 48 |
| aq135 | 19 |
| BI37I | 60 |
| BMs12.5 | 29 |
| capti | 30 |
| chino | 39 |
| chstnt | 26 |
| CKDA | 24 |
| colaθ | 35 |
| david | 42 |
| ddskk | 8 |
| DET+1 | 25 |
| dqpsa | 33 |
| EMEm | 48 |
| h0209 | 10 |
| igara | 38 |
| ikustaka | 39 |
| KAZ | 45 |
| kittu | 24 |
| kmsoy | 23 |
| knee3 | 21 |
| kojiro | 45 |
| maitasomaitaso | 48 |
| miaosuk | 34 |
| mikuo | 36 |
| minghai | 57 |
| MossR | 42 |
| moudameda | 40 |
| msx2mg | 33 |
| muise | 33 |
| n13ns | 26 |
| oasis | 51 |
| omega13 | 24 |
| poc | 32 |
| PPPPP | 60 |
| QRQQQ | 18 |
| sapha | 40 |
| sh5ou | 24 |
| shiyou | 35 |
| Tb2CEW | 18 |
| thx39 | 37 |
| ukiy | 44 |
| wiwiw | 29 |
| XEOEX | 33 |
| Z4119 | 34 |
| ZGMFIJG | 48 |
| あかさたな | 41 |
| としきです | 15 |
| もうだめぽ | 38 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評
- 総評：できている問題のでき方と，できていない問題のできていなさが大きく開いていると感じました．できていない人の答案を見ると，勉強の仕方において，本質を捉えられていない気がします．講義で扱った内容と問題で聞かれている内容のどの部分が似ていて，どの部分が似ていないのか，ということをはっきりと理解しないまま，自分の書いている文も理解せずに，答案が構成されているようにみられる場合が散見されました．一方で，できている人の答案はかなりよく書けていて，満点も数人いました．
- 問題1：二部グラフの完全マッチングに関する問題．演習問題8.4と同じ問題．
せめて小問1はできてほしいのですが，そうでもない場合も割とあって残念でした．小問2はHallの結婚定理をどのように使うのか，しっかりと書いて下さい．Hallの結婚定理ではなく，Kőnig-Egerváryの定理を使った答案もありました．正しい場合は満点を与えています．小問3で注意しないといけないことは，「Aを飽和するマッチングが存在し，かつ，Bを飽和するマッチングが存在する」ということと，「AとBを飽和するマッチングが存在する (つまり，完全マッチングが存在する)」ということは違う，ということです．この違いが明確でない答案は減点しています．なお，小問1と2をともに数学的帰納法で証明しようとしている答案もありましたが，正しくありませんでした．この2問を数学的帰納法で解くことは非常に難しく思います．(少なくとも，私はできない，あるいは，やりたくないです．)
- 問題2：グラフの染色数とその最小性を証明する問題．演習問題10.4，10.5，10.9の類題．
よくできていました．正答は「4」なのですが，「5」としている答案がいくつかありました．また，グラフの写し間違いに起因すると思われる誤答もありました．
- 問題3：凸多面体の分類に関する問題．演習問題12.4，12.8の類題．
できている人はかなりきれいに答案を書けています．一方で，どこから手をつけていいのか全く分からなかった，と見られる答案も多くありました．講義でやった正多面体の分類に関する証明をそっくりそのまま書いて，そこから何かを主張しようとしている人がいましたが，それは無理です．そもそもこの問題で扱っている多面体は正多面体ではありません．使われる正三角形の数と正方形の数が定められたら，そこから実際に多面体が作れるところまで確認して下さい．計算からでてくるものは「多面体が存在するための必要条件」です．その条件を満たす多面体が存在することを確かめなくてはならないのです．
- 問題4：選択問題．Aを選んだ人は18人 (全体の25％)，Bを選んだ人は49人 (全体の約68％)．それ以外の人はこの問題に解答していません．
- 問題4A：外平面的グラフの彩色に関する問題．演習問題13.3と同じ問題．
できている人は四色定理を使ってきれいに解けています．思いつけば簡単なので，どれだけ事前に準備できていたのかが重要だと思います．四色定理を使わずに正しく解答するのはちょっと難しいですが，外平面的グラフに必ず次数2以下の頂点が存在することを正しく証明できれば，平面的グラフに対する六色定理の証明と同じように，外平面的グラフの3彩色可能性が証明できます．そのアプローチで正解にたどりついている答案もありました．
- 問題4B：単位円グラフに関する問題．演習問題11.6と同じ問題．
この問題はAに比べて，記述の仕方が難しいと思います．部分グラフとしてK2,2やK1,3に着目するのはあまり筋がよくなく，そうしてしまうと，考えなくてはならない場合が多くなり記述が直感的で不完全になりがちです．そのアプローチで正解にたどり着いている人も多かったですが，上側の2つか下側の3つをどのように配置するべきなのか，というところからスタートして，残りをどのように置くのか考えると，よりスムーズに記述できると思います．
- 中間試験
- 中間試験問題 (6月8日実施，一部修正しています)
- 採点：1問15点満点，合計60点満点
- 得点分布
- 受験した人の数は77，平均点は37.74 (60点満点)．45点以上 (S相当) が11人 (約24％)，45点未満40点以上 (A相当) が5人 (約11％)，40点未満35点以上 (B相当) が10人 (約22％)，35点未満30点以上 (C相当) が6人 (約13％)，30点未満 (D相当) が13人 (約29％) です．
- 得点掲示 (辞書順に並べています)
| 0101 | 35 |
| 06158 | 35 |
| 0714 | 53 |
| 0M16 | 50 |
| 11235 | 33 |
| 1149 | 30 |
| 13479 | 33 |
| 13q8a | 43 |
| 1719 | 45 |
| 37110 | 35 |
| 389cz | 20 |
| 39gts | 22 |
| 3m7oc | 40 |
| 94419 | 35 |
| a4wbg | 40 |
| a628b | 39 |
| bdc13 | 45 |
| BFQRN | 58 |
| BX717 | 60 |
| chstnt | 55 |
| david | 45 |
| DET+1 | 39 |
| dodta | 59 |
| EA-11R | 25 |
| erebos | 25 |
| fosta | 25 |
| h0209 | 34 |
| hokky | 20 |
| igara | 15 |
| ikustaka | 38 |
| inprs | 45 |
| kittu | 45 |
| KK5KK | 30 |
| kojiro | 33 |
| Luxia | 45 |
| MAC-10 | 55 |
| MDAS | 20 |
| meumeu | 35 |
| mkbyy | 30 |
| mnivw | 43 |
| MossR | 50 |
| MUTA | 49 |
| niigo | 48 |
| n---n | 20 |
| NOV59 | 44 |
| POPPO | 30 |
| qrz3c | 33 |
| R7tbM | 59 |
| rinne | 55 |
| sapha | 35 |
| satsumasan | 59 |
| sgt1k | 43 |
| sh5on | 30 |
| stein | 15 |
| syhoi | 43 |
| takri | 35 |
| tbsbt | 50 |
| tofu | 46 |
| Tombow | 10 |
| ukiy | 43 |
| VMEDX | 28 |
| wackq | 35 |
| wiwiw | 54 |
| xenon | 20 |
| YKTR | 35 |
| yohei | 35 |
| z4119 | 45 |
| ZGMFFG | 55 |
| あかさたな | 35 |
| せやかてcdar | 28 |
| のなかです | 33 |
| 比叡ちゃん | 48 |
- 念のためお断りしますが，拝んだり頼みこまれたりしても素点が上がることはありません．
- 講評
- 総評：標準的な「でき具合」だと感じましたが，よくできているわけではないと思います．問題4ができていないのは仕方ないかもしれませんが，問題1から3はしっかりとできてほしい問題でした．
- 問題1：最大性論法による証明問題．演習問題2.6と同じ問題．この証明を数学的帰納法によって行うことは非常に難しいと思います．(少なくとも，私はどのようにやったらよいか分かりません．) また，非常に特殊な場合のみ (例えば，$G$ 自体の頂点数が $k$ である場合のみ) を考えている答案もありましたが，それで不足していることには気づいてもらいたいです．
- 問題2：次数に関する問題．演習問題1.5の類題．(a) は「存在する」が正答ですが，「次数の和が偶数である」ということだけを理由にして「存在する」という答えは導けません．実際，(b) では次数の和が偶数になっていますが，正答は「存在しない」です．「○○が存在する」という命題の証明の仕方について，基本的な理解が問われていると思って下さい．
- 問題3：まず，問題の図の中で $c$ が2つあるのは誤りです．すみません．ただし，大きな誤りではなく，これにより問題の趣旨が変わることもないので，素点に対する特別措置はありません．
問題自身は与えられたネットワークの最大流を求めるもの．演習問題6.3，6.7の類題．そもそも流れが何であるのかわかっていない答案がいくつかありました．勉強して下さい．もう1つの注意ですが，カットの容量は弧の容量を足し合わせることで得られます．そこから出ていく流量の和ではありません．
- 問題4：完全マッチングの存在性に関する問題．演習問題4.11と同じ問題．その場で考えて正解にたどり着くのは難しいかもしれません．演習問題にちゃんと取り組んでもらえるとありがたいです．
- 過去の試験問題 (注意：内容や説明法，試験範囲は変化しています．)
公式シラバス
こちらをご覧ください
履修上の注意
『グラフとネットワーク』は，『数理解析』(情報・通信工学科：新)，『数理解析第一』(情報工学科：旧昼)，『離散数学第二』(情報通信工学科：旧昼) の読替科目です．
これらを履修した人 (つまり，単位取得した人) は『グラフとネットワーク』を履修できません．
スケジュール (予定)
- 4/13 (1) グラフの定義と次数：数理
- 4/20 (2) 道と閉路：数理
- 4/27 (3) 木：数理
- 5/4 みどりの日 のため 休み
- 5/11 (4) マッチング：数理
- 5/18 (5) マッチング：モデル化
- 5/25 (6) 最大流：数理
- 6/1 (7) 最大流：モデル化 (1)
- 6/8 中間試験
- 6/15 (8) 最大流：モデル化 (2)
- 6/22 (9) 全域木：数理とモデル化
- 6/29 (10) 彩色：数理
- 7/6 (11) 彩色：モデル化
- 7/13 (12) 平面グラフ：数理
- 7/20 海の日 のため 休み
- 7/27 (13) 平面グラフ：モデル化
- 8/3 (14) ラムゼー理論
- 8/10 期末試験
過去の講義
注意：内容や説明法は毎年少しずつ変わっています
[Teaching Top]
[Top]
okamotoy@uec.ac.jp
