グラフ理論入門 (翻訳)
- 通常版ダウンロード商品¥ 1,500
- サンプルダウンロード商品¥ 0
Darij Grinberg 著 An introduction to graph theory の翻訳です。 フォーマット: PDF ページ数: 359
本書について
グラフ理論の入門書です。前半では単純グラフ・多重グラフ・有向グラフ・木といった基礎的な概念の定義と性質が解説されます。後半では BEST 定理・行列木定理・彩色多項式定理・Hall の結婚定理・最大フロー最小カット定理・Menger の定理といった有名な定理が証明と共に解説されます。de Bruijn 列や魔法陣といった応用的な話題にも言及があります。 類書に比べて証明や議論が丁寧だと翻訳をしていて感じました。グラフの数学的な扱いを初めて学ぶ方におすすめです。 サンプルには「1. はじめに」と「2. 単純グラフ」が含まれます。翻訳と組版のクオリティを確認するのにご利用ください。 本書の HTML 版は https://inzkyk.xyz/graph/ で公開されています。 本書の英語版は https://arxiv.org/abs/2308.04512 にて CC0 1.0 Universal ライセンス ( https://creativecommons.org/publicdomain/zero/1.0/deed.en ) で公開されています。本書は CC0 1.0 Universal ライセンスの許諾に基づいて販売されます。
目次
1. はじめに 1.1. 本書について 1.2. 数学記号 2. 単純グラフ 2.1. 定義 2.2. 描画 2.3. 最初の事実: ラムゼー数 R(3,3) = 6 2.4. 次数 2.5. 同型 2.6. 特別なグラフ 2.7. 部分グラフ 2.8. 非交和 2.9. 歩道と路 2.10. 閉歩道と閉路 2.11. 最長路を使ったトリック 2.12. 橋 2.13. 支配集合 2.14. ハミルトン路とハミルトン閉路 3. 多重グラフ 3.1. 定義 3.2. 単純グラフと多重グラフ間の変換 3.3. 単純グラフから多重グラフへの一般化 3.4. オイラー歩道とオイラー回路 4. 有向グラフと多重有向グラフ 4.1. 定義 4.2. 入次数と出次数 4.3. 部分有向グラフ 4.4. 有向グラフへの変換 4.5. 歩道・路・閉歩道・閉路 4.6. 強接続性と弱接続性 4.7. オイラー歩道とオイラー回路 4.8. ハミルトン路とハミルトン閉路 4.9. 逆グラフと補グラフ 4.10. トーナメント 4.11. トーナメントに関する練習問題 5. 木と有向木 5.1. 成分と閉路に関する一般的な性質 5.2. 森と木 5.3. 葉 5.4. 全域木 5.5. グラフと木の中心 5.6. 有向木 5.7. 有向木 vs. 木 5.8. 全域有向木 5.9. BEST 定理: 主張 5.10. 特定の頂点を終根とする有向木 5.11. BEST 定理: 証明 5.12. 全域有向木に関する系 5.13. 全域有向木と全域木 5.14. 行列木定理 5.15. 無向グラフに対する行列木定理 5.16. de Bruijn 列 5.17. ラプラシアンに関する他の話題 5.18. ラプラシアンの左零空間 5.19. 重み付き行列木定理 6. グラフの彩色 6.1. 定義 6.2. 2-彩色 6.3. Brooks の定理 6.4. 適切な彩色に関する練習問題 6.5. 彩色多項式 6.6. Vizing の定理 6.7. その他の練習問題 7. グラフの独立集合 7.1. 定義と Caro-Wei の定理 7.2. 弱いものの単純な下界 7.3. Turán の定理の証明 8. マッチング 8.1. 定義 8.2. 二部グラフ 8.3. Hall の結婚定理 8.4. König の定理と Hall–König の定理 8.5. 個別代表系 8.6. 正則二分グラフ 8.7. ラテン方陣 8.8. 魔法陣と Birkhoff–von Neumann の定理 8.9. Hall の結婚定理に関する練習問題 8.10. マッチングに関する練習問題 9. フロー 9.1. 定義 9.2. 最大フロー問題と二部グラフ 9.3. フローの基礎的な性質 9.4. 最大フロー最小カット定理 9.5. Hall–König のマッチング定理の証明 9.6. 最大フロー最小カット定理の応用 10. さらに路について 10.1. Menger の定理 10.2. Gallai-Milgram の定理 10.3. 路残存集合 10.4. Elser 和 参考文献 索引
更新履歴
2024 年 6 月 23 日 公開