グラフとネットワーク

岡本 吉央

ショートカット： 講義資料 | コメント | 成績評価 | 公式シラバス | スケジュール | 過去の講義 | 過去の試験問題

お薦めする受講形態は，以下のとおりです．

• 授業日の前日まで：講義動画 (オンデマンド) を視聴する → 質問やコメントをフォームから投稿する (21:00まで)
• 授業日：リアルタイム授業 (質問やコメントに対する回答) に出席する → リアルタイム授業で演習問題にグループで取り組む
• 授業日の後：自習で演習問題に取り組む → 演習問題をレポートで提出する

• 7/16 (14) 平面グラフ：モデル化
  • スライド | 印刷用スライド | 演習問題 | 用語集
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 7/9 (13) 平面グラフ：数理
  • スライド | 印刷用スライド | 演習問題 | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 7/2 (12) 彩色：モデル化
  • スライド | 印刷用スライド | 演習問題 | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 6/25 (11) 彩色：数理
  • スライド | 印刷用スライド | 演習問題 | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 6/18 (10) 連結性：数理とモデル化
  • スライド | 印刷用スライド | 演習問題 | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 6/11 (9) 最大流：モデル化 (3) カットの視点
  • スライド | 印刷用スライド | 演習問題 (6/14修正) | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 6/4 (8) 最大流：モデル化 (2) 二部グラフの最大マッチング
  • スライド | 印刷用スライド | 演習問題 (6/4修正) | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 5/28 (7) 最大流：モデル化 (1) 割当
  • スライド | 印刷用スライド | 演習問題 | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 5/21 (6) 最大流：数理
  • スライド | 印刷用スライド | 演習問題 | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 5/14 (5) マッチング：モデル化
  • スライド | 印刷用スライド | 演習問題 (5/28修正) | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 5/7 (4) マッチング：数理
  • スライド | 印刷用スライド | 演習問題 | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 4/30 (3) 木：数理
  • スライド | 印刷用スライド | 演習問題 | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 4/23 (2) 道と閉路：数理
  • スライド (4/23修正) | 印刷用スライド (4/23修正) | 演習問題 | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 4/16 (1) グラフの定義と次数：数理
  • スライド | 印刷用スライド | 演習問題 | 用語集 | Jupyter Notebook
  • 講義動画 (オンデマンド)
  • 復習動画 (リアルタイム授業の録画)
• 4/9 (0) ガイダンスと離散数学の復習
  • スライド (4/11修正) | 印刷用スライド (4/11修正) | 演習問題 | 用語集
  • 復習動画 (リアルタイム授業の録画)

• 7/16 (14) 平面グラフ：モデル化
  • コメントありがとうございます．
  • 半年間、ありがとうございました。何度も証明を書いて、証明を書くことに慣れることができた気がします。証明を書く練習をこれからもしていきたいです。
    -- こちらこそありがとうございました．皆さんはなぜ証明をしないといけないのか，と思うかもしれませんが，「アルゴリズム (ソフトウェア，ハードウェア) を開発する」というのは「証明を書く」ということとほぼ等しいのです．この講義からその一端が感じられれば成功です．
  • 少し早いですが, 1学期の間ありがとうございました. 個人的には他の人のコメントやそれらに対する先生のレスポンスも楽しみにしていたので, 今週で最後だと思うと少し残念です.
    -- こちらこそありがとうございました．私も少し残念です．;-)
  • 第1回必須レポートは任意レポートのコメントが参考になった部分がとても多かったので, 後半の授業で任意レポートがほぼ提出できなかった分, 第2回必須レポートでちゃんとした文章が書けるか不安はありますが, 丁寧に書くことを心がけて取り組もうと思います.
    -- はい，ぜひよろしくお願いします．
  • 「円は３点以上で交わらない」というところで詰まりました。（高校生レベル？背理法を使った証明を読んで、解決しました。）
    -- すみません，この点はオンデマンド授業の中でもごまかしてしまいました．(間違った説明をしてしまいそうになり，口ごもりました．) リアルタイム授業で補足します．
  • グラフの（平面に限らず）描画に同型のような概念はありますか？描画自体は点の数を少しずつ変えれば無限に存在しますが、角度や線の長さなどを適当に変えることで同じとみなせるものはそこまで存在しないものも多いように見えます。
    -- リアルタイム授業で補足します．答えは「あります」になり，これは「組合せ埋蔵 (combinatorial embedding)」や「回転系 (rotation system)」と呼ばれるものとして定義されます．
  • （レポートなどで）あるグラフがあるグラフのマイナーであることを示す場合、頂点集合の分割＆全単射φが定義を満たすことを示せばいいのでしょうか？それとも図で色分けして、「各色で塗り分けられた頂点の集合が頂点になるマイナーは○○になる」のような書き方をしてよいのでしょうか？見かけのわりに定義が複雑なので少し戸惑いました。
    -- これはどちらでも構いませんが，わかりやすく書いてください．
  • 4色定理で、飛び地があると単純な平面グラフではなくなるので4色で塗れないパターンがあるとは思いますが、地図に適当な条件がある場合（飛び地のなかに飛び地があるか？ある飛び地は別の飛び地と触れるか？など）うまく彩色できる、など派生問題はあったりしますか？現実だと色々な配置があったりするので気になりました。
    -- 条件によりますが，飛び地がある場合にどう考えるのか，という話はあります．リアルタイム授業で補足します．
  • 先生がオープンキャンパスのリアルタイムイベントを行うと知り、参加することを検討しています。研究紹介と研究の活動紹介を行うとのことですが高校生向けの内容なのでしょうか？
    -- 高校生・一般向けの内容となる予定です．よろしくお願いします．
• 7/9 (13) 平面グラフ：数理
  • コメントありがとうございます．
  • オイラーほど「またお前か」って思わせる人, 中々いないと思います.
    -- 私もそう思います．
  • グラフは描かれ方を考えないでいいから便利だと思っていたので, グラフの描かれ方に着目した議論というのは個人的に意外性を感じて面白かったです.
    -- そうですね．いままでは描き方を気にしていなかったのですが，描き方を気にすることによって生まれる数学があるということは面白い点ですね．
  • 描画の定義で「曲線」を定義しないで用いていることについて, これに関する話題だけで1学期講義ができるとおっしゃられていたので, 一体どんな内容なんだと思って「曲線 数学 定義」で検索してみたら, 「曲線をよくみる」というpdfがあって斜め読みしただけなのですが, 確かに1学期(で済むのか？)はかかりそうだなぁ思いました.
    -- 足助先生の原稿でしょうか．このような内容を勉強するためには，解析学やトポロジーといったものをある程度まじめに勉強する必要があるので，少し敷居は高いかもしれません．といっておきながら，おそらく，電通大でも何年か一度は現代数学入門か幾何学概論でこのような話題を扱っているとかもしれません．機会があればぜひ勉強してみて下さい．
  • スライドの19ページを理解するのに時間がかかりました。（どこかでグラフの他の辺に閉曲線Cが引っかかる場合はないのか？と思って図をいくつか書いたのですが、外面が非有界なのでそれはないのだと理解しました。）
    -- その通りですね．分かりにくかったかもしれないので，授業で補足します．
  • 最近別の教科でCGのUV座標周りを扱ったのですが，できる限り連結かつ「いい感じ」に展開する方法（用途などにもよりますが）を求める方法にもこのあたりの理論は使えるのでしょうか？
    -- 「このあたりの理論」がどのあたりなのか，ということに依存しますが，テクスチャマッピングを作成するときには，いろいろなことを考えないといけません．その一部が平面グラフに関係するということはあります．例えば，考えている物体に穴がある場合です．その場合は切り拓くときに，「穴を壊せる」と都合がよいので，そのように切りたいのですが，それを考えるときには，オイラーの公式を使えます．授業で補足します．
  • 凸多面体のグラフを平面上に書くとき、立体的に後ろ側の面をひっくり返して広げ、外側に押し出されるような様子が、泡の集まりが変形する現象に似てると思いました。
    -- そうですね．そのような類推を思い浮かべると理解しやすそうですね．時間があれば授業で補足します．
