Skip to content →

グラフ理論(R. Diestel)読んだ

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版に比べて証明が洗練されていたり、新しい章(無限グラフ)が追加されていたりするので、日本語版より英語版をメインに進めていくのがよいと思います。

各章の感想を一言ずつ書いていきます。前提として、私はグラフ理論の専門書を読むのは初めてでした。

  1. The Basics
    • 基本とあるのに「マイナー」「基本閉路・基本カット」のような未履修の概念が出てきて心が折れかけました。
  2. Matching, covering and packing
    • Tutte Theorem と演習問題4が印象に残っています。
  3. Connectivity
    • 2点連結グラフ、3点連結グラフの構成は競プロで生かせそうだと思いました。輪読した内容で作問したい。
  4. Planar graphs
    • 有名な Kuratowski’s theorem の証明が履修できて嬉しい。この章に限らないですが、パズルのような証明が多かったです。
  5. Colouring
    • リスト彩色も競プロで出せそうですね。
  6. Flows
    • 競プロで Flow のことは知っているつもりだったが、新概念がいろいろ登場。
  7. Extremal graph theory
    • regularity lemma の理解に苦しみましたね……。
  8. Infinite graphs
    • 無限遠の頂点(end)や位相空間という謎概念が出てきて一番苦しい章でした。
  9. Ramsey theory for graphs
    • Ramsey数は履修済みだったのですが、ほかにもいろいろ変種があって、へーと思いました。
  10. Hamilton cycles
    • hamiltonian sequence の必要十分条件が導けることにびっくり。
  11. Random graphs
    • 私が担当。計算ばかりですぐに終わりました。
  12. Minors, trees and WQO

対象者は、グラフ理論(≠グラフアルゴリズム)をしっかり勉強したい人だと思います。演習問題もめっちゃあります(ほとんど解いてない)。ほかの参加者のレート高すぎて怖いんですが、それでも苦戦してるパートがあったので、簡単な本ではないと思います。この本の内容で何か作問したいです。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA