グラフ理論の真珠

グラフ理論の真髄: 包括的な入門

著者	ノラ・ハーツフィールドとゲルハルト・リンゲル
主題	グラフ理論
ジャンル	教科書
出版社	学術出版
発行日	1990

Pearls in Graph Theory: A Comprehensive Introductionは、ノラ・ハーツフィールドとゲルハルト・リンゲルによるグラフ理論の学部レベルの教科書です^{。1990年にAcademic Press [1] [2] [3]}から出版され、1994年に改訂版が出版され^[4]、2003年にはDover Booksから改訂版のペーパーバック版が出版されました^{[5] 。}アメリカ数学会の基本図書館リスト委員会は、学部生の数学図書館にこの本を収蔵することを提案しています^{[5] 。}

タイトルの「真珠」には、グラフ理論の定理、証明、問題、例が含まれています。この本は10章から成り、基本的な定義の導入章の後、残りの章ではグラフの色付け、ハミルトンサイクルとオイラーツアー、極値グラフ理論、順列、混沌、ケイリーの公式との関連を含むサブグラフカウント問題、グラフラベル付け、平面グラフ、4色定理、円充填定理、近似平面グラフ、位相面へのグラフ埋め込みについて説明しています。^{[4] [5]}

この本には、完全グラフをサイクルで覆うことに関するオーバーヴォルファッハ問題、マジックグラフの特徴付け、二平面グラフの色付けに関するリンゲルの地球-月問題など、いくつかの未解決問題も含まれています。^[3]

副題が「包括的な入門」であるにもかかわらず、この本は短く、トピックの選択は著者のリンゲルの個人的な興味を反映している。^{[1] [5]}。グラフ理論の重要なトピックのうち、 ^{[1] [4]}で取り上げられていないものには、グラフの対称性、クリーク、グラフと線型代数間の接続（隣接行列を含む）、代数グラフ理論とスペクトルグラフ理論、グラフの接続性（または2連結成分）、ホールの結婚定理、線グラフ、区間グラフ、トーナメント理論などがある。また、アルゴリズムとグラフ理論の実際の応用については1章のみ取り上げられている。^{[1] [4] [5]}また、この本では「難しいまたは長い証明」は省略されている。^{[2] [5]}

この本は学部レベルの教科書として書かれており、この本を使用する学生は離散数学のコースを受講済みであることが推奨されている。とはいえ、高校レベルの数学の知識しかない学生でも読んで理解できる。レビュアーのLW Beinekeは、演習問題のレベルの多様性がこの本の強みの一つであると書いている。^[4]また、レビュアーのJohn S. Maybeeは、演習問題は「広範囲」で、他のトピックとの興味深いつながりを提供していると書いている。^[1]しかし、レビュアーのJ. Sedláčekは演習問題を「決まりきったもの」と批判している。^[2]

何人かの査読者は、本書が重要なトピックを不完全または欠落して扱っていることに不満を述べたが、^{[1] [4] [5]、}査読者のジョアン・ハッチンソンは、トピックの選択を「新鮮に異なっている」と称賛し、グラフ理論に関するこれまでの多くのテキストの中で、位相グラフ理論をこれほど深く扱ったものはなかったと指摘した。^[3]その他の査読者の不満には、出典が間違っていること、^[2]グラフのコンポーネントの定義が間違っており、1つのコンポーネントを持つグラフには適用できなかったこと、^[5] 5色定理の証明がすべての平面グラフではなく特別な平面マップにのみ適用されていることなどがある。^[3]

これらの不満にもかかわらず、Beineke は、学部生向けのテキストとして「この本は多くのことを提供している」と書いています。^[4] Maybee は、この本は「読むのが楽しい」、以前のグラフ理論のテキストよりもいくつかのトピックについてより深くカバーしており、「多くのグラフ理論家」にとって役立つ読み物になるだろうと書いています。^[1] Hutchinson は、この本が「位相グラフ理論への素晴らしい、魅力的な初歩的でありながら包括的な入門書」であると賞賛しています。^[3]

• インターネット アーカイブの「グラフ理論の真珠 (第 1 版)」