• 7/2 (12) 彩色：モデル化
  • コメントありがとうございます．
  • グラフの彩色としてモデル化できる問題について, 最大流問題としてモデル化できる問題と同様に何かを割り当てる問題が多いなと思ったので, 今回紹介されたような問題も最大流問題としてモデル化できないのかなと少し考えてみたのですが, 「領域」が被らないようにするという制約(ふわっとした言い方ですが, 例えばジョブスケジューリングだと同じ時刻に一人ができる仕事は一つであるという部分)を落とし込むところが難しいように思いました.
    あと, 最大流問題としてモデル化しようとすると, 最低何種類の割当元があれば割り当てられるか(ジョブスケジューリングでいうところの最低何人必要になるか)を調べようとすると, (何らかの定理で下界が分からない限り)1から順に調べないといけなさそうなので, その面でもグラフの彩色としてモデル化した方が, 多項式時間で染色数が計算できる場合があって便利なのだろうと思いました. (講義のどこかで言及されていたら申し訳ないのですが, 区間グラフの染色数計算は多項式時間で可能で正しいですか？)
    -- 実を言うと，区間グラフの染色数計算は最大流問題としてモデル化できます．これは授業で補足します．
  • グラフには要素同士の繋がりを表現することに専ら使われているイメージを持っていたので、グラフの要素同士の距離も交えて考えるのは新鮮に感じました。
    -- 図形 (幾何) からグラフが現れるということは，実をいうとよくあります．センサネットワークや地理情報システムなどが応用例として現れます．時間があればこれについても授業で補足します．
  • 個人的な話ですが, MICS実験のレポートの〆切に次々と迫られるようになって, この講義の任意レポートに手が回らなくなってきました. 加えて, 先日PC初期化が必要な事態に出くわしてしまい, 復旧作業という余計なタスクが増えたせいで, 大変なことになってます(こちらは必要な分は完了したのですが). 今学期履修している講義で一番関心があるものなので, 頑張りたいところなのですが, 思うようになっておらずもどかしさを感じてます(-_-;)
    -- それは大変ですね．復旧できたということですので，それは何よりです．
  • 今回の講義で、円がdiskであるという話がありました。そこで、先生が言いかけていたことが気になりました。
    -- では補足します．「円」ということばで想起するものには2つあるので，それを説明します．
  • 彩色というと効率的に解くのが難しく、実際に応用できる範囲が少なくなりそうな印象があったのですが、特殊なグラフに限ればいろいろと工夫の余地があるのが面白いと思いました。
    -- そうですね．今回は彩色について，特殊なグラフに限った場合に何がいえるのか，ということを扱いましたが，これは彩色でない問題についても当てはまります．例えば，マッチングについても，何も制限がなければ強双対性が成り立たないかもしれないのに，二部グラフであるという特殊な状況を考えると，強双対性が必ず成り立つということが言えます．問題をモデル化したときに現れる特殊な状況が何であるのか，ということに目を向けることがいつでも重要になるのです．
• 6/25 (11) 彩色：数理
  • コメントありがとうございます．
  • 現実の問題で、彩色を適用したくなるシーンを考えたのですが、なかなか良いものが思い浮かびませんでした。やっと思い浮かんだのが「職場における新型コロナウィルス感染症ワクチンの接種日程」でした。（同じ会社の人のうち、職務上関連のある人同士を辺で結び、そこで彩色を適用。ワクチン休暇を使う可能性を考える一方、医師を外部から会社に派遣してもらう場合、そのコストはなるべく抑えたい）
    -- このように自分の例を考えるのは素晴らしいので，ぜひ励行して下さい．
    考えてもらった例のように，競合があることをモデル化するときに，グラフを使うということはよくあります．授業で挙げたジョブスケジューリング，レジスタ割当，周波数割当の例もその考え方に沿っています．
  • 隣り合う辺や頂点の色が重複しないように色を定めるという話を聞いた時、真っ先に4色定理を思い浮かべました。任意のグラフも4彩色可能であったり、4辺彩色可能であったりするのでしょうか？
    -- 四色定理は14回目の授業で扱います．「任意のグラフも4彩色可能であったり，4辺彩色可能であったりするのでしょうか？」という質問に対する回答は授業で行います．簡単に答えますと，「No」です．
• 6/18 (10) 連結性：数理とモデル化
  • コメントありがとうございます．
  • 証明についての質問です。証明中に他の定理を参照する場合に、その定理を証明する必要がありますか？文脈によってケースバイケースなのでしょうか？
    -- これは根深い問題です．まず，我々は試験やレポートのために勉強をしているわけではない，ということを認識しないといけません．
    それを踏まえて，「試験やレポート」で証明を書く場合の話をまずします．この授業の場合は，他の定理を参照する場合に，その定理を証明する必要はありません．特に，授業の中 (オンデマンド動画の中) で証明されているものは，(その証明を行うという問題でない限り) 証明をする必要はありません．ただ，どの定理を参照しているのか書く必要があります．
    一方で，自分で物事を考えるとき，あるいは，論文を書くときには，知られている定理はなんでも使ってよく，その証明をする必要はありません．ただ，どの定理を参照しているのか書く必要はあります．
  • 第9回演習問題の授業内問題9.1で出てくる, 講義によって得られる知識とそのためのコストについてのfootnoteに「本来, そのようなことがあってはならない.」って書いてあるのが個人的にはツボです. 現実には笑い事じゃないですが…
    -- モデル化している問題がどれほど現実的なのか，ということは常に考えていないといけないことです．研究としては，現実の問題を抽象化して，複雑な部分を切り落として (捨象して)，シンプルな状況を考えることがありますが，そうであったとしても非現実的なことを考えるものがよくあります．そういうものが論文として出版されていることもありますが，「よくない研究」なので，真似しないようにして下さい．
  • 現実での問題をグラフのモデルとして解決を図れないかと考えたとき、どうパラメータをグラフの情報に変換して、どうグラフの特徴を抽出するかがとても重要で、同時にとても難しいと感じました。
    -- それはその通りだと思いますし，グラフだけの問題ではなく，数学全般に適用されると思います．「数学は技術」だという立場において，その技術をどのように使うのか，という点は，「技芸」(art) なのだと思います．それをどのように「科学」(science) にして，誰もが使えるようにできるのか，ということが研究なのだと思います．
  • 用語の脳内への定着度がかなり低いです（悲）使いこなせる自信がないので、演習問題を解きながら一つ一つ復習していこうと思います。
    -- 用語を覚える必要はないので，調べながら思い出して取り組むようにして下さい．
  • 「:」(コロン)、 「;」(セミコロン)、「,」（カンマ）、「｜」（バーティカルライン）など、要素を並列させたり補助的な条件を入れたりするときに使いますが、それぞれに使い分けはありますか？与えられた記法を使うだけならあまり気にする機会はありませんが、それらを定義するときなどどうやって決めているのか気になりました。
    -- あまり区別されずに使われ，その点は曖昧であることが多いと思います．残念ながら，数学というのは，人々が思うほど形式的ではないのです．
    ただ，カンマを補助的な条件を書くために使うことは少ないように感じます．カンマを使うのは，大抵，要素や条件を並置するときだと思います．
  • テロリストとネットワークの脆弱性のくだりで, 「彼を知り己を知れば百戦殆うからず」って言葉をふと思いました.
    -- そうですね．最適化における双対性というのはそういうもので，何かを最大化したいときに，別のものを最小化することを組にして考える，ということになります．これは「最大化したい側」と「最小化したい側」のせめぎ合いであると捉えられるわけです．このようなものは，ゲーム理論のことばでいうと「二人零話ゲーム」なのですが，実をいうと，二人零話ゲームは最適化の基礎である線形計画法と同値であることが知られています．このようなことは『オペレーションズ・リサーチ基礎』の授業で扱っているかもしれません．
  • 最後に言及されていたように, メンガーの定理の話自体は流れやカットといった概念を持ち出すまでもないのですが, 強双対性という共通点から流れやカットを利用しても理解できる(きちんと証明する上ではむしろ必須だったりするのでしょうか？)というのは面白いと思いました. 他の強双対性を持つ関係も実はグラフ(の流れとカット)の話に持ち込めるというのは, よくある話だったりするのでしょうか？
    -- 強双対性を持つ関係の多くは「線形計画法の双対性＋整数性」という形で理解されます．こういうことは『オペレーションズ・リサーチ基礎』や『数理計画法』で触れられないといけないと思うのですが，おそらく触れられません．授業では簡単な例を使って補足します．
  • メンガーさんの名前は「メンガーのスポンジ」で聞いたことはあったのですが, まさかこの講義で出てくるとは思ってなかったです.
    -- 「メンガーの定理」のメンガーさんは「メンガーのスポンジ」のメンガーさんと同一人物です．20世紀の初めぐらいまでは，まだ数学の細分化がされていなくて，一人の数学者が (今でいう) 多くの分野に関与していたように思います．
• 6/11 (9) 最大流：モデル化 (3) カットの視点
  • コメントありがとうございます．必須レポート1の提出締切が迫ってますので，提出を忘れずに済ませて下さい．よろしくお願いします．
  • 手間かと思いますが中間レポートの採点をした後にどこが間違っているかなどコメントを付けていただきたいです 結構頑張ったのでどこが間違っているか知りたいです
    -- 「中間レポート」というのは「必須レポート課題1」のことであると読み替えます．
    提出されたレポートは返却します．どこが間違っているか，ということをすべてコメントすると，コメントが大量になり，私の限られた時間で処理することができなくなるので，取捨選択してコメントをつけることになります．予めご了承ください．
  • 渾身の力を込めて必須レポートを書きました（以前解いた問題であっても、解答がメチャクチャなものも多く、一から考え直した）。そこで力尽きてしまい、ここ二週間は任意レポートまで全く手が回らなかったのが残念です。
    -- 渾身の力の使い方が重要ですね．力をうまく振り分けられることが試されているのかもしれません．
  • 毎週課題が提出できるのがとても良いと思います。
    -- 課題を提出しているのは私であって，皆さんが提出しているのはレポートです．ご留意ください．せひ，ご提出ください．
  • 個人的にはなかなか時間が割けずに提出が少ないですが、証明の添削してもらえるのがとても勉強になるのでもっと出せるように頑張りたいです。
    -- はい，お待ちしております．よろしくお願いします．
  • この質問フォームには過去回の講義の質問をしても大丈夫ですか？
    -- はい，大丈夫です．ただし，そのような質問には，このページ上でお答えすることになり，授業では扱わないことになります．
  • 帰納法についてですが、高校生のときn = 1のとき成り立つことを証明してからn = kで成り立つことも証明しました
    講義第3回の木ではn = 1のときに成り立つか確認をしていないように思うのですが、なぜなのでしょうか
    -- まず，帰納法について「n = 1のとき成り立つことを証明してからn = k で成り立つことを証明する」というものではありません．ご注意ください．
    また，第3回講義のスライドを見直したのですが，n = 1のときに成り立つか確認しているように思います．すみませんが，どの部分のことなのか，ご指摘いただけますでしょうか．
  • 第4回の講義でマッチングの辺eはeの端点を飽和するとありましたが、辺が端点を飽和するという表現に少し違和感を感じます この分野では一般的に使われている表現なのでしょうか？
    -- マッチングを考えるとき，各頂点には「それに接続する辺を1つまで選べる」という制約がついている，と思って下さい．そのとき，頂点に接続する辺を1つ選ぶと，それによって，「1つまで選べる」という制約が飽和されます．これを，「辺が頂点を飽和する」と見なしているわけです．
    ちなみに，「飽和する」に対応する英単語は「saturate」です．皆さんは，電子回路や電気回路についてどれほどの経験があるのか分からないですが，例えば，回路の過渡現象を観察するときに，「サチる」というジャーゴンが使われることがあります．これは「saturate」を語源としています．
  • 今回の講義で紹介された問題は, いずれも「何らかの意味を持つ『領域』を取り出す」という形式の問題で, 割当問題とは全然違う形式に見える問題なのに, どちらも流れとカットの強双対性というありがたい性質のおかげで, 最大流問題を解くことによって解くことが出来るというのは面白いと思いました.
    -- そうですね．これはあまり思いつかないと思いますし，とても有用なのでご紹介しました．使えそうな場面がありましたら，ぜひ使ってみて下さい．
  • 最小カットは大量の制約がある問題をうまく機械的に解くのに便利という印象を受けます。最近何かの本（多分図書館にあるアルゴリズムデザイン）で問題をProject Selection Problemに落とすやり方を知ったので、今回のグラフの構築は割と自然に読むことができました。
    -- おそらく「Project Selection Problemを(最小s,tカット)問題に落とす」だと思います．向きにご注意ください．
    なお，この手の問題は，文献に置いて「minimum-weight closure problem (最小重み閉包問題)」とふつうは呼ばれています．授業で紹介したのは，それを最小s,tカット問題としてモデル化して解く方法になっていて，Picard (ピカール) の1976年の論文に由来します．
  • ところで、講義で説明されていることを理解しようとして、よく頭がこんがらがるのですが、今日の講義では図までこんがらがってしまい、何度か書き直しました。
    -- 自分で描くことは理解するために重要なので，ぜひやってみて下さい．:-)
  • 大なりイコールを高校生までは≧(\geqq)の形しか見なかったのですが、大学生になった途端\geqの方をよく見るようになりました(この授業でも\geqですよね) 多分数学的な意味の違いは無いと思うのですが先生はなぜ\geqを使いますか？感覚的には論文でどちらが多く使われていますか？他にも豆知識などあれば知りたいです
    -- 実数に対して使われる場合は，違いがないと思って下さい．授業で補足します．
    ちなみに，HTMLでは「≧」に対応する文字実体参照はないようです．
  • 好きなプログラミング言語はなんですか？また、研究でよく使うプログラミング言語はなんですか？
    -- 特になし，です．使えるものをなんでも使っています．また，研究で真剣にプログラミングをしたことはないです．
• 6/4 (8) 最大流：モデル化 (2) 二部グラフの最大マッチング
  • コメントありがとうございます．
  • 陽に「割り当てる」ように見えない問題でも, 割当問題としてモデル化できる例が想像以上に多くて驚きました.
    -- そうですね．まず，そういう例があることを学んで，そこから，自分でそのような応用ができるところまで進めると素晴らしいです．
  • 四目並べは子供の頃によくやりましたが、すぐにつまらなくなって（引き分けばかりになって）やらなくなりました。その理由が分かって面白かったです。どちらかが勝つためには、相手の見落としに賭けて、あえて勝負を賭けに出ないといけないということだと理解しました（慣れてくると潰すことにだけ意識がいくー＞引き分けばかりー＞つまらなくなってやめた）。
    -- 残念ながら，「結論が分かっている」ことと「つまらない」ことはあまり関係ないと思われています．例えば，オセロ (リバーシ) は後手が有利であると言われています (それが数学的に証明されているわけではないです) が，仮に後手が必勝であるとしても，ゲームとしては十分楽しめるものだと思います．また，オセロの場合は，先手と後手が最善を尽くすとすると，結果が「先手必勝」，「後手必勝」，「引き分け」になるか，ゲームを行う前から決まることが分かっています．これについては授業で補足します．
  • ゲームの解析は様々な方法がありますが，フローを使う方法はどの程度一般的なのか，ほかに代表的な手法はあるのか気になりました．
    -- フローを使う方法はそれほど一般的ではなく，使える場面は限られています．一方で，ここで紹介した「ペアを用いた戦略」はいろいろな場面でよく使われます．これについては授業で補足します．
  • 「知られていること」で述べられている3次元3目並べや3次元4目並べは重力無しのルールについてですか?
    -- 「知られていること」で述べられているものは重力無しのルールです．一方で，重力がある場合の結果もあります．授業で補足します．
  • 証明の中で自分が定義したfが流れであることを言うために, 流量保存制約と容量制約が成立することを確認するときに, 後者はグラフの各弧で1回ずつ比較すれば分かるので簡単に記述しても問題ないように思いますが, 前者も簡単に確認できることとして記述して良いのでしょうか.
    -- はい，「簡単に確認できる」と書いてしまってよいです．線形時間で確認できますから．これも授業で補足します．
  • 別件で、レポートに向けて過去に添削していただいた任意レポートを見返していますが、自分が書いた過去レポート、ひどいですね（苦笑）。定義を無視＆言いたいことが日本語できちんと表現できていない部分が目立ったので、必須レポートではまともな日本語が書けるように頑張ろうと思います。
    -- よろしくお願いします．「言語を用いて表現する」ということはとても重要な技能なので，磨いていって下さい．
• 5/28 (7) 最大流：モデル化 (1) 割当
  • コメントありがとうございます．
  • 忘れないように書いておきます．授業の中で，「最小 $s,t$ カットは○○である」という言い方と「○○は最小 $s,t$ カットである」という言い方の違いを説明します．
  • 優勝可能性問題はパラメータを弄ったり、目標を変えると多くがNP困難になりますが、どの程度まで許容されるのかが決まっているのか気になりました。
    -- 最後の方でちょっと補足していましたが，今一度，授業で補足します．
  • (a,b,c)-規則を定めたときの優勝可能性判定問題で, 最大流問題としてモデル化が可能な例にa=bの場合が挙げられていましたが, そうすると負けた場合だけ不利になるため, 「如何に相手を負かすか(=如何に相手に勝つか)」というより「如何に負けないようにするか」という戦略の方が発展しそうで, ゲームがつまらなくなるのかもしれないなと思いましたw
    -- これは重要な着眼点で，そのため，FIFAでは勝利をより貪欲に目指すようにするため，(3, 1, 0)-規則が採用されるようになった，という経緯があるそうです．
  • 最後に(a,b,c)-規則と優勝可能性判定問題の難しさについて紹介されてましたが, ほとんどの規則に対して問題がNP困難であり, 簡単に解くアルゴリズムも発見されていないのに, 過去のFIFAの規則やMLBの規則の場合といった, 関心が高そうな場合に限って偶然, 最大流問題でモデル化が可能だということが面白いと思いました.
    -- (2,1,0)-規則のように「割り当てる」という考え方がとても自然なのでしょう．それだからこそ，採用されたのだと思います．
  • 今回扱った割り当ての問題が二部グラフの最大マッチング問題のように見えました。実験で二部グラフの最大マッチング問題を扱いましたが、今回のように頂点s,tを導入して増加道を探しました。次回が、二部グラフの最大マッチングということで、関連がありそうだと予想しました。
    -- その通りで，第8回の内容が二部グラフの最大マッチングに関するもので，そこでは第7回の考え方を使います．
  • レポートに関してですが、「○○を求める時間計算量O(△△)のアルゴリズムを設計せよ」や、「これを◇◇問題として定式化せよ」という問題にはどのように答えるべきですか？例えば、停止性や正しい出力が得られること、計算量の証明、定式化に至る過程、正しいことの証明などは必要ですか？
    -- 「○○を求める時間計算量O(△△)のアルゴリズムを設計せよ」に対しては，「○○が求まること (停止性を含む)」と「計算量の証明」は必要になります．
    「これを◇◇問題として定式化せよ」に対しては，「◇◇問題として書く方法」と「◇◇問題に対する答えから元の問題に対する答えを読み取る方法」が必要になります．定式化に至る過程は不要です．
  • 具体的な問題が出てきたので、理解しやすかったです。
    同じ二部グラフでも、使う人が工夫すれば水の流れだけではない様々な問題に応用できるのが面白いと感じました。
    -- それを伝えたいのです．それが伝わったのならば，とてもうれしいです．:-)
  • モデル化の際のグラフはすぐに思いつくものもあればしっかり考えなければ思いつかないものもあり、モデル化の練習が必要だと感じました。
    -- そうですね．練習や慣れが必要になりますね．それだからこそ勉強する価値があるのだと思います．「数学は技術だ」と思っているのですが，技術を使えるようになることが重要だと思います．
• 5/21 (6) 最大流：数理
  • コメントありがとうございます．
  • この時期の梅雨入りの速報は沖縄ぐらいでしかないものだと思っていたのですが, コメント記入時点で東海以西はもう梅雨入り速報が発表されててビックリしました. まだ, 関東地方の梅雨入り速報は発表されていないですが, 天気が悪い日が続いているので早くも梅雨入りするのかなぁと思ってます. 個人的には, 天気が悪くなると頭が痛くなりがち(窓が開けられないために換気しづらくなるからか, 気圧のせいなのか, 湿度のせいなのか, はたまた全く別の理由なのかは謎ですが)なので, あまり長引きすぎないで欲しいところですね…
    -- 今年は年始の段階の長期予報で，夏の雨が多い，と言われてますので，注意していきたいですね．
  • 成績は絶対評価と相対評価のどちらでしょうか？また、レポートの点数が何点以上など成績の具体的な決め方を教えてほしいです(シラバスは少し抽象的に感じました)
    -- 第0回講義のスライド16ページをご覧ください．
    ここでも繰り返しますと，2回のレポート提出のみで評価され，1回のレポートでは5題だされて，1題10点満点です．評価基準は2回のレポートの素点の合計です．
  • 理解能力の問題か、1時間半の動画を2時間以上かかって閲覧しました。「f」ってなんだっけ？（関数なのに変数みたいな使われ方をしている）、「最大流」を聞かれた時、どうやって答えたらいいんだっけ？（最小カットならば頂点集合だから答えやすいのに・・・）など、前提や言葉の使い方といった部分で混乱しました。直感的には分かりやすいトピックだけに、逆に難しかったです。
    -- 「関数なのに変数みたいな使われ方をしている」と「最大流を聞かれたとき，どうやって答えたらいい？」については，授業で補足します．
    簡単な答えをこちらでも掲載します．前者については，流れは $f\colon A\to \mathbb{R}$ という「関数」として定義していますが，これはベクトル $f \in \mathbb{R}^{A}$ と見なすことができます．そうすると，各弧 $a \in A$ に対して，$f(a)$ の値を定めれば，それが (流量保存制約と容量制約を満たせば) 流れになります．後者については，上で述べた「$f(a)$ の値を定める」ということを行なえばよいです．
  • Ford-Fulkersonのアルゴリズムなどをかなり前に独学でやろうとした時は「何かよくわからないけど確かにできてるなすごーい」という感じだったのですが、今回は論理的な正しさを追いかけられて楽しいです。
    -- それはよかったです．ぜひ自分の手で動かしたり，実装してみたりして，理解を深めて下さい．
  • 流量保存制約はキルヒホッフの第一法則と同じようなイメージを想像しました.最大流を求めるアルゴリズムから,回路に悪影響を与える大電流が起こる部分を特定するというような応用方法があるのではないかと考えました.
    -- 流量保存制約はキルヒホッフの第一法則と同じことをいっています．そして，電気回路をグラフであると見なすことはよくあります．これについては授業で少し補足します．応用を自分で思い浮かべるのはとてもよいですね．
    ただ，電流を講義で扱ったような「流れ」として扱おうとすると，容量に対応するものをうまく考えることが難しいので，その点には注意する必要があります．
• 5/14 (5) マッチング：モデル化
  • コメントありがとうございます．
  • １つの授業を１日にまとめて５回分ぐらい連続して見たほうがそれぞれの回の繋がりを知ることが出来て効率が良いと思っています
    ただこの授業は１週間に１回分の講義をアップしていて、任意レポートの締切も１週間しかないです　複数回先の授業も公開することを検討してほしいです
    -- ご意見ありがとうございます．このように授業への提案もどしどしお寄せ下さい．
    毎週授業がある，というペースは対面であっても遠隔であっても変わらない，という意味で，毎週1回分の講義動画を用意しています．また，皆さんからのコメントや質問に応じて，授業内容を変える余地を残すためにも，そのようにしています．ご了承ください．
  • スライドの図はどのように作成しているのでしょうか？
    -- IPEを使って作っています．
  • 実社会での応用例を見るのは面白かったです。
    -- それはよかったです．次回以降もモデル化の場合はそのような例を見ていくことになります．
  • 昨今のコロナ禍のせいで, 簡単に真っ先に思いついた問題が患者と病床のマッチングだったり, ワクチン接種希望者と予約枠のマッチング(形式次第では研修医配属問題と同型になりそう)だったりで, 重要だとは思ったのですが, もっと楽しげな問題を思いつきたいものです…
    -- そのように自分なりの例を思い浮かべるのは重要ですね．楽しげでなくてもよいと思います．問題解決というのは，困っていることを解決するわけですから，困っていることというのが楽しげでないことはよくあることだと思います．
  • 組み合わせを評価したり、効率的な組み合わせを見つけたりするのに便利そうだと感じました。部屋の家具の配置を提案するアルゴリズムのようなものも作れそうですね。
    -- そのように自分なりの例を思い浮かべるのは重要ですね．あと「効率的」という用語は少し注意が必要なので，これについては授業で補足をします．
  • 今までの動画と違って、現実問題を扱っているところがすごく新鮮で、見入ってしまいました。ただ、自分で使えるようになるレベルに達するにはまだまだで、今までの単元と同様、基本（言葉の定義とか）から一つひとつ確認しながら練習しなければと思いました。
    -- 「自分で使えるようになる」のは確かに難しいと思います．実際のところ，この講義では既存の例を学ぶということになります．一方で，自分で問題を解決するということは卒業研究やその後で行うこと，あるいは，行ってほしいことになります．この講義では自分で使えるようになるための基礎を学んでいると思って下さい．
  • GNN(グラフニューラルネットワーク)に興味があるのですが先生はGNNを用いて何か研究していますか？また、英語でしか文献がなくて手が出せない状況なのですが効率の良い英語の勉強方法を教えてほしいです
    -- 2つの質問があるので分けて答えます．
    (1) グラフニューラルネットワークを用いて研究をしていません．そういうものが存在しているということは知っています．
    (2) 英語の勉強方法についてですが，私は英語教育の専門家ではないので，ただ私の妄想持論をお伝えします．その点はご了承ください．
    まず，何事も「使う」ことが重要です．つまり，英語を使わなければ英語が使えるようにならないと思います．日本に生活していて英語を使うというのは実をいうとかなり難しいです．その中で英語を使おうとすると割と努力が必要です．
    ここまでは抽象的なことを書いてるので，もう少し具体的なことを書きます．(A) 英語の文書を読むこと．これは割と簡単にできます．例えば，インターネットのニュースサイトとか見ればよいです．技術的な文書でもよいです．適当なWebブラウザを使えば，単語をドラッグすると辞書が動いて意味を教えてくれます．(B) 英語の映画とか動画を「吹替」ではなく「字幕」で見ること．これも定額動画サービスに入れば簡単にできます．なお，映画や動画の英語はかなり速いです．それでも，だんだん慣れていって，肝となる単語は聞き取れるようになります．(C) 洋楽をカラオケで歌うこと．英語っぽいリズムは音楽を通じて身につけるとよいと思いますし，実際身につきます．
    ここからは別のことを書きます．また妄想持論ですが，多くの日本人が英語をできない理由は，実をいうと「日本語が下手」だからだと思っています．日本語が上達すれば英語も上達すると思います．「日本語の上達」というのは，難しい漢字が書ける，とか，たくさん四字熟語を知っている，とかそういうことではなくて，とにかく「論理的に文章が書ける」ということと「論理的に文章が読める」ということです．これは文章が論説文であるとか小説であるとかに関わらず成り立ちます (小説も論理的に読まれるべきであって，論理的に書かれるべきだと思っています)．
    また別のことです．はじめに「何事も『使う』ことが重要」と書いたのですが，例えば，これは数学についても言えます．皆さんは試験のために数学を勉強する，ということしかしたことがないかもしれませんが，ぜひ皆さんには普段の生活の中で数学を使ったり，数学の芽を見つけてほしいと思うのです．これは数学でなくても，物理，化学，情報，…なんでもそうです．ぜひ励行してみて下さい．
• 5/7 (4) マッチング：数理
  • コメントありがとうございます．コメントがだんだんと減っているので，みなさんしっかりと提出するようにして下さい．
  • 先生の受け持つ情報工学工房ではどのようなことをしますか？
    -- 今年度は受講生がいないので，何もしません．;-)
  • 丁度MICS実験第一のJ8課題でマッチングを扱っており, 既に実験テキストから分かることは理解していたつもりではあったが, この授業では思考の過程をより直接的にたどって説明されていて, 特にマッチングと増加道の関係についてより理解を深められたと思う.
    -- それはよかったです．1つのことを繰り返し学ぶとよりよく定着すると思います．
  • ORの線形計画問題やフロー・カットなど、マッチング・頂点被覆と似た構造が色々なところで出てくるのでだんだん見慣れてきた気がします。
    -- フローとカットは次々回の内容になります．実をいうと，この3つは深く関係がありますが，この講義では線形計画法に触れないので，授業でも補足しないことにします．
  • 頂点被覆、特に最小頂点被覆について、選んだ頂点集合が（最小）頂点被覆であることを述べる際「図に書き込んだ頂点の部分集合が最小頂点被覆の定義を満たしているので、これは（最小）頂点被覆」と言い切ってしまっていいのでしょうか。（定義がそうなんだからそれで良し、とは思うものの、それで説明になっているか、自信がないです。また、複雑なグラフになるほど数え落としなどのミスも考えられるため、プロセスが危険だとも思いました。）
    -- これは「確認する」という行為に関する疑問であると思います．「確認すること」と「証拠の考え方」は重要ですので，授業で補足します．
  • 動画とは関係ないですが、個人的にはリアルタイムの演習の時間がとても刺激になっています。他の人の前で間違った証明をしていつも恥ずかしい思いをしていますが、一方で優秀な同級生からもらえる指摘は貴重で、理解を深めるために欠かせない時間だと思っています。
    -- それはよかったです．「聞くは一時の恥，聞かぬは一生の恥」とも言われます．恥ずかしい思いをせずに成長することは難しいとも思います．私は才能というものの存在を信じていないのですが，才能があると思われる人ほど，おおく恥をかき，努力しているのだと思っています．
• 4/30 (3) 木：数理
  • コメントありがとうございます．雑談でもなんでもよいので，コメントを投稿してください．よろしくお願いします．
  • 過去の講義のコメントとレスポンスが公開されていて, どんなことが書かれたのだろうと思って読ませていただいたら, ギャグみたいなものが想像以上に多くて思わず笑わせていただきましたw.
    -- みなさんもなんでもよいのでコメントをお願いします．;-)
  • レポートの再提出をする際、最初の提出時に解いていない問題を新たに解くことは可能ですか？
    -- 新たに解くことは可能ですが，そのときに私が見るかどうかは分かりません．
  • 研究では証明を自分で考えたり、人が考えた証明を読んだりすることが多いのでしょうか？
    -- 数学の研究においてはそうですね．実をいうと，コンピュータサイエンスというのは割と数学に近いので，コンピュータサイエンスの論文の中には，証明が書いてあるものがたくさんあります．そういうものを読むときは「人が考えた証明を読む」ということになりますし，そういうものを書くときは「証明を自分で考える」ということになります．
    皆さんに理解していただきたいことは，数学を勉強したり研究したりする人が証明を考えるのは当たり前で，むしろ，皆さんのようにそうであるとは限らない人が，証明を考えたり，証明できるようになることが重要だということです．それが皆さんの付加価値になります．
  • グラフ理論における木は、個人的に自然の木に表れるアルゴリズムをまさに体現しているように感じます。そう考えるとグラフ理論の木は、変形自在の物体の切ったり付けたりできる物体による理想的なモデルを表しているようにも思えます。
    -- 面白い見方ですね．類推（アナロジー）は創造の源泉なので，他の概念についてもいろいろな見方をしてみて下さい．
  • 帰納法の不十分な部分の指摘について, 残念ながら自力では見つけられませんでした(´・ω・｀). 任意の○○の性質を示すときに帰納法を利用するときは, 本当にやらかさないようにしていきたいです(；・∀・).
    -- これは授業で補足します．
  • 数学的帰納法の「好ましくない証明法」について理解しましたが、「好ましくない証明法」の方を先に使いたくなる欲求に駆られてしまうのはなぜだろうと思ってしまいます（今回の問題の3.1とか）。あと、数学的帰納法が適しているかそうでないかを問題ごとに見極めることが苦手です。（例えば前週の問題2.8は、数学的帰納法を使う必要はないと思いましたが、当初帰納法でやろうとして突き進んでしまいました）
    -- 何が数学的帰納法に適しているか見極めることは難しいです．一つポイントとなるのは，証明すべきことにおける「前提」が小さくした問題でも成り立っているか確認できることだと思います．授業で補足します．
  • "有限の世界において「帰納法はアルゴリズムそのもの」"というのはなるほどと思いました。
    普段便利なアルゴリズムを使うことに慣れて定義をおろそかにしているとそれが適用できない状況になった時に何もできなくなってしまうといったことがちょくちょくあるので、これを含め「格言」に書いてあるような視点を持って自分がやろうとしていることの本質を理解しようとすることは重要だと思いました。
    -- 科学や工学において「用語の定義」は重要な考え方です．用語を定義するというのはコミュニケーションにおける核であって，1つの用語に対する定義がぶれていると，コミュニケーションがままならなくなります．正しい用語を正しい定義に基づいて用いる習慣をつけるようにして下さい．
• 4/23 (2) 道と閉路：数理
  • コメントありがとうございます．先週よりもコメントが増えました！ ありがとうございます．ぜひ皆さんもコメントを投稿してください．
  • 4月18日8時現在、復習動画 (リアルタイム授業の録画)が公開されていないのですが、いつごろ公開されますか？
    -- すみません，既に公開されていました．このページからリンクが張られていなかっただけなので，張りました．
  • 第2回の資料スライドの20頁のQ4の図がP2とQ3の直積ではなくQ2とQ3の直積になっていると思うのですが間違っていますでしょうか
    -- 私が間違っています．これは授業で補足します．
  • スライドP20の多次元立方体グラフのうち、d＝4、すなわち４次元立方体グラフがなぜ図のようになるのかわからなかったので、解説をお願いできますか。図に書いてみたのですが、（高校数学までの意味での）立方体を二つ並べて線で結ぶところまでで詰まってしまいました。なぜ図のようにQ3が4つ出てくるのか、図解していただけるとありがたいです。（これがわからないと問題が解けない）
    -- 上のコメントのとおり，私が間違っていて，これはQ5です．授業で補足します．
  • 面白かったです
    -- それはよかったです．演習問題にも取り組んで下さい．
  • 授業動画を見た後配布資料のJupyterNotebookのコードをいじって理解を深められるのが良かったです。
    -- Jupyter Notebookの使い方は皆さんの自由ですので，ぜひ活かして下さい．
  • スライドの１８枚目の、第一行目の式から第二行目の式にいくところが、どうしてそうなるのか分からなかったので、解説いただけるとありがたいです。（確率で言うところの独立事象みたいなもの？と理解したのですが、絵的・直感的にわからなかったので、図解いただけると理解が進みそうで嬉しいです。）
    -- はい，これは授業で補足します．基本的には，有限集合 $A$, $B$ に対して，$|A\times B| = |A| \cdot |B|$ が成り立つことを使っています．
  • グラフに関する定義が多かったので、整理しながら理解していきたい。
    -- そうですね．定義を理解することからスタートするので，その視点は大事にしていってください．
  • 最後に「性質を深く理解するための考え方」について紹介されていましたが, 性質を深く理解することに限らず, 新しい問題を見つけるためにも役に立つと思いました.
    -- その通りだと思います．このように考えることは「論理的に考える」ということを行う時にはとても大事なので，ぜひ励行して下さい．
  • δ（G）＞＝ｋならばGはP_{k+1}を含むという最大性論法、完全グラフの時、反例になるか？と悩んでいたら、Pの定義が道に含む辺数ではなく、頂点数だった。定義に戻ることの大切さを確認した。
    -- そうですね．これは授業で補足します．
  • 完全二部グラフK_{n,m}では,nとmの差が1以下でないとP_{n+m}を含むことができない,というのは正しいでしょうか?
    -- 正しいです．授業で補足します．
