Reinhard Diestelのグラフ理論を読み終えました。感想を残しておきます。
maspyさん主催の輪読会(maspyさん、熨斗袋さん、gazelleさん、kort0nさん(途中まで)、kanra824さん(途中まで)、僕)でこの本が選ばれました。
開催日時・回数は毎週月曜日夜9時から12時、合計30回(2020年5月25日~2021年1月4日)です。輪読したのは合計90時間ですが、自分の担当の会の準備には一回当たり20時間は使いました。復習の時間もあるので、合計300時間ぐらいです。独学だともっと時間が掛かっていたと思います。
日本語版と英語版がありますが、私は英語版をメインに読みました。free preview で全てのページが読めます。私は free preview で読みました。紙で読みたい場合は英語の書籍を買うのがよいと思います。
日本語版(Amazon)は第2版(第3, 4, 5版の翻訳は出ていない)がありますが、絶版なので定価の3倍以上の値段がついています。私は図書館で一部読みました。英語が分かりにくい部分を、日本語版で補填するためです。ただ、5版は2版に比べて証明が洗練されていたり、新しい章(無限グラフ)が追加されていたりするので、日本語版より英語版をメインに進めていくのがよいと思います。
各章の感想を一言ずつ書いていきます。前提として、私はグラフ理論の専門書を読むのは初めてでした。
- The Basics
- 基本とあるのに「マイナー」「基本閉路・基本カット」のような未履修の概念が出てきて心が折れかけました。
- Matching, covering and packing
- Tutte Theorem と演習問題4が印象に残っています。
- Connectivity
- 2点連結グラフ、3点連結グラフの構成は競プロで生かせそうだと思いました。輪読した内容で作問したい。
- Planar graphs
- 有名な Kuratowski’s theorem の証明が履修できて嬉しい。この章に限らないですが、パズルのような証明が多かったです。
- Colouring
- リスト彩色も競プロで出せそうですね。
- Flows
- 競プロで Flow のことは知っているつもりだったが、新概念がいろいろ登場。
- Extremal graph theory
- regularity lemma の理解に苦しみましたね……。
- Infinite graphs
- 無限遠の頂点(end)や位相空間という謎概念が出てきて一番苦しい章でした。
- Ramsey theory for graphs
- Ramsey数は履修済みだったのですが、ほかにもいろいろ変種があって、へーと思いました。
- Hamilton cycles
- hamiltonian sequence の必要十分条件が導けることにびっくり。
- Random graphs
- 私が担当。計算ばかりですぐに終わりました。
- Minors, trees and WQO
対象者は、グラフ理論(≠グラフアルゴリズム)をしっかり勉強したい人だと思います。演習問題もめっちゃあります(ほとんど解いてない)。ほかの参加者のレート高すぎて怖いんですが、それでも苦戦してるパートがあったので、簡単な本ではないと思います。この本の内容で何か作問したいです。
Comments