離散最適化基礎論

岡本 吉央

テーマ：マッチング

注意：内容は毎年変わります

ショートカット： 講義資料 | コメント | レポート・評価 | 公式シラバス | スケジュール | 参考書 | 過去の講義

講義資料

• 1/26 (13) 一般グラフの最小費用完全マッチング：アルゴリズム (詳細)
  • スライド (1/29修正) | 印刷用スライド (1/29修正)
  • 講義動画
• 1/19 (12) 一般グラフの最小費用完全マッチング：アルゴリズム (概要)
  • スライド (1/25修正) | 印刷用スライド (1/25修正)
  • 講義動画
• 1/12 (11) 一般グラフの最小費用完全マッチング：完全双対整数性
  • スライド (1/14修正) | 印刷用スライド (1/14修正)
  • 講義動画
• 1/5 (10) 一般グラフの最小費用完全マッチング：線形計画法
  • スライド (1/7改訂) | 印刷用スライド (1/7改訂)
  • 講義動画
• 12/22 (9) 二部グラフの最小費用完全マッチング：アルゴリズム
  • スライド (12/24改訂) | 印刷用スライド (12/24改訂)
  • 講義動画
• 12/8 (8) 二部グラフの最小費用完全マッチング：線形計画法
  • スライド (12/9改訂) | 印刷用スライド (12/9改訂)
  • 講義動画
• 12/1 (7) 整数計画法の復習
  • スライド (12/4改訂) | 印刷用スライド (12/4改訂)
  • 講義動画
• 11/17 (6) 線形計画法の復習
  • スライド (11/19改訂) | 印刷用スライド (11/19改訂)
  • 講義動画
• 11/10 (5) 一般グラフの最大マッチング：アルゴリズム
  • スライド | 印刷用スライド
  • 前回の続きから始めます
  • 講義動画
• 10/27 (4) 一般グラフの最大マッチング
  • スライド (10/28改訂) | 印刷用スライド (10/28改訂)
  • 講義動画
• 10/20 (3) 二部グラフの最大マッチング：アルゴリズム
  • スライド (10/22改訂) | 印刷用スライド (10/22改訂)
  • 講義動画
  • 補足動画 (Hopcroft-Karpのアルゴリズム)
• 10/13 (2) 二部グラフの最大マッチング
  • スライド (10/14改訂) | 印刷用スライド (10/14改訂)
  • 講義動画
• 10/6 (1) マッチングの用語
  • スライド (10/7改訂) | 印刷用スライド (10/7改訂)
  • 講義動画

• 1/26 (13) 一般グラフの最小費用完全マッチング：アルゴリズム (詳細)
  • コメントありがとうございました．講義は終了となりました．レポートを忘れずに提出して下さい．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • 特にありません
    -- こちらも特にありません．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • 半年間ありがとうございました。
    -- こちらこそありがとうございました．
  • 特にありません。ありがとうございます。
    -- こちらこそありがとうございました．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • 特にありません、授業ありがとうございます。
    -- こちらこそありがとうございました．
  • 面白かったです。ありがとうございました。
    -- こちらこそありがとうございました．
  • ありがとうございました．
    図が多くてイメージがつかみやすかったです．
    -- 図を多くしてイメージをつかみやすくすることはいつも意識しています．皆さんも自分の発表を構成するときに図でイメージをつかみやすくすることを心がけて下さい．
  • ありがとうございました．基礎知識がゼロだったので，非常に難しく感じましたが，動画があって復習がしやすい環境だったので，この機会に勉強してみて良かったです．
    -- このような機会なので，動画はYouTubeに公開してしまいました．今後も機会があれば，講義動画をYouTubeに公開しようと思います．
  • わかりやすい説明で理解しやすかったです。また各回の講義全体を通して、各種の問題や理論が関連づけられていることがわかり、楽しかったです。
    -- ありがとうございます．最適化の楽しみを感じていただけたようで，うれしいです．
• 1/19 (12) 一般グラフの最小費用完全マッチング：アルゴリズム (概要)
  • コメントありがとうございました．
  • 復習します...。
    -- はい，復習をぜひお願いします．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • ありがとうございました
    -- こちらこそありがとうございました．
  • 授業ありがとうございました。
    -- こちらこそありがとうございました．
  • ありがとうございました．
    クラスルームによるレポートの返却などはあるのでしょうか？
    -- レポートを返却する予定はありません．
  • 特にありません。
    -- こちらからも特にありません．
  • 特にありません．
    -- こちらからも特にありません．
  • 特にありません。
    -- こちらからも特にありません．
  • 特にありません。
    -- こちらからも特にありません．
  • 特にありません
    -- こちらからも特にありません．
  • 特にありません
    -- こちらからも特にありません．
  • 特にありません
    -- こちらからも特にありません．
• 1/12 (11) 一般グラフの最小費用完全マッチング：完全双対整数性
  • コメントをありがとうございました．授業はあと2回となります．寒い時期なので，体調に気をつけて臨んで下さい．
  • スライド14pのスラック変数の位置はそこで正しいのでしょうか？ 1以上のものに0以上のものを足したら=1にならない気がします。
    -- すみません，間違っています．間違っているのは符号で，$+X_S$ ではなく，$-X_S$ として下さい．ご指摘ありがとうございます．
  • 難しいですね．
    -- そうですね．しっかりと復習をして下さい．
  • 特にありません
    -- 私からも特にありません．
  • 特にありません。
    -- 私からも特にありません．
  • 特にありません、授業ありがとうございます。
    -- こちらこそありがとうございます．
  • ありがとうございました
    -- こちらこそありがとうございます．
  • ありがとうございました
    -- こちらこそありがとうございます．
  • ありがとうございました。
    -- こちらこそありがとうございます．
  • ありがとうございました。
    -- こちらこそありがとうございます．
  • ありがとうございました。
    -- こちらこそありがとうございます．
  • ありがとうございました。
    -- こちらこそありがとうございます．
• 1/5 (10) 一般グラフの最小費用完全マッチング：線形計画法
  • コメントをありがとうございました．
  • 今年もよろしくお願いします。
    -- 今年もよろしくお願いします．
  • 課題難しかったです
    -- しっかりと取り組んでいただき，ありがとうございます．
  • ありがとうございました。
    -- ありがとうございました．
  • ありがとうございました。
    -- ありがとうございました．
  • ありがとうございました。
    -- ありがとうございました．
  • ありがとうございました。
    -- ありがとうございました．
  • ありがとうございました。
    -- ありがとうございました．
  • 特にありません、授業ありがとうございます
    -- ありがとうございました．
  • 特にありません。
    -- 特にありません．
  • 特にありません
    -- 特にありません．
  • 特にありません
    -- 特にありません．
  • 特にありません
    -- 特にありません．
• 12/22 (9) 二部グラフの最小費用完全マッチング：アルゴリズム
  • コメントをありがとうございました．レポートの提出締切は1月4日ですので，忘れずにお願いします．
  • ハンガリー国内でもハンガリー法と呼ばれるのでしょうか？もし、"日本法"があったら奇妙に感じるかもしれません。
    -- ハンガリー国内，という形かどうか判断は難しいですが，ハンガリー出身の研究者がHungarian methodと呼んだり書いているのは見たことがありますし，敬意をもって受け入れられているように思います．
    なお，英語としてのHungarian method は「ハンガリー人の手法」という意味なのだと思います．それを日本語では「ハンガリー法」と訳しています．似たものにChinese remainder theorem というのがあって，これは「中国人剰余定理」とか「中国剰余定理」と訳されたりします．Chinese postman problemというのもあります．
  • 復習不足だったので、こんがらがりました。
    -- はい，しっかりと復習をして下さい．
  • 計算量の解析、なんだか不思議だなと思いました。
    -- 計算量の解析では，何かしらの単調性を使うことが多いです．ハンガリー法では，Mの要素数が大きくなるか，そうではない場合は B∩C の要素数が大きくなる，という単調性を使って証明をしているのです．
  • ありがとうございました
    -- こちらこそありがとうございました．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • 授業ありがとうございました。
    -- こちらこそありがとうございました．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にないです。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
• 12/8 (8) 二部グラフの最小費用完全マッチング：線形計画法
  • コメントをありがとうございました．
  • 特にありません
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありませんでした。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にないです。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • ありがとうございました
    -- こちらこそありがとうございます．
  • ありがとうございました。
    -- こちらこそありがとうございます．
  • ありがとうございました
    -- こちらこそありがとうございます．
  • ありがとうございました。
    -- こちらこそありがとうございます．
  • ありがとうございました。次回もよろしくお願いいたします。
    -- こちらこそよろしくお願いします．
  • 授業ありがとうございました。最近楽しかったことを教えてください
    -- 最近楽しかったことは特にない気がします．残念な生活ですね．
  • 今日の授業はちょっと難しいと思います。
    -- 線形計画法の復習をしっかりとお願いします．
  • スライドにAx<1や1の転置などが出てきますがこの1は要素がすべて1の列ベクトルのことでしょうか？
    -- はい，その通りです．授業の中でも説明したのですが，分かりにくくてすみません．
  • スライドで出てきたあの碁盤目状のグラフは二部グラフなのですか？（これをCommentScreenで質問しようとしたらなぜかできませんでした．ちなみに絵文字を送ったら2倍表示されてました）
    -- はい，碁盤目状のグラフは二部グラフです．次の図のように2つの部分に分けられます．
    
  • 線形計画緩和を使って解ける問題の種類に、何か特徴はあるのでしょうか。
    -- 組合せ最適化の専門家の間では，特徴があると思われていて，それは「凸多面体の整数性」ということばで表されます．これは後の方の講義で扱う予定でいます (が予定通り進むかどうかは分かりませんので，ご了承ください)．
• 12/1 (7) 整数計画法の復習
  • コメントをありがとうございました．
  • 特になし
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特になし
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • ありがとうございました。
    -- こちらこそありがとうございます．
  • ありがとうございました。
    -- こちらこそありがとうございます．
  • ありがとうございました
    -- こちらこそありがとうございます．
  • 授業ありがとうございました
    -- こちらこそありがとうございます．
  • クリスマスプレゼントはレポート課題ですか？
    -- そうなれば幸いです :-)
  • 言い表したいことを定義としてきちんと表現できるのは、すごいなと思いました。端点の定義を考えた人とか...。
    -- そうですね．端点の定義はそんなに直感的ではないと思いますが，直感的に「端点」だと思うことを言い当てている雰囲気はありますね．
  • 今日の授業は定義が多くて、連続最適化との共通の部分がある
    -- 関連分野との共通部分を見出せるのはいいですね．
  • 凸多面体の端点でも辺（2次元のとき）の上でもない点が最適解になることはないのですか．
    -- あります．極端なことをいうと，目的関数が $0$ (ベクトル $c$ がゼロベクトル) のときを考えると，許容領域の任意の点 (任意の許容解) が最適解になります．