• 4/16 (1) グラフの定義と次数：数理
  • コメントありがとうございます．いただいたコメントとその回答は以下のように掲載されます．雑談でもよいので，オンデマンド講義動画を見た人はコメントを提出してもらえるとうれしいです．
  • とてもいいやり方だと思います。
    -- 進め方について，何かご提案があれば，よろしくお願いします．
  • とても面白かったです。
    -- それはよかったです．次回以降もお楽しみに．
  • 授業の進め方及び学ぶ内容について理解できた
    -- 何か質問がありましたら，よろしくお願いします．
  • グラフとして図で書くと全く別に見えるのに実は同じということによく悩まされるので、順序対で見ればよい、道警写像を考えればよい、というのはいい発見だった。また、握手補題は直感的に正しいが、証明を与えられることで確信を持てた。
    -- 直感的に正しいと思えることを，しっかりと定義して，証明を与える，ということが数学の強みです．数学だけではなく，すべての科学がそうあるべきなのですが，そのようになっているとは限らないことが悩みです．
  • グラフが同型であるとき、その同型写像は1つだけなんですか？
    -- 1つだけであるとは限りません．授業で補足します．
  • 握手補題を視覚的に見て、グラフの次数が奇数となる頂点の個数は偶数であることに納得できた。
    -- それはよかったです．これも授業で補足します．
  • 現代数学入門Bで群の同型について学び、同型という言葉に慣れていたためか、同型なグラフは理解しやすかった。同値関係なども現代数学入門Bの群で学んだ。このような繋がりを見つけられて楽しかった。
    -- 同値関係は「離散数学」でも扱っているはずなので，見直してみて下さい．
    いわゆる数学的な「構造」と呼ばれるものにはたいてい「同型」という概念が定義できます．群においては同型の他に準同型というものがあって，それが群の性質を調べる上で重要な役割を果たします．実をいうと，グラフにも準同型というものがあるのですが，これはちょっと進んだ話なので，この講義では扱いません．

• 2回のレポート提出により，成績の評価を行います．
• 全体成績について
  • 受講者数 (履修登録者数相当) は95で， 90点以上 (S) が10人 (約11%)， 90点未満80点以上 (A) が7人 (約8%)， 80点未満70点以上 (B) が12人 (約13%)， 70点未満60点以上 (C) が12人 (約13%)， 60点未満 (D) が54人 (約57%) です．
  • レポート1とレポート2の一方でも提出した人の総数は83で， 90点以上 (S) が10人 (約12%)， 90点未満80点以上 (A) が7人 (約8%)， 80点未満70点以上 (B) が12人 (約14%)， 70点未満60点以上 (C) が12人 (約14%)， 60点未満 (D) が42人 (約51%) です．
• 第2回レポート
  • レポート課題 (PDF)
  • 問題4.1の図のファイル
  • 問題5の図のファイル
  • 提出締切：8月24日(火) 23:59
  • 素点分布 (返却後の修正分があってもそれは反映されません．この後に示す得点や平均点も同様です．)
    
    
  • 提出した人の数は58，平均点は34.07 (50点満点)． 45点以上 (S相当) が11人 (約19％)， 45点未満40点以上 (A相当) が11人 (約19％)， 40点未満35点以上 (B相当) が6人 (約10％)， 35点未満30点以上 (C相当) が10人 (約17％)， 30点未満 (D相当) が20人 (約34％) です．
  • レポートは返却しますので，不明な点がある場合はご連絡ください．ただ，経験上，点数が「上がる」ことはほぼありませんので，ご了承ください．一方で，レポートに書かれているメモは，あくまでも私が個人的な確認のために書いているものであって，フィードバックを目的としたものではありません．その点もご了承ください．そのため，何もコメントが書かれていない部分に全く問題があるというわけでもありませんし，何か書いてあってもそれが減点の理由になっていない場合もあります．
  • 講評
    • 総評：「全体的にできている問題」と「全体的にできていない問題」の差が大きいように感じました．得点が高い人は「全体的にできていない問題」ができている人です．下で述べる通り，問1と問5は「全体的にできている問題」で問2と問3は「全体的にできていない問題」です．これは出題するときから大体わかっていて，問1, 4, 5は小問に分かれているので，点を得やすく，問2, 3は小問に分かれていないので，点を得にくいという構造があります．そのため，問2, 3の答案については，はじめから正しくない直感に基づいて文章を進めていては，正しい解答にたどり着けません．これは各問に対して下でも述べます．
      以下，それぞれの問題に対する寸評です．
    • 問題1：最大流を用いたモデル化に関する問題．平均点は8.83． よくできていました．容量が無限大である弧の容量を省略する場合は，それをしっかりと述べて下さい (そうでなければ読み手が分かりません)．
    • 問題2：連結度に関する問題．平均点は5.30． できている人とできていない人の差が大きいように感じました．この問と次の問題3に共通することですが，「等号が成立する (つまり，左辺が最小となる) 場合を考えて，それだけ証明すればよい」という方針は大抵破綻します．なぜかというと「等号が成立する場合」がいつなのか，ということを正確に書き下すことは，問われている不等式を証明することよりも圧倒的に難しいからです．普通の数学的精神を持ち合わせていれば，一般の場合に不等式を証明し，その後で等号が成立する場合を考えるものです．それは，この授業でさんざんやってきたはずである双対性の考え方につながります． なお，正しい証明は3行ぐらいで終わります．メンガーの定理を用いている (正しい) 解答もありましたが，メンガーの定理を使わなくても3行ぐらいで証明できます．
    • 問題3：彩色に関する問題．平均点は4.19． できている人とできていない人の差が大きい問題でした．問題2のところでも述べましたが「等号が成立する (つまり，左辺が最小となる) 場合を考えて，それだけ証明すればよい」という方針は大抵破綻します．「完全グラフが辺数最小の場合になる」と述べている答案が散見されましたが，この問題の主眼はそれを証明することです．そのため，それを無証明で述べているだけの答案は0点です．また，「染色数が $k$ のグラフは，頂点数 $k$ のクリークを含む」と述べている答案もありましたが，これはシンプルに正しくありません．これは講義でも扱っています．これに依拠している答案もほぼ0点です．
    • 問題4：幾何学的なグラフの表現と彩色に関する問題．平均点は7.02． アイディアをしっかりと文章で表現できていない答案が散見されました．あまり図に頼ってはいけません．また，「領域内のどの2点間の距離も $\sqrt{2}$ 以上」だから，その中に中心を持つ2つの単位正方形は交わる，というのは理由として弱いです．たとえば，その領域が円であれば，円の縁に中心を持つ2つの単位正方形は交わらないことがあります．一方，本質を理解している答案は，まず2つの単位正方形が交わるための必要十分条件を書き下しています．何かを参考にして自分の文章を紡ぐ場合には，もとにしたものをしっかりと理解する必要があります．
    • 問題5：平面性とマイナーに関する問題．平均点は8.73． よくできていました．小問1, 2とも答えは「Yes」です．こう並んでいると片方の答えは「Yes」でもう一方は「No」だと思ってしまうのはよくない癖です．小問3でワグナーの定理を使う必要はありません (が使っても正答としています)．
• 第1回レポート
  • レポート課題 (PDF)
  • 問題4の図のファイル
  • 提出締切：6月11日(金) 23:59
  • 素点分布 (返却後の修正分があってもそれは反映されません．この後に示す得点や平均点も同様です．)
    
    
  • 提出した人の数は71，平均点は32.72 (50点満点)． 45点以上 (S相当) が10人 (約14％)， 45点未満40点以上 (A相当) が7人 (約10％)， 40点未満35点以上 (B相当) が10人 (約14％)， 35点未満30点以上 (C相当) が18人 (約25％)， 30点未満 (D相当) が26人 (約37％) です．
  • レポートは返却しますので，不明な点がある場合はご連絡ください．ただ，経験上，点数が「上がる」ことはほぼありませんので，ご了承ください．一方で，レポートに書かれているメモは，あくまでも私が個人的な確認のために書いているものであって，フィードバックを目的としたものではありません．その点もご了承ください．そのため，何もコメントが書かれていない部分に全く問題があるというわけでもありませんし，何か書いてあってもそれが減点の理由になっていない場合もあります．
  • 講評
    • 総評：できている人とそうでない人の差が大きいように感じました．また，リアルタイムの授業に出ている人 (の名前を憶えているので，その人) は得点が高い傾向があるように思いました．もちろん，リアルタイムの授業に出ていなくても得点が高い人はいます．
      皆さんにお伝えしたいことがあります．それはまず答案というものは文章を書くものだ，ということです．文章を通して，自分の考えを伝えるための技術を磨いて下さい．これは重要な技術であり，皆さんは文章力を高める必要があります．
      その一方，上で述べた通り，私が書いたコメントは，皆さんの書いた答案を改善したり，文章の良し悪しを判断したものではありません．文章力を上げるための指導をすることも可能かもしれませんが，それをする時間は私にありません．すみませんが，このレポートの採点をこのように行うだけで，既に数週間かかっているのです．文章そのものの指導を行なおうとすれば，これの10倍は時間がかかるでしょう．そのため，皆さんの日本語としての文章力を改善することにこのレポートはほとんど役立ちません．それを踏まえた上で，返却されたレポートはご覧ください．
      以下，それぞれの問題に対する寸評です．
    • 問題1：次数に関する問題．平均点は8.82． よくできていました．満点でない人は大抵の場合に説明が不足しています．
    • 問題2：閉路に関する問題．平均点は6.20． できている人とできていない人の差が大きいように感じました．小問1について，問われていることが何であるのか理解せず，調べたことを丸写しして，平気な顔をしている答案が散見されました．小問2と3については，任意のkに対して反例を求めているのに，特定のkに対する反例しか挙げていない答案が多かったです．
    • 問題3：森に関する問題．平均点は4.65． これもできている人とできていない人の差が大きいように感じました．小問1について，これも問われていることが何であるのか，正確に理解できていないように思える答案が散見されました．また，帰納法で証明しようとしている答案も多くありましたが，その場合，何が帰納法の仮定であり，何を帰納法によって証明しようとしているのか明確に書かないと文章としてまとまりがなくなり，論理を追えなくなります．そして，大抵の場合，正しくない証明が書かれることになります．気をつけて下さい．次に，小問2ですが，正当は「真 (正しい)」です．こちらも問われていることが何であるのか，正確に理解できていないように思えました．一方で，どちらの問いについても，正しく理解できている人の答案はとてもすっきりしています．
    • 問題4：マッチングに関する問題．平均点は8.67． よくできていました．最大マッチングであることを証明するために「増加道が存在しない」と書いている答案がいくつかありましたが，その場合，増加道が存在しないことをしっかりと証明して下さい (それがしっかりと書かれている証明は満点です)．一方で，頂点被覆を使った答案はもっと簡単に書けて，満点にたどりつきやすくなっています．
    • 問題5：最大流とカットに関する問題．平均点は4.38． あまりできていませんでした．まず，式を使わずにことばで説明しようとしている答案は説明が間違っているか不正確であることが多かったです．式の変形を行うとき，何に依拠して変形を行なっているのか分からないものもよく見られました．適当に書けば何とかなるというものではありませんので注意して下さい．

• こちらをご覧ください

• 4/9 (0) ガイダンスと離散数学の復習
• 4/16 (1) グラフの定義と次数：数理
• 4/23 (2) 道と閉路：数理
• 4/30 (3) 木：数理
• 5/7 (4) マッチング：数理
• 5/14 (5) マッチング：モデル化
• 5/21 (6) 最大流：数理
• 5/28 (7) 最大流：モデル化 (1) 割当
• 6/4 (8) 最大流：モデル化 (2) 二部グラフの最大マッチング
• 6/11 (9) 最大流：モデル化 (3) カットの視点
• 6/18 (10) 連結性：数理とモデル化
• 6/25 (11) 彩色：数理
• 7/2 (12) 彩色：モデル化
• 7/9 (13) 平面グラフ：数理
• 7/16 (14) 平面グラフ：モデル化

• グラフとネットワーク (2019年度前学期，I類 (情報系))
• グラフとネットワーク (2018年度前学期，I類 (情報系))
• グラフとネットワーク (2017年度前学期，情報・通信工学科)
• グラフとネットワーク (2016年度前学期，情報・通信工学科)
• グラフとネットワーク (2015年度前学期，情報・通信工学科)
• グラフとネットワーク (2014年度前学期，情報・通信工学科)
• 数理解析 (2013年度後学期 (後半)，情報・通信工学科)
• 数理解析 (2012年度後学期 (後半)，情報・通信工学科)

• 2019年度： 中間試験 | 期末試験
• 2018年度： 中間試験 | 期末試験
• 2017年度： 中間試験 | 期末試験
• 2016年度： 中間試験 | 期末試験
• 2015年度： 中間試験 | 期末試験
• 2014年度： 中間試験 | 期末試験
• 2013年度： 期末試験 (数理解析 (後半))
• 2012年度： 期末試験 (数理解析 (後半))