香川大学全学共通科目 2005 年度 夜間主
共通科目 数学
グラフ理論とネットワーク最適化 (Graph Theory and Network Optimization)
三原麗珠 (地域マネジメント研究科)
2単位, 第1学期前半, 火曜 6, 7 校時 (1800-2110), 三原研究室
グラフとネットワークの理論をみなさんといっしょに学んでいきたい． 《グラフ》とは有限個の「点」とそれらを結ぶ何本かの「辺 (枝，線)」からなる 数学的オブジェクト (対象) である． グラフはたとえば電気回路，コンピュータや人のネットワーク， 道路網や航空路線網を表現できる．携帯電話の中継点を「点」とし， 混信可能性のある中継点の対を「辺」とするグラフを考えることで， 中継点への周波数割り当て問題をあつかうこともできる． グラフの「点」や「辺」に，容量，長さ，コストなどを表す数値を付与したものを《ネットワーク》という． たとえば「辺」が地点間の道路を表すとき，その道路の長さや通行所要時間などを考慮できる．
現実問題をグラフにかんする数学問題に翻訳し，その数学問題を解くことで解決できることは少なくない． カーナビゲーションシステムは，目的地までのもっとも近い (あるいは早く着く) 道順を答えてくれる．これはグラフ理論 でいう「最短路問題」を解いていることになる． 携帯電話の中継点への周波数割り当ても，グラフの「彩色問題」によって考えることができる． この授業では，グラフやネットワークにかんするさまざまな問題を考えることを通して， 現実問題の解決へのヒントを得ることにする．
情報科学総論，情報システム，経済学概論．交通・運輸にかんする地域科学系の科目．
前提科目はない．高校数学とはだいぶちがうため，高校であまり数学を学んでいなくても問題ない．
集合論と (ネットワークをふくむ) グラフ理論の概念を正確に理解すること． 現実の問題や情報科学の問題をグラフ理論の問題に翻訳できるようになること． グラフ理論の問題を解くアルゴリズムを簡単なケースに適用できるようになること． 数学的帰納法をはじめとする有限数学の手法をマスターすること．
教科書にそってすすめ，適当なところで演習問題 (宿題) を与える．授業では教科書を参照しつつ，断片的に板書を用いる． 細かな証明に深入りすることは避け，鍵となる概念を直感的に理解させることを重視する． 学生は授業内容を参考にしながら教科書を読んだうえで，演習問題を自習していく．
中間試験と期末試験による．期末試験のウエイトが高い．ほとんどの問題は演習問題 (宿題) の類題を予定．
教科書の以下の章をカバーする．カッコ内は予定講義回数 (週に2回と数える):
中間試験は5月10日の予定．
以下のほか，教科書の文献案内を参照:
火曜 2110-2150．前日までにメールで，あるいは当日の授業の直前直後に予約のこと．
みなさんの学問への熱意に応えるため，レベルは落とさないようにしたい．かなり難しいだろう． 一週間に2コマの授業だから，学則によれば必要な自習時間は週あたり8時間となる． その程度の自習はするという前提ですすめる．
本文中の例題は(特に外すもの以外)すべてマスターしておくこと． 練習問題は解き方の分からないものや解答の書き方の分からないものがあるだろう．正解を理解すること． 「追加問題」とある問題のほとんどは，練習問題よりも初歩的な問題である．
テキストのどの部分を省略するかなどの情報もここに載せる．
●2頁3行目の A= は消した方が分かりやすい．その Aは 1行目の A とはべつもの．
●7頁の反射法則以下 i から v までの性質．実数上の等号 =，不等号 ≧，> のそれぞれが
これらの性質のどれをみたすかを考えてみよう．
●8頁3行目 b のかわりに別の文字 x などとしたほうがいい．b は集合 A の具体的な要素として登場するので．
●9頁4-5行目．「点対 ek=(...) である辺」というのを
「(通常は，点対の集合 ek={...} あるいは点対 ek=(...) で表される) 辺」
と修正した方がいい．
-無向グラフのばあいは辺を点対の集合 {v, v'} で記述し，
-有向グラフのばあいは辺を点対 (v, v') で記述する
のが自然である．ただし，点対集合あるいは点対だけで辺を記述するかぎり，
多重グラフは表せない．多重グラフを表すには，そのぞれの辺にどの点対が対応しているかを
記述する関数 f: E→V×Vを導入して G=(f, V, E) とする方法が考えられる．
●9頁下から6-7行目の記述は，集合 {v, v'} をふたつの点対の集合 {(v, v'), (v', v)} と同一視したときの話である．
●11頁完全グラフの定義．「すべての異なる点の対 (vi, vj) を辺とする単純な無向グラフ」
とした方がいい．
●18頁「ペアノの公理」から19頁「数学的帰納法」の直前までは，難しかったらこだわらなくてもいい．
数学的帰納法の正当性の証明も同様．
●20頁から．§1.7 は最初のふたつのパラグラフのみ現段階では理解すればよい．残りは，もし必要になれば
そのときに指示する．
●107頁．証明は授業では省略した．できれば読んだ方がいい．
●109-111頁．「2連結性」にかかわる 109頁-110頁の3段落までと111頁の2行目から8行目までは
現時点では省略する．
●112頁．証明の第2パラグラフ以降は読まなくてもいい．
●114-115頁．「2SAT の別解法」の項目は省略．115頁以降の「有向木」は省略しないので注意．
●122-123頁．「集合 Q」とあるものは，「リスト Q」と考えた方がいい．要素の順番が重要だから．
特にステップ 2(a) で「w を Q に格納し」とあるのは，「w を Q の最後に格納し」と読むべきである．
●130頁 地図の彩色の話は，飛び地がない場合を考えている．
●133頁 8行目「一般に」以降の最大次数と彩色数の話は軽くあつかう．
●135頁 彩色数の上界の証明は読まなくてもいい．
●135-6頁 5色定理の証明は読まなくてもいい．
●143頁 十分性の証明は読まなくてもいい．
●148頁 ダイクストラ法の正当性の証明は読まなくてもいい．
●149頁 平面上の巡回セールスマン問題では完全グラフをもとにしたネットワークを考えていることになる．
●149頁 最後の段落 通常，ハミルトン閉路は一般の無向グラフ (辺長なし) について考えることが多い．
すべての点を一度ずつ通る巡回路である．
●151頁．ランダムに発生させた訪問順序を考慮する「ランダム法」にたいし，すべての訪問順序を発生させる
「完全列挙法」もある．この方法は訪問する点の数がちょっと大くなると (たとえば25くらいでも) 何十万年とか
宇宙の年齢を超えるとかいった膨大な時間がかかる．
●152-156頁 この部分は軽くあつかう．授業で NEAREST_NEIGHBOR, INSERTION, LOCAL_SEARCH はざっと
触れる程度．
●163-166頁 「無向ネットワーク上のフロー」以下 5.2 節の最後までは省略．
●167頁 「一般化」の外れた「マッチング」「最大マッチング」は，すべての aiと bjが 1 のとき
のみ使っているようだ．
●172頁 結婚定理はマッチングを対象にする．一般化マッチングではない．(5.17) が必要条件であることはすぐ分かる．
女性3人がいて結婚してもいいという男性が2人しかいなかったら溢れる女性がいる．
●174頁 2-3 行目 集合の表記があいまい．「……与えられたとき，すべての i について si∈ S i
となるような互いに相異なる n 要素の集合 {s1, ..., sn} は存在するか？」
●174 頁 ケーニヒ・エガヴァリイの定理も一般化されていないマッチング問題にかんするもの．
●176-182 頁 5.4節は省略する．
試験は課題 (本文中の例題も含むことを忘れずに) を理解していれば正解できる問題を出題する． 理解することに重点を置くこと．用語はできるだけ覚えるべきだが，覚えにくい公式などを無理に 覚える努力はしなくてよい．覚えにくい公式や定義はできるだけ問題自体に載せる． 用語などが分からないときは質問すれば試験監督が説明するばあいもある． (試験はテキストの持ち込みを許す部分と許さない部分の2部に分けてやるつもりだったが，その必要は ないようだ．テキストは見ないでやってもらう．) 配点は中間試験は40点，期末試験は60点．
中間試験では以下の課題に特に注意: ●1章 追加問題 1, 練習問題 3ix (ド・モルガンの法則), 15, 16ab. ●4章 追加問題 1-7 (すべての追加問題), 練習問題 7, 9, 14. 練習問題 7 については，深さ優先だけでなく幅優先探索もできるように． 練習問題 9では，出発点と終着点が異なるばあいの一筆書きのできる条件に注意． 練習問題 14 では点の数や面 (領域) の形などが違う場合も扱えるように．
期末試験では以下の課題に特に注意: ●1章 練習問題 15 (中間試験の範囲からの出題はこの練習問題にかかわるものに限定)．たとえば (¬q)⇒(¬p) とか ¬((¬p)∨q) の値が p, q の値に応じてどう定まるか． ●4章 練習問題 17ace. ●5章 練習問題 1 (授業でダイクストラ法を説明したときの小さなネットワークへ適用). ●追加問題 (中間試験の範囲よりあとの分すべて).
中間試験の個人別成績は以下の通り (大問題のなかのプラス記号は省略; 満点は 333+6+3345+6+4=40点):
試験前にだいぶ情報を与えたので，9割である36点以上を半数くらいはとれると思っていたが，ひとりだけだった． 一定の努力の跡は認められる．7割である28点を合格点の目安とする．期末試験は中間よりやや難しくなるだろう． 各問題にたいする講評は以下のとおり:
期末試験の個人別成績は以下の通り (満点は 6+10+10+10+10+14=60点):
講評．問題 4 (iii) で説明不足があった．問題5では U={a, c, d}とすればいいのだが，U={a, b, c, d}という答がほとんどだった．それでも正解．
総合点は 96, 94, 92, 87, 83, 78 点．規程どおりの点数で区切って，秀3人優2人良1人とした．ただし「秀」の適用がない学年の「秀」は「優」に読み替え．高校生は成績はつかない．
予想通り授業自体はむずかしかったようだ．まともな2単位分の内容を教えるために，ハイレベルな内容を かなりのスピードでやったのが大きい．はじめて聞いたときチンプンカンプンだった内容も，その場で 質問して確かめたり，あとで課題とからめた説明を受けたりして，自然と理解して行ったようだ．図で説明 できることは時間さえかければかなりスムーズに理解してもらえた一方， 記号の読み方が絡むものは得手不得手があるようだった． ほとんどの学生にとって，受講科目の中ではよく勉強した科目だったようだ．今回は， 「勉強していないと試験でほとんど点数を採れない，しかしある程度やれば容易に高得点が採れる」 という三原の科目の特徴の後半部分が証明された形になった．
以下は評価決定後にメールで送ってもらった感想．到着順に掲載．
Akino: 秀をありがとうございます〜！うれしいです☆ 先生の授業は難しいって聞いたし、数学苦手だったので、最初はいやだなぁと思ってたけど、 中間テストの直前に補講してくれて、テストも３４点とれて、そこからこの授業が楽しくなりました！ 期末テストも授業中にはわからなかったことが、あとからわかってきて、６０点とれてほんとうれしかったです。 まぁほかの普通のテストでは考えられないようなテスト風景でしたけど、最後まで楽しかったです！ 授業の内容は、聞いてるときは難しく感じられたけど、テストしてみると、そんなに難しいって感じではなかったですよ！ ありがとうございました☆★ Hiromi: 数学は、共通科目なので絶対にとらないといけない単位だったので、ほぼ強制的に履修をしなければなりませんでした。 去年、先生のゼミをとっていたということもあって、単位はくれるかな…という軽い気持ちで受けてましたが、授業は さっぱり意味が分からなくて、かなり苦戦しました。毎回、21時を過ぎてまで授業をしてたし、補講もあったし、とに かく大変でした。なので、テスト勉強はかなりしました。ホントに勉強しました。でも、そのおげで期末は満点でした し、結果、秀をもらえました。 先生の授業は大学の勉強…って感じで、これからは役に立つか分からないですけど、ためになった気はします。少しの 間でしたが、ありがとうございました。 Nao: 最初、授業をうけたさいは、単位をとるのは不可能だ！とまったく自信を持てなかった。受講人数も少人数だったので、 あせりをかんじていた。しかし３回目以降から研究室での受講となり、親身になって先生が教えてくださったので、わ からないところでもすぐに聞いて、徐々に理解することが出来た。最初におどしのように言われていた『全員落ちても おかしくない』とゆう言葉が焼き付いていたため必死になって勉強した。授業内容はチンプンカンプンの世界だったが、 先生生徒ともに、和気あいあいとしていて、マジメにやるときは、先生がしっかりかためてくれていたため、ケジメを つけて授業を行うことができた。勉強を楽しみにいっていたのではなく、先生のキャラクターを楽しみにして行ってい たのがほとんどだった。 Mikiko: 私はもともと数学に苦手意識がすごくあって、 始めはテキストの1ページも理解できませんでした。 簡単なこともものすごく複雑に書いてる気がして 読むことも困難。 でも、単位をなにがなんでも取らなきゃだし、 1年の時から敢えて避けてきた三原先生の授業に 合格できたら絶対達成感はあるなと思って受講しました。 授業は案の定レベルが高いものだったけど、 テスト前の補講、授業後の指導、ホームページでの 情報などから、一つ一つ消化していくことが出来ました。 結果、合格した時は達成感と安堵感と単純に嬉しい気持ちと、 色々な感情があって、その日の夜はすごく燃えました（仕事にね）。 授業はあれだけ難しいものだったから、少人数で 本当によかったと思います。個人的に質問もできた し、答えてもらえたし、何よりみんなでの雰囲気が 良かった。 今までで一番、授業と先生と一緒に受けた友達とを 近くに感じられた授業だったと思います。 ありがとうございました。 Masaki (高校生): 初めて大学の授業を受けてますます大学に進学したいと思いました。授業の内容は僕が最も好きな数学だったので退屈は しませんでしたし、先生と大学５年生（♂）のコンビはツボでした。（笑）とてもおもしろかったです。授業を受ける人 が少数だったので緊張もせず（初めての授業をのぞく）みんなと仲良くなれたのでよかったです。
Lecture: 1800-1940, 1950-2115. E22教室．受講者 1時間目 8 人; 2時間目 4人 (男2女2，ATFK，5年生4年生4年生高校2年生．) 茨木1章 1.5節まで． ●教材提示装置がまともに動かなかったので，板書を多様． ●導入のための例は，航空路線図，ケーニヒスベルクの橋 (139頁)，オイラー公園 (久保, 松井 p. 1, p. 17)など． ●用語がたくさんでてくる．太文字 (ゴチック体) の用語をすべて理解し，それらを目にしたり耳にしたときに それが何か思い出せる程度には覚えておくこと．なお，文献によって用語の意味にずれがあるので注意． ●「課題」は，このページの上の方に載せる． ●「テキストへの訂正・コメントなど」は，このページの上の方に載せる．どのセクションを省略するかなどの情報も． ●授業後，出席を重視して欲しいという5年生．出席しただけで単位を欲しいというから，これは出席を単位取得の 十分条件として欲しいということだろう．しかし，その人はちゃんと勉強したいとも言うので， 出席を必要条件 (一度でも欠席すれば即「不可」) にしてくれていいということかも． ●しかし，教養科目らしからぬ学生構成だ．大学生 3 人は，卒業要件の共通科目の単位が必要な学生ばかり． ●最初の時間はガイダンスの後， 1.3 節まで (集合，写像，関係) を急いでやった． 言葉の定義ばかりで，深く考えるような内容ではなかったが，それでも「早すぎる」という苦情あり． 授業ではノートを取るのはあまりすすめない．ほとんどのことはテキストに載っている． 授業では直観的な理解を得ることを優先し，自習で時間をかけてきちんと理解するのがいいだろう． ●2時間目はグラフの用語と命題と述語．グラフについては，視覚的なイメージをしやすいし， 言葉も日常のものに近いこともあって，理解出来ている感じ．完全グラフK5で辺を ひとつ書き忘れたら，指摘してくれた． ●立方体のグラフと同形な平面描画をしめしたら，「どうしてそれらが同形?」という表情． 点の対応を説明したら納得した模様． ●命題論理では p が偽のとき「p ならば q」が自動的に真となるのを不思議そうにしていた． 数学における「ならば」という言葉の使い方がそういう約束なのだと受け入れればいい． 少し納得出来る説明としては，以下のようなことを言った． 仮に僕が東京にいなくてあるひとに会わなかったとする．彼女に 「東京にいればキミに会っている」という言葉を僕が言ったとすれば， それをウソだとは言い切れない．なぜなら「東京にいれば」とう仮定が事実ではないのだから． ウソだと言い切れないなら，「真」ということにしておこうと．まあ，何人かは頷いていた．
Lecture: 1810-1945, 1955-2110. 問題演習 2110-2135. E22教室．受講者 6人 (先週の4人ATFKプラス2人SE) 茨木 1章 1.6節 ，1.7節 (最初の2段落)，4章 4.1節 (一部省略)-4.2.1 節． 2110-2135 練習問題 1章 1, 3. ●4.1節は目立った定理もなく，目標が分かりにくい節である．とりあえず連結や強連結，カットセットや木 の概念を理解し，与えられたグラフの連結度を求められることを目標とする． ●4.2節の深さ優先探索，幅優先探索は読んで字のごとくである．書かれているアルゴリズムは 分かりにくいかもしれないが． ●授業開始が10分も遅くなった．次回からはきちんと時間通りに来るように．でないと遅れた分終了時刻を遅く せざるを得なくなる． ●先週来ていた 4年生ふたり，買ったばかりのテキストを袋に入れたまま持って来る． 先週の授業以来，勉強しなかったというわけだ．そんなことでは単位取得は危ない． 自習を週に8時間はするのは前提とシラバスに書いてある． ●かなり遅刻して先週来なかった学生が二人来る．2コマ半の遅れを自力で取り戻すのは無理では ないかと思ったが，テキストも持って来たので何も言わずに受け入れた．とうぜん知っているだろうが， 私の夜間主授業は合格率21パーセントという実績がある．必死でテキストを読んで勉強しなければ 簡単に落とすだろう． ●授業の直後に希望者向けに補講を実施．学生はあまりうれしそうではなかったが，次週の次はもう試験だ． 少しでも練習問題をやる時間を取りたい．本来は練習問題は自分でやるべきだが，質問もあるだろう． オフィスアワーとしてできるかぎり授業後の時間に対応するので，利用するといい． 本日の補講には先週の4人が残った．残りの2人は自力で完璧にやれる人たちなのだろう． ●補講のときは，学生が互いに教え合っていた．高校2年生が大学上級生に教える場面も． ●いうまでもなく，練習問題だけでなく上に「課題」として挙げたすべてを理解することが 試験対策になる．本文中の例題もふくまれるので注意． ●人数が少ないので三原研究室でやろうとH から要望あり．合格率を上げさせる心理的効果でもあると思ったか． ところが二時間目に移動するのが面倒になったようで，もういいと言い出す． けっきょく研究室でやるのは来週からということにした． ●いまごろテキストのどの章をやるのか聞く学生が複数．シラバス読んでないのか． ●「先生はけっこうスケベじゃないですか」と男子学生 A．ぜんぜん当たっていないと思うが， たしか「まあね」と返事．真実のほどは去年演習とってた女子学生にでも聞いてくれ． べつにエッチなことは一切発言していないのだが，どうしてそう思ったのだろう．
Lecture: 1810-1940, 1945-2035. 問題演習 2035-2200. 三原研究室． 受講者 6人 KETA, 遅れて F (風邪)と S (求職活動). F が21時頃帰宅した以外は全員最後までいた． 茨木 4章 4.2.2-4.3節． 練習問題 1章 4a.ii, 5, 6, 8, 13, 15b, 16a. ●本日から三原研究室で授業をする．第一週と第二週のいずれの授業も無断で欠席した学生は， 履修意思のないものとみなす．自力で二週間分 (授業4コマ分)の遅れを取り返すのはもう無理だと思うので． さすがに今週初めて来る者はいなかった． ●中間試験の情報はこのページ上の方を参照． ●4章の課題をやる時間がなかった．補講をしてくれという希望はあった． メールで連絡するから授業のあとにメールを送るように頼んだつもりだが，だれもメールを送ってこない． どうなってるんだ．早く送るように．それにしても来週は休みだらけだというのは後になって気づいた． [5/3 火曜までに連絡あり．] ●オイラーの一筆書き定理を知っていれば，一筆書きができるかどうかが一瞬に分かる． 中高生の弟や妹に自慢出来る． ●オイラーの公式 (4.3) は正四面体，正六面体などで「頂点の数-辺の数+面の数=2」となっている ことの一般化と考えられる．グラフの外側の領域を数えるのを忘れずに． ●双対グラフは定義が抽象的でぽかんとした表情の学生．しかし，例を見れば意味は分かる． はじめに定義を見たときに何もイメージがわかないのは仕方ない．しかし例を見てイメージがつかめた後に 定義を見てもまだ意味が分からないとしたら，そこにある用語をちゃんと理解出来ていないということだ． 理解出来ていない原因は数学的抽象力が弱いか，努力不足かどちらかである．よほど時間をかけていないかぎり， 後者と思う． ●5:45ころ僕が階段を上っているときすぐ後ろを歩いていたのが前回から出席した E だった． どっかで見た感じはしたが，ほかの研究室に向かっている人なのかと思っていた． 高校生の K はすでに研究室前で待っていた． ●E は少しは自習したらしくカットセットなどについて質問．講義ページに僕の感想が載っていますねと言っていた． ●「授業を聞いたら分かるが，本を読んでもなかなか分からない」と E．まあ，数学の本はたいてい そんなものだ．グラフ理論のしっかりした本で，しかもすらすら読めるという本もあるかもしれないが， 残念ながら自分は見つけられなかった．授業に出ている人で週8時間の自習を前提にしているわけだから， そうでないひとがついて行くにはもっと時間をかけないと無理だろう．時間のないひとはとりあえずは 課題だけはやることだ． ●後ろの席に座って眠そうな顔して携帯メール(?)やってる H，やばいぞ．去年の演習は週1コマのところを 2コマ分近くかけてやったのでのんびりやれたが，今回はもともとの週2コマという違いがある．忘れないように． ●同じ机に向かう女子学生のお化粧の濃さは同じ程度になる法則．ちがってるっけ． 濃い方のグループの E は誰かに似てると思ったら，薬学をやっていた昭苑に似てるかも． 多度津に本部がある少林寺拳法の宗由貴には……似てないか． ●積んであった本のなかから『女から口説く101の恋愛会話』(中谷彰宏 著)を見つけて「ストッキング脱いでもいい？」とか 読むはじめる A．続きは授業記録に埋もれさせるのはもったいないので， コンテンツの相互提供協定を結んだブログに載せてもらった: http://theorist.blog6.fc2.com/blog-entry-13.html 高校生は読むな． ●なかなか理解してもらえないと思ったら，直積 A×Bをかけ算とかんちがいしていた学生たち． これは第一週目に出した課題だ．とうぜん自習していて定義をチェックしているべきなのに．勉強不足． ●部分集合を求める問題はさすがにルーティンかと思ったが，そうではないようだ． 空集合を要素とする集合と空集合とは別物だといった中学生のときに習っておいていいはずの話題あたりで やたら盛り上がっていた． ●帰納法による証明もなかなか理解してもらえない．a(1) から a(k+1)までの和は， a(1) から a(k) までの和に a(k+1) を足したものだというのがなぜ分からないのか． 1+2+3+4+5=(1+2+3+4)+5 つまり 1から5までの和は1から4までの和に5を足したもの と言っても分からないだろうか．それだけのことなんだが．あと，帰納法自体を把握していない 学生もいた． ●まあ，こんな調子だから全員単位落としても仕方ないかもなあというのが率直な感想だ． できれば合格者は出したいのだが……．まだチャンスはあるけど，最後に落とされても恨むなよ．
1640-1730 (SK), 1730-1950, 2005-2020? (SKA), 2020?-2130 (SKAE), 2130-2150 (SAE), 2230-2320 (AE). 1640-1730 (SK): 1章 練習問題 1, 3, 4a. 1730-1950 (SKA): 12, 15ac, 16b. 2005-2020? (SKA): 4章追加 1, 2. 2020?-2130 (SKAE): 4章追加 3, 4, 5, 6, 7. 1章追加1. 4章例題4.1. 練習問題 1, 4, 7, 8, 9, 10, 12, 14. 2130-2150 (SAE): 1章 練習問題 16a. 2230-2320 (AE): 1章 練習問題 3, 16b. 4章追加 1, 2. ●「p ならば q」と「pでないあるいはq」が同値であることをまた「うそとは言えない」で説明． ●帰納法はなかなか理解に時間がかかるようだ．必ず試験に出すと言ったら，練習問題 16a か 16bのどちらかに いま決めてそれを出すことにして欲しいと学生．「分かった．決めた」と僕．でもどちらか，あるいは 例題 1.7 かは教えない． ●カットセットやカットはけっこうむずかしい． ●連結度の概念は難しくないが，求めるのはやや面倒だ． ●強連結成分を求めるのは簡単と学生はいうが，少し迷う例題をやってみた． ●出発点と終着点が異なるばあいの一筆書きのできる条件 (4章練習問題9) に注意． ●深さ優先探索，幅優先探索は分かるというので，特にやらず．試験には出題するつもり． 人によって解答が違って来ないかと聞いたのは S だっけ．その通り，するどいじゃん． ●4章の追加問題はおおむね簡単と学生．立方体の平面描画とか双対グラフを作る問題とか．こういう問題を出してくれと． ●4章練習問題1や14は少しむずかしいので試験には出ないだろうと高をくくる学生たち．でも， 1の方は証明の一部に出したい部分があるし，14はオイラーの公式をうまく使える問題ということで魅力がある． ●「先生のホームページ見ました．エロいじゃないですか．女の子紹介してあげるから，単位ください」と 入室して来た学生．たぶんリンク先と混乱しているんじゃ．その学生の問題発言やそれにたいするなかなか いい感じの周りの反応は，ここには詳しくは書かない．「オナニー」(今日は保健の補講じゃないだろ！) とか， 「わたし，これでも C カップあるんですよ〜．触れば分かりますよ」 (自分は A, B, C とか言われても， この順に大きくなるのか小さくなるのかさえつねに忘れるので，説明がないと分からん！) とか， そういう言葉が飛び交う夜の研究室だった．怪しすぎる．そういえば途中で心配して (?) 研究室を覗きに来た 正義感溢れる好感度高い青年風 (ただし子持ちだったと思うが) の助教授もいたな． ●授業だったらこちらの表現の自由 (編集権) を主張して弾圧 (相手にしないでさっさと先に進める) したであろうエロ発言 が多かったが，きょうは補講だ．この補講は自習に替わる部分なので，主体は講師ではなく学生であろう． しかも参加は学生の自由意思にゆだねられている．苦情もないうちから教員の立場を利用して安易に言論弾圧をするのは 考えものだ．表現の自由が大学という場に取ってどれだけ大切かということを教える教育上の機会を逃すことになる． いずれにせよ，みなさん大人の反応をしめしてくれた．大人の反応ねえ……． さすが社会人学生だけのことはある． ●「せんせーはどんな女性がタイプですか？ たとえば芸能人で言ったら？」とか男子学生が聞いて来た． ごめん，芸能人をほとんど知らないの．でも，だいぶ以前たまたまドラマで見た，稲森いずみはいいなと思った ことがある．好きな彼女に似ていたからね．ちなみに授業一覧ページの上に載ってるビーバーの一匹はいずみという名前だ． 今日来た学生のうち3人が稲森いずみに「よく似た子を知ってる」から紹介するという．それぞれべつの子のようだ． ホンモノがいいに決まっているが，まあいいだろう．とりあえず写真を用意しておくように．
1315-1500, 1520-1610 (TF) 1章追加 1, 練習問題 3ix, 15, 16a. 4章追加 1-7, 練習問題 7, 9, 14 他，例題 4.1. ●5/5に出席出来なかったふたりのための補講．日曜日あたりふたりで勉強したとのこと． 練習問題の一部はちゃんとやっていなかったが，それ以外は勉強した跡は見られた． ●ソース焼きそば味のベビースタラーメンとかマカダミアナッツのチョコとか食べたりしつつ． ●クークー寝てしまった H．写真にでも撮ってやりたい表情だったが，怒られると怖いのでやめとく．
中間試験 4.3節まで．1810-1850. 少しヒントを与えた． Lecture: 1900-1955, 2000-2115. 三原研究室．受講者 6人． 茨木 4章 4.4節. 5章 5.1.2節 (146頁まで)． ●図 4.25 は左上から順番に (左の列で始まり右の列で終わるように) 色を塗って行っても4色で済むので， アルゴリズム COLORING の適用例としてはいまひとつおもしろくない． ●図5.2は KRUSEL と PRIM の説明にはやや大きすぎたので，右上の部分だけを利用． ●ケニーヒスベルクの橋をあつかった「ひとやすみ」をやらないのかと E．それはすでに オイラーの定理のところで説明したのだ． ●「KRUSELでどうしてそれで最小木が出来るのか」という質問が A からあった． 145 頁に説明はあるのだが，できるだけ重みの小さな辺を最初に考えて行くところあたり， 感じとしては分かるんじゃないか． ●PRIM は最初のうちは分かりにくいこともあって，A が「やめましょう」と言った． しばらく続けているとたいして難しくないことが分かったはずだ． ●きょうは学生も真剣で教えやすかった．短い休み時間以外，ほとんど雑談もなかった． 休み時間は S と研究室外のソファーに座ったり，そこに E がやってきてカップコーヒーを もらったり． ●H&Fはこの時間もポッキーなど食べている．僕が学生時代はこれを男女で一緒に食べる遊びがあって， タイの学生との交流パーティーといった，まじめな (?) ボランティア活動なんかでもやっていたものだ． 「やろうか？」と言っても，H も F も乗ってこないので，自分でとって食べた． スナックなどの飲み屋にはなんでポッキーが置いてあるんだろうと飲み屋勤めの学生に聞いたが， 理由は分からないようだった． ●まあいい．グラフ理論の問題も，うまく選べば飲み屋のおつまみ代わりになるかもしれない．
Lecture: 1820-2045, 2055-2100. 補講: 2110-2145. 本日を含めて，あと3日しか講義がない．時間的に厳しいのに集まりが悪い． K, A, F は1820までにはそろい，席を外していた E と就職活動で大阪(?)行って来た T は1830ころ， S はそのあとしばらくして来た． 茨木 5章 5.1.2節 (147頁から)-5.2節． ●テキストにあるが授業では省略する部分が今日は多い．「テキストへの訂正・コメントなど」を参照． ●ダイクストラ法の説明に以下を利用: 久保幹雄, 松井知己. 組合せ最適化 [短編集]. 朝倉書店, 1999, 2章． ●ダイクストラ法にかぎらないが，アルゴリズムを説明するのはむずかしい．その場ではとりあえず理解出来るような， 直観に訴える説明をすることはできる．だが，それだけではテキストの記述をあとで学生が読んだとき，数学が相当出来なければ ほとんど分からないだろう．あとで学生がテキストの記述を理解出来るようにするには，書いてある数式なども 参照しつつ，ゆっくりと説明しないといけない．が，それを厳密にやりすぎると学生はフォローできなくなる． しかも，2単位分の授業をするためには急がないといけない．なかなかそこあたりの調整はむずかしい． ●はじめて授業で聴いて分かった気になったとしたら教え方がいいのだろう．しかし，なんとなく分かった気になっても， 自分でやってみると分かっていないことに気づくものだ．何度か自分でやってみて，それで途中に睡眠を挟んで 頭を整理して初めて，アルゴリズムを自然な考えとして受け入れられるようになって来る．はじめて勉強した直後に 分かった感覚は重要なファーストステップだが，それだけではほとんど頭には定着していない．集中的に考える時間と しばらく離れる時間が必要だ． ●アルゴリズムを「なんで[テキストでは]こんなに分かりにくく書くんですか？」と S． 「最終的にはコンピューターが読めるように書かなければならないからね．そこの書き方はコンピュータープログラムではないけど， それに近い．」コンピューターの気持ちを少しは理解出来たかな． ●ハミルトン閉路の非存在をしめした2部グラフの例は，飲み屋のパズルにいいかも． ●巡回セールスマン問題の完全列挙法の計算量の組み合わせ的爆発については，久保幹雄, 松井知己の7章にある． ●「最近近傍法」という言葉を何度か発音させて喜ぶ学生たち，特に AとEがにやにやしている． 何がおかしいのか分からなかった．もしかして「金棒」とか思ったのか？ いや，きっとなにか他の理由があるのだろう． その直後に出て来たより効果的な欲張り法の「挿入法」で E が吹き出したのは分かった気がするが． いずれにせよ，そこらの話題は参考程度のあつかい． ●フロー追加法も，テキストを後で学生が見たときに読めるようになっているような説明の仕方をするのは むずかしい (時間がかかる)．絵で理解してもらうだけなら速くて簡単なのだが． 課題の補講: 4章追加 8, 9; 練習問題 15, 17. 5章練習問題 1. ●スーパーマーケットが閉まってしまうという F の苦情にも拘らず強行．H も就職活動で疲れたと 言っていたが，まあ日曜日未明のメールでも予告してたわけだし，どうせ疲れてるなら ちょっと延ばしても変わらないだろうと強行． 補講自体はすんなり気持ちよく進んだ．課題くらいは自習をした上で受けてもらいたいのだけどね． ●授業前に高校生が図形の面積比を求める問題を持って来た． 「正三角形の内接円に内接する正三角形が描かれている． ただし両方の正三角形は上に頂点が来ている．さて，小さな三角形の面積と大きな三角形の面積の比は？」 とりあえずその小さな三角形をこういうふうに動かすと答は瞬間的に分かる．(図でなく言葉で問題が 与えられた方が正解が得やすいという，おもしろい問題だ．) しかし，あれはそういう答が欲しかったのだろうか．内接円の半径と外側の三角形に外接する円の 半径を求めるやり方を教えるべきだったか．それをやるにしても，こういう補助線を考えて小さな 三角形の面積を考えてということをやることになるから，標準的かもしれないが同じていどの ひらめきは必要な気もする． ●急いでいたため，休み時間も学生同士で猥談などしているばあいではない感じ． 授業がすんなり再開するのはある意味快適だが，もう少し時間に余裕があって話せたらいいなとも思う．
Handout: 例題 5.5の解説，5章追加問題6の解説． Lecture: 1815-1925, 1950-2105. Tへの補講: 2105-2125. はじめ K, F だけでやりにくい．A が 1820に．もっと遅れる予定だった E は仕事をひとに任せて 1850 に来る． 就職活動で松山?に行ってたT は 2010 に来た．就職活動で S は欠席． 茨木 5章 5.3 節． ●きょうはマッチング問題．出来るだけ多くのペアを作るのが最大マッチング問題． 最大マッチングを求めるために，あるネットワークを考えて最大フロー問題に変換する． したがって前回のフロー追加法の理解が欠かせない．フロー追加法では， 現在のフロー x が与えられたとき，フローの余裕，つまりフローをどれだけ増やせるかあるいは減らせるかを表した 「残余ネットワーク」を考え，その上に始点から終点までつなぐ「フロー追加路」を探す．フロー追加路があれば， その路沿いのいちばん容量が少ない辺の容量がもとのフロー x に追加できる．そのようにして，新たなフローを x' を 求める……という操作をフロー追加路がなくなるまで繰り返す． ●「こんなに少ないのに始めるんですか」と F. それでも2名で始めた．「H が来てなくてさみしくないですか？」 「さみしい．というか2名というのはさみしい．」遅刻した学生への対応はむずかしかったが， 授業の構成をモジュール式にして，まあなんとか乗り切った．質問も活発に出るまあまあの授業だった． ●テキストはかんたんなことを難しく書いてると A．今日のところはそんなに簡単じゃないのではと思ったが， 簡単というならそれでいい．口頭では同じことをくどいほど繰り返したりポイントを強調したりできるけど， 文章ではそれはむずかしいという事情もあるだろう．このテキストには読者にプログラミングや数学の力もつけてもらう という目標もあるだろう．まあ，逆に言えば口頭の説明でも，すらすらとしゃべってしまっては分かりにくくなるということだ． わざと言葉を途切れさせたり，しつこく同じことを繰り返したりといった「不完全」な日本語を意図的に使うことも 必要だと思う． ●E「こういう交互追加路もありませんか．」よろしい，図にあるのはひとつの例だから． ●2部グラフでない一般グラフのマッチングのところで「今度はホモとかレズがいるばあいの話」と言うと， えらく受けていた．男と女のふたつには分けられないグループでできるだけ多くのペアを作るのが目的． ●遅れて来た T に授業の前半の個人教授 (Fも居たが)．もう帰りたいというのを捕まえて，残ってもらった． 聞気落としたモジュールの分を説明しなければならない．ハイスピードだったが，普通の授業よりよくわかると感想． ●ほかの雑談はコンテンツの相互提供協定を結んだブログに載せてもらった．「勉強することがないんじゃないですか？」 と聞いたようなひとは読むといい．学者の仕事少しは分かるかも: http://theorist.blog6.fc2.com/blog-entry-24.html
Lecture: 1810-1920, 1930-2050, TEへの補講: 2110-2150. 課題の解答: 1章練習問題15，5章追加1 (KFAS) 追加 2, 3, 4 (KFASE). 追加 5, 6, 7. 練習問題 8, 15, 16 (KFASET). 補講は遅刻した T, E の聞き逃した分．(E は2130まで．) ●予定していた授業内容は先週まででこなしたので，本日は学生の自習を支援するための 課題の正解の解説．来週の期末試験への対策． ●本日は「学生による授業評価アンケート」といいうのをやる日．理事の意向で，受講者ひとりの授業でも やるらしい．調査票は成績決定後に教員に回って来るはずだが，そこがきちんと伝わっていなかった かもしれない．学生はそのことを把握しているのか． ●アンケートに答えながら，F が「学生の理解度を把握して授業を進めている」 に低い評価をやるとか言っている． きょうは試験前の最後ということもあって残っていた課題のすべてを かなり速いペースでこなす必要があったから，タイミングも悪かった． だが言わせてもらえれば，学生の理解度をほぼ把握しているのはまちがいない．(質問もあれだけ出るし．) つねに高い理解を全員に求めるわけではないというだけのことだ．たとえば本日のところだと， 「この部分は何度もやっているからその過程は省略して (自習にまわしてもらって)，結論に すぐ行こう」ということをやって時間内に終わらせているのである．(「そう言えば先週やった」と 何人か言っていたとおり．あのな，課題は授業の前にやってくるものなんだが．) ほかのところでも，敢えて完全な理解を求めない部分というのはけっこうある． 全員には理解してもらう必要はないが，意欲ある人には言っておきたい内容などである． そのへんはなんとなく分かった印象を与える程度 (ほとんど分からないひともいるだろう) で満足する こともある．たとえばテキストに書かれている (集合の記号など使った) 数理的な表記の多くは， じつは日常言語でも言い表せるものだ．意味は普通のことばや図で伝わる．だが，数学の授業である以上， そういう表記にまったく触れないわけにはいかない．そういう部分は 「と言われても分からないよな．つまりこういう話……」 とよくやっている通りだ． 要はメリハリをつけて，ポイントをおさえてもらえればいいのだ． すべての部分を同じように理解してもらおうとは考えていない．それをやると簡単なことだけしか 教えられなくなる．「学生の理解度を把握して授業を進める」というのはこういうことだと思う． ●「教員の授業にたいする熱意が感じられる」って質問もある． 熱意が感じられる授業がいいのかってのは疑問だが，それは置いておこう． 関連する参考書何冊も読んで準備して，受講生にも解けるレベルの追加問題作って， 授業の後にも休日のこどもの日にもたっぷりと補講をして，こんなホームページまで作っても， 最高評価をくれない学生はいるだろうなあ． まあ，他の科目のように詳細な講義ノートを準備してといったことはしなかったのは確かだけどね． ●補講は遅刻して来た T と E のためのものだ．だが， 「遅刻して来たのは僕に個人教授でもしてもらいたいんだろう」 というのを否定していた F も (T もだけど) 最後まで残っていた．きみはボディガードか． 補講の終わったあとも 15 分くらい部屋に残って本をみるふたり． ●1750 ころこの科目を履修している高校生が来る．情報数学を専攻出来る大学に入りたいと． 自分は情報科学の専門家ではないので，あんまりアドバイス出来ることもない．一般論を述べる． 「情報数学」という呼び方はあまりしないと思うが，この授業のテキストに載っているような数学が 情報科学のための数学のなかでも中心的なものである． (僕が経済学者であることからこの科目の数学を経済数学とかんちがいしていたらしい高校生．) もし「情報数学」なんていう名前が学科についているとしたら，情報科学の専門家は少なくて，かわりに情報科学 のための数学も教えられる数学者が多いだけといった事情があるかもしれない．純粋理論だけ やりたいならそれでも構わないかもしれない． 工学部とか理学部とかなんとか情報学部とかその他雑学部といった学部名や学科名よりも， 内容をよく調べることが大切だろう．情報科学をやるにしても数学的な純粋理論をやりたいのか， それともプログラミングなど実務で使える知識を得たいのかといったちがいはある． できれば自分がやりたいことをある程度把握しておく必要がある．特にずば抜けた頭脳を 持つ人以外には，純粋理論だけのプログラムは薦めないが． ただし，誤ったイメージを経済学に持って経済学部に入学して来て失望する学生が 多いことを考えれば，情報科学をやろうとして大学に入学して失望する学生はそんなには いないのかもしれない． ●ほかの雑談はコンテンツの相互提供協定を結んだブログを参照． 今回はファーストネームを呼んでもらいたかった女子学生やトイレを覗いた女子学生や ボクを口説こうとした女子学生のお話: http://theorist.blog6.fc2.com/blog-entry-29.html
補講: 1515-1850, 試験 1850-2040. 雑 2055まで 質問を受付 T&F&K 1515-, T&F は1645まで．S 1615 に合流．E 1630 に合流．A 1800 に合流． 全員が揃ってからは，出題問題を特定． ●期末試験場所は三原研究室 (E22 ではない) ●試験は持ち込み不可． ●試験中は「これでいいですか？」と正解かどうかを尋ねる質問が多かった． ●試験は K と E 以外は2000ころまでに終わり．残れと言った覚えはないが，そのまま残って翌日の 試験準備をするT&F. 他は E のところに行って応援 (?) したり． ●2000頃から採点もはじめ，その場で採点をおえる．60点満点で 54, 55, 56, 60, 60, 60 点． 全員 9割行った．もっともレベルの高い最難関と言われている三原の授業にしては良く出来ていた． さすが科目を落とせない4年生以上が揃っていることもあって，モーティベーションがちがう． 「大学の授業っていう感じがすごくしました．試験はそうではなかったけど」という感想があった． みんなと握手を交わしてさよならを言った．みんなごきげんよう． ●授業の裏ログはコンテンツの相互提供協定を結んだブログを参照． 今回は「期末試験日のキスとか握り合いとか身体検査とか」．最後ということもあって力の入った長文になった: http://theorist.blog6.fc2.com/blog-entry-32.html