• 11/17 (6) 線形計画法の復習
  • コメントをありがとうございました．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特になし
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • なし
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 本日もありがとうございました
    -- こちらこそありがとうございました．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • ありがとうございました
    -- こちらこそありがとうございました．
  • 授業ありがとうございました。
    -- こちらこそありがとうございました．
  • 内容はよくわかりました。
    -- それはよかったです．ぜひ復習してください．
  • 今回の証明は以前と比べて簡単だった
    -- 前回まではグラフに関する事項を証明していたので，今回のおもむきはいままでとかなり違うように感じられたでしょうね．
  • 線形計画法は重要だと思います。
    -- 実際に重要だということをあとの授業で見ていきます．
  • 任意の線形計画問題を効率解くアルゴリズムは存在するのでしょうか。
    -- なにをもって「効率」と呼ぶのか，ということによって回答は変わってきます．まず，理論上の話をしますが，線形計画問題を多項式時間で解くアルゴリズムがあります．一方で，線形計画問題はP完全であるということも知られていて (NP完全ではなくP完全です)，例えば，理論上，多項式個のプロセッサを用いて対数多項式時間で解けないのではないかと思われています． (P=NC予想に関係します．P=NP予想ではないです．)
    一方，実践上の話があります．多くの最適化ソルバが開発されており，線形計画問題はたいてい問題なく解けます．例えば，変数の数が1万程度だったら，何も考えずに，ソルバで解かせようと思っていいと思います．それで解けない場合もありますが，そういうことはあまりないので，解けないことが分かってから，いろいろと工夫をすることになります．
  • いろんな分野の知識を取り入れることの大切さを改めて心得ました。
    -- そうですね．持論ですが，たいていイノベーションというのは，その分野の中だけでは起こらなくて，他の分野や考え方を持ち込むことによって起こると思います．そういう視点で勉強してみると，いろいろなものの見え方も変わってくると思います．
  • 相補性定理が何を表しているのか分からなかったです．
    -- これはこの講義の範囲を超えるので，説明不足になりました．すみません．私が以前行った講義では幾何学的なイメージをお伝えしているので，参考にして下さい．
  • 線形計画法の基礎に関するおすすめの参考書などありますか？
    -- 残念ながらありません．数理最適化や最適化理論に関する書籍は多く，その中で線形計画法はよく扱われているのですが，私の不満は，それらの書籍がどれも「単体法」の説明に大きな紙面を割き，しかも，それが割と初めの方に出てくることです．私自身，単体法が重要でないと主張したいわけではないですが，これが「基礎」なのかと問われると，そうではないと思っています．単体法が基礎であると呼ぶには難しすぎると思いますし，単体法を知らなくても線形計画法を使うことはできます．しかし，「線形計画法の基本定理」と呼ばれている定理や「双対定理」と「相補性定理」を学ばずに数理最適化を使うことはほぼ無理です (それらを知らずに使えていると思えているうちは，使い方が浅いと思います)．百歩譲って，単体法によって得られる最適基底解が重要である，という意見もあるかもしれませんが，それならば最適基底解の性質を論じれば十分であって，単体法の説明がそこに出てくる必然性は (基礎を論じるという立場ならば) ないと思います．
    一般的に言えるのですが，数理最適化や最適化理論の書籍は，アルゴリズムの説明に多くの紙面を割きすぎています．私自身はアルゴリズムを研究しているので，もちろんそのような書籍があるのはよいと思いますし，うれしいですが，そのような本は今となっては数理最適化を研究しようとする人向けの本になってしまっていると思います．一方で，実際に数理最適化や最適化理論を使う人の立場から見た「ユーザ視点の教科書」がほとんどありません．そのため，おすすめの参考書はない，ということになります．
    なお，「単体法をなぜ教えるのか？」ということを私は20年前ぐらいからずっと言ってますが，専門家にはだいたい同意してもらえません．
• 11/10 (5) 一般グラフの最大マッチング：アルゴリズム
  • コメントをありがとうございました．来週からは内容がガラッと変わりますが，今までの内容も後で使いますので，そのつもりでいてください．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • ありがとうございました。
    -- こちらこそありがとうございます．
  • 授業ありがとうございました。先生の好きなアルゴリズム を教えてください
    -- たくさんありますが，例えば color coding です．学生のときに論文を読んで感動した覚えがあります．
  • アルゴリズムの動作例を丁寧に説明してくれてとても助かりました。
    -- それはよかったです．自分でも例を作って，試してみると，よりよく分かると思いますので，ぜひやってみてください．
  • 最大マッチングのアルゴリズムの説明が分かりやすかった
    -- 分かった気になるのは簡単なのかもしれないので，ぜひ自分自身でも試してみて下さい．
  • 雰囲気よくわかりました．証明は途中で追えなくなることが多いので，録画があって良かったなと思います．
    -- はい，ぜひ復習してください．
  • 図を用いた説明がわかりやすく、最大マッチングのアルゴリズムの雰囲気は、わかった気がします。
    -- 図を用いて説明することには力を入れています．皆さんも，何かを説明するときに図を用いるようにして下さい．
  • 間が空くとよく分からなくなりがちですね。復習を心掛けます。
    -- そうですね．調布祭片付けでまた間があくので，復習を心がけて下さい．
  • 今日の授業で花という概念を知りました。今日習ったアルゴリズムは煩わしいけど、面白いと思います。
    -- 「煩わしい」というのは面白い表現ですね ;-)
  • 花の縮約と最大マッチングの証明は私にはちょっと難しいですが、この証明を覚えなければなりませんか。
    -- なにごとにも当てはまりますが，覚えようとしないで下さい．覚えようと思って覚えることは無駄です．そんな無駄なことはしないようにして下さい．
  • 私が聞き忘れていたら申し訳ないのですが，どうして花という名前なのですか？
    -- これは私もよく分からないのですが，見た目が花に見えるから，ということだと推測します．花に見えるかどうか，というのは主観によるとも思いますが．
  • blossom と flower の違いって何でしょうね
    -- 英語一般のはなしだと見なします．blossomというのは木になる花で，flowerというのは茎になる花のことだそうです．例えば，サクラはblossomでキクはflower，ということです．
  • アルゴリズムの例のところ（スライドP77）、黄色の部分は花ではなく、Cの気がします
    -- Cが花なので，これは正しいです．分かりにくいのは確かですね．この例の場合，Cの中のマッチングの辺で飽和されない頂点にくっついている偶数長の交互道の長さが0になっています．
  • BT公式で使用するUがアルゴリズムの停止時に得られるのはすばらしいと思いました。
    -- そうですね．最適化アルゴリズムにおいては，このように「最適性の保証」を得ることが重要になります．重要な考え方なので，ぜひ身につけて下さい．
• 10/27 (4) 一般グラフの最大マッチング
  • コメントをありがとうございました．
  • ありがとうございました。次回もよろしくお願いいたします。
    -- こちらこそよろしくお願いします．
  • ありがとうございました
    -- ありがとうございました．
  • 特になし
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にない
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 雑談ですが、最近楽しかったことを教えてください
    -- 最近，いわゆる「オンライン飲み会」というのをして，それは楽しかったです．
  • 最近冷えてきましたね
    -- そうですね．季節の変り目は体調を崩しやすいので，ご注意ください．
  • 難しいので、復習します。
    -- 前回予告したように，今回は難しかったと思います．ぜひ復習をして下さい．
  • 数式が多くてどれがどの式か時々混乱しそうになった。
    -- 1つずつ追っていくことはできると思うので，丁寧に見直してみて下さい．
  • Tutteの定理の証明難しかったです．もう一度見直してみたいと思います．
    -- はい，よろしくお願いします．
  • 授業がどんどん難しくなってきたので、授業後に復習する必要があります。
    -- 復習は重要なので，励行して下さい．
  • Tutte の60%は 't' でできている
    -- そのとおりですね :-)
  • G-Uの各奇成分とUの頂点を結ぶ辺に名前はありますか．
    -- 特別な名前を聞いたことはないです．
  • 非常にわかりやすくてよい講義だと思います．
    -- ありがとうございます．
  • わかりやすかった：）
    -- ありがとうございます．
  • 今回の授業はちょっと難しいです、留学生だから少し先生の話は理解できませんから、薦めの本があるかどうか教えていただけませんか。よろしくお願いいたします。
    -- このページの下の方に参考書を挙げてます．
  • 講義資料のグラフはどのように書いているのでしょうか。何か良い描写ツールはありますか。
    -- 私はipeを使っています．
• 10/20 (3) 二部グラフの最大マッチング：アルゴリズム
  • コメントをありがとうございました．
  • 印刷用スライド47ページの辺数+1の+1の位置はそれぞれ逆ではないでしょうか？
    -- はい，その通りです．ご指摘ありがとうございます．スライドも修正しました．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • 特にありません。
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • なし
    -- ありがとうございます．何もなくてもコメントは提出し続けて下さい．
  • ありがとうございました
    -- こちらこそありがとうございました．
  • 増加道アルゴリズムの証明が途中からわからなくなった．
    -- 分からないところはすかさず質問するか，何を質問したらよいか分からない場合は，とりあえず止めて下さい．止めてから質問を考えるか，「分からない」というか，どちらかをしてみて下さい．とりあえず何かしらの行動をすることが重要です．皆さんのバックグラウンドは様々です．誰かにとって簡単なことでも他の人にとっては難しいかもしれません．私は皆さんのバックグラウンドを正確に把握しているわけではありませんので，皆さんから行動を起こしてもらわないと分からないのです．
  • Hopcroft-Krapのアルゴリズムが全然分からなかったです．
    -- この部分はあまり理解してもらおうとして話をした，というよりは，雰囲気だけ伝えるつもりだったので，「全然分からなかった」という感想を持ってもらうことで問題ありません．
  • 復習、します。。
    -- はい，よろしくお願いします．
  • 難しいので、復習します。
    -- はい，よろしくお願いします．
  • 難しいので、復習します。
    -- はい，よろしくお願いします．
  • 図がとてもわかりやすかった
    -- 図で例示したり，雰囲気を伝えることには力を入れています．皆さんも何かを説明しようとする際には，図を使えるかどうか考えてみて下さい．
  • 極大な最短有向道の集合どうやって見つけるのを考えました
    -- これは幅優先探索を使うことで可能になります．幅優先探索について調べてみて下さい．
  • 今日は二部グラフの増加道の発見法と最適性の保証法について勉強しましたが、最大マッチングを見つけるアルゴリズムをもっと深く理解しました。
    -- それはよかったです．もしできたら，自分でアルゴリズムを実装してみるともっと深く理解できると思います．ぜひ試してみて下さい．
  • Dinic's AlgorithmとHopcroft-Karpの差分って有向グラフか二部グラフかの違いだと思っていますがいかがでしょうか
    -- Dinicのアルゴリズムは最大流問題に対するアルゴリズムなので，そもそも考えている問題が違う，という違いがあります．ただ，二部グラフの最大マッチング問題を最大流問題としてモデル化する，という方法があり，その方法を経由して，二部グラフの最大マッチング問題をDinicのアルゴリズムで解くことを行うと，実質的にHopcroft-Karpのアルゴリズムで解いていることと同じになると思います．
  • |M|≧|C|の証明において、『したがって、|M|≧|B∩Rを飽和する…』とありますが、ここで等号ではなく不等号である理由が上手く理解できませんでした。
    -- A-Rを飽和するMの辺とB∩Rを飽和するMの辺以外にもMの辺があるかもしれないからです．実際に，そのようなMの辺はないのですが，ここまでの議論でないことまでは証明できていないので，不等号になっています．
  • 次回の内容は難しいとのことなので楽しみにしています
    -- はい，お楽しみに．
  • マクドナルドは好きですか？
    -- 最近いってないです．毎日大学にいっていた頃は，甲州街道沿いのマクドナルドで朝食をとっていたこともありました．
• 10/13 (2) 二部グラフの最大マッチング
  • コメントをありがとうございました．
  • 特にありません。
    -- ありがとうございます．特になくても，このコメントは書くようにして下さい．
  • 特にありません。
    -- ありがとうございます．特になくても，このコメントは書くようにして下さい．
  • 序盤で置いて行かれました。
    -- 質問をして下さい．私は置いていっているつもりがないので，止めていただかないとただただ進んでいきます．それは私の本意ではありません．よろしくお願いします．
  • 各証明を深く理解しておく必要はありますか？
    -- 自分が必要だと思ったら深く理解しようとして下さい．勉強とはそういうものだと思います．
  • 自分の中で飽和という単語の意味が理解しきれておらず序盤は置いて行かれました
    -- スライドの5ページ目で説明されています．見返してみて下さい．
  • 気を抜いたら途中でついていけなくなってしまったので、もう一度見直します
    -- はい，よろしくお願いします．
  • 復習します
    -- はい，よろしくお願いします．
  • 証明は難しいです。
    -- 離散数学に慣れていないと難しく感じるところはあると思います．
  • 強双対性の定理の証明が難しかった
    -- そうですね．私も難しいと思います．
  • マッチングが僕に牙を向き始めてきて，ついて行けるか心配です．
    -- 理解できないことがでてきたら，質問をお願いします．
  • 途中から自分の理解が追いつかなかったので資料を読み直してきます。
    -- はい，しっかりと復習をして下さい．
  • わかりやすかったです
    -- すぐにわかりにくくなるので，期待 (？) していて下さい．
  • わかりやすくてよかった。
    -- それはよかったです :-)
  • 本番って感じですね…分かりやすかったです
    -- まだ2回しかやってないのです．;-)
  • 定理とその使え方を覚えて、具体的な証明はおぼえなくてもいいですか（証明が使った二重の数え上げなどの方法は覚えておきます）
    -- 何も覚えないで下さい．覚えようとして覚えるのは無駄です．何かをやっていて結果的に覚えてしまう，ということと，覚えようとして覚える，というのはまったく違うことで，覚えようとして覚えるのは，覚えることが目的化してしまっています．そんなことをしている暇はありません．
  • マッチングと頂点被覆の弱双対性を証明するときの二重の数え上げのところは握手補題の証明（頂点，辺の立場からそれぞれ数え上げるやつ）と似てるなぁと思いました
    -- 証明法は極めて似ていますね．ただ，握手補題は等式で，弱双対性は不等式なので，その違いは重要です．
  • 今回の授業は面白いと思います。
    -- 面白いと思っていただけるのはよかったです．:-)
  • 「結婚定理」という名前の由来が気になりました．グラフに関連する用語で「結婚」という言葉は稀に使われるのでしょうか？
    -- 「結婚」ということばはマッチングに関する分野でしか聞かない気がします．
  • 弱双対性と強双対性、ありがたい性質だな、と思いました。
    -- そうですね．今後も重要になってきます．
  • 双対性はいろいろな分野で見かけますね。あまり同じものだととらえてはいませんでした。
    -- 数学や物理学では，いろいろな双対性がでてきますね．最適化における双対性は線形代数の双対性に関連がありますが，それはこの講義の後半の話題と関係します．(しかし，その関連がこの講義で重要になるわけではないですし，線形代数の双対性が分からなくてもまったく問題ありません．)
  • Ore(オーレ)の定理があるなら、カフェ・オーレの定理もありそう（なさそう）
    -- 残念ながら，ありません．;-)
  • 今日も授業ありがとうございました。マッチングが具体的に我々の生活にどのように役立つかが知れるともっと面白いと思いました
    -- ありがとうございます．論点が2つあります．(1) どのように役立つか，という点は学域 (学部) の講義で扱っているので，この講義では扱う予定がありません．(2) どのように役立っているか，という視点より，皆さんがどのように役立てられるか，ということを考えていただくのが重要だと思います．いまどのように役立っているのか，ということは，今の技術，つまり，古い技術のはなしになって，そこから新しいことを生み出すのは難しいと思います．それよりは，いままで役立っていなかったところにここで学んだことを活かせるかどうか考える方が有益です．ぜひ，そのような視点で考えてみて下さい．
• 10/6 (1) マッチングの用語
  • コメントをありがとうございました．以下のように掲載されます．
  • これからよろしくお願いします。
    -- はい，よろしくお願いします．
  • よろしくお願いいたします
    -- こちらこそ，よろしくお願いします．
  • 先行履修です．よろしくお願いします．
    -- はい，よろしくお願いします．
  • いいです
    -- 何がいいでしょうか？ ;-)
  • 特にありません
    -- はい，特になくても，このコメントは出し続けるようにして下さい．お願いします．
  • 離散最適化基礎論さん対戦よろしくお願いします
    -- 私の名前は離散最適化基礎論ではありません．
  • 私にとっても2分間の休憩は内容の整理ができてありがたかったです。
    -- それはよかったです．休憩の使い方は皆さんの自由ですので，ぜひ活かして下さい．
  • 最適化には全く詳しくなく、むしろ苦手意識があったので履修を迷っていましたが、非常にわかりやすく、面白く講義を聴くことができたので、履修しようと思います。
    -- 今後わかりにくくなることもあると思うので，遠慮なく質問して下さい．
  • まとめられた講義で非常に興味深かったです
    -- そう感じていただけてよかったです．:-)
  • マッチングをしっかり学びたかったのでうれしいです。よろしくお願いします。
    -- こちらこそよろしくお願いします．
  • 最大マッチング・極大マッチングのところで置いて行かれてしまいました。
    -- 極大マッチングは今後使わないので，紹介しない方がよかったかもしれません．すみません．
  • 最大と極大がごちゃまぜになりそうでした
    -- そうですね．定義のみかけはまったく違うものなので，しっかり定義を理解するようにして下さい．
  • 定義の図解があるので非常に理解しやすかったです．
    -- 図を使って説明をすることは心がけています．図が減ってきたら，私自身が理解できていないと思って下さい．
  • やはり受講する側としてはオンラインの方が圧倒的に楽です、教員側はそうでもないのでしょうか
    -- オンラインと対面はそれぞれの良さがあると思います．動画サイトのMV視聴とライブハウスの生ライブの役割分担に似てるのではないでしょうか．別の言い方をすれば，教員は今後「ライブハウスの生ライブ」で集客を行うだけの覚悟が必要だと思います．
  • これまで何を述べたか、これから何を議論していきたいかがはっきりしていてわかりやすかったです。
    -- ありがとうございます．今後もその方針は心がけていきます．
  • 増加道の話題において「ではない」が次のスライドに記述されているが、資料を見返した際に混乱の元になるので避けたほうが良いと感じた。
    -- その通りですね．ありがとうございます．提案に従ってスライドを改訂しました．
  • 増加道を用いた最大マッチングアルゴリズムは学部の実験で扱いましたが、当時は細かく理解していなかったので今回学べて良かったです。
    -- それはよかったです．同じような内容を繰り返し学ぶと理解が深まると思います．
  • 対称差から、連結成分の特徴を考えて、Mの増加道を考えていくアイデアが、面白いな、と思いました。言われてみればそうだけれども、一個づつ性質を確かめて積み上げてみないとわからないな、と思いました。
    -- このアイディアはそんなに簡単ではないと思います．だからこそ「定理」と呼べるのだと思います．
  • 非常にわかりやすくてありがとございます。ちなみに日本語の参考書とかはありますか
    -- 参考書に挙げているKorteとVygenの本には和訳があります．他には『応用数理計画ハンドブック』というものに，マッチングについて詳しく書かれている章があります．グラフ理論的な側面については，ディーステルの『グラフ理論』という本に説明があります．ただし，この『グラフ理論』という本はかなり難しいです (そして，離散最適化の本ではありません)．
  • 先生は離散最適化基礎論のどの点が魅力的だと感じるか教えてください
    -- 1つには，数学が問題解決やアルゴリズム設計に直接役立つことが分かることがあります．

• 2回のレポート提出により成績評価を行います．
• レポート1
  • レポート課題，提出要項
  • 提出自体はGoogle Classroomで行って下さい．
• レポート2
  • レポート課題，提出要項
  • 提出自体はGoogle Classroomで行って下さい．

• こちらをご覧ください

• 10/6 (1) マッチングの用語
• 10/13 (2) 二部グラフの最大マッチング
• 10/20 (3) 二部グラフの最大マッチング：アルゴリズム
• 10/27 (4) 一般グラフの最大マッチング
• 11/3 文化の日のため休み
• 11/10 (5) 一般グラフの最大マッチング：アルゴリズム
• 11/17 (6) 線形計画法の復習
• 11/24 調布祭片付けのため休み
• 12/1 (7) 整数計画法の復習
• 12/8 (8) 二部グラフの最小費用完全マッチング：線形計画法
• 12/15 国際会議のため休み
• 12/22 (9) 二部グラフの最小費用完全マッチング：アルゴリズム
• 12/29 冬期休業
• 1/5 (10) 一般グラフの最小費用完全マッチング：線形計画法
• 1/12 (11) 一般グラフの最小費用完全マッチング：完全双対整数性
• 1/19 (12) 一般グラフの最小費用完全マッチング：アルゴリズム (概要)
• 1/26 (13) 一般グラフの最小費用完全マッチング：アルゴリズム (詳細)
• 2/2 (14) 予備
• 2/9 授業等調整日

• B. Korte, J. Vygen, Combinatorial Optimization, 6th Edition, Springer, 2018.
• W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, Wiley-Interscience, 1997.
• C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization Algorithms and Complexity, Dover, 1998.
• L. Lovász, M. Plummer, Matching Theory, AMS, 2009.
• D.B. West, Introduction to Graph Theory, 2nd Edition, Prentice-Hall, 2001.
• その他の研究論文

• 離散最適化基礎論 (2019年度) テーマ：離散最適化における計算困難性
• 離散最適化基礎論 (2018年度) テーマ：理想グラフに対する組合せ最適化
• 離散最適化基礎論 (2017年度) テーマ：幾何的被覆問題
• 離散最適化基礎論 (2016年度) テーマ：グラフの木分解
• 離散最適化基礎論 (2015年度) テーマ：組合せ最適化におけるマトロイドの役割
• 離散最適化基礎論 (2014年度) テーマ：組合せ最適化における線形計画法の利用
• 離散最適化基礎論 (2013年度) テーマ：局所探索法の理論的側面
• 離散最適化基礎論 (2012年度) テーマ：ゲーム理論における離散構造とアルゴリズム