1.1. 本書について

本書はグラフ理論 (graph theory) に関する講義ノートである ── グラフは非常に基礎的な数学的概念 (実際には密接に関連するいくつかの概念の集合体) であり、数学の様々な分野で姿を現す。本書では様々な種類のグラフ (単純グラフ、多重グラフ、有向グラフなど) の特徴・性質を学ぶ。具体的には、グラフの路・歩道、グラフのマッチング、ネットワーク (追加情報を持ったグラフ) のフローといった概念や、木・トーナメントといった特別な種類のグラフの話題に触れる。

グラフ理論の研究は少なくとも Leonhard Euler まで遡ることができる。Euler は 1736 年に発表した論文 [Euler36] (英訳は [EulerEn53]) でケーニヒスベルクの町を巡る最適な順路に関するパズルを解決した。その後グラフ理論は 19 世紀にさらに発展し、20 世紀には爆発的に研究が進んだ。現在グラフ理論は数学で最も盛んに研究が行われている分野の一つである。数百冊とは言わないまでも、数十冊のグラフ理論に関する教科書が出版されている。その一部を次に示す:

• 専門的: [BonMur08], [Berge91], [Ore74], [Bollob98],[Dieste17], [ChLeZh16], [Jungni13]

• 入門的: [Harju14], [Ruohon13], [LeLeMe18, Chapters 10–13], [Wilson10], [Bollob71], [Galvin21], [Tait21], [Guicha16, Chapter 5], [Harary69], [Ore96], [BenWil06, Chapters 5–6], [HarRin03], [KelTro17], [LoPeVe03], [West01], [Verstr21], [HaHiMo08, Chapter 1], [Griffi21]

これらの教科書が扱う内容のレベルはそれぞれ異なり、議論の厳密さ、詳細さ、想定する読者も異なる。また、扱う話題も (最も基礎的な話題を除けば) 同じでない場合が多い。例えば [Dieste17] は無限グラフとランダムグラフを扱うのに対して、[Griffi21] はグラフの応用に多く紙面を割いている。

本書は自己充足的であり、他の教科書を参照しない。ただし、グラフ理論に関する広い視点 (この入門講義がカバーするより格段に広い視点) を得るために、上に示した他の教科書に軽く目を通して、そのいずれかを本書の次に読むことを読者には勧める。本書が焦点を当てるのはグラフ理論の離散的な側面と代数的な側面 (様々な種類の有限グラフ、存在に関する結果、数え上げの公式) に関する話題であり、それも時間的な制約 (本書はクオーター講義のために書かれた) と著者自身が持つ知識の制約によって制限される。

1.1.1本書に関する情報

前提知識: この講義ノートは大学院生 (または意欲ある学部生) を対象読者とする。数学に対する一定程度の慣れと、自分で考えながら (そして自分で例を作りながら) 文章を読む意思が求められる。この二点の他には、行列式、多項式、有限和に関する基本的な性質などが前提知識として仮定される。本書は体と環にも言及するものの、最も基本的な例 (\(\mathbb{Q}\), \(\mathbb{R}\), 多項式環と行列環) だけを分かっていれば十分だろう。いくつかの箇所では有限体 \(\mathbb{F}_{2}\) も登場する。本書で解析学の知識が必要になることはない (微積分の知識さえ必要にならない)。

講義のウェブサイト: この講義ノートはドレクセル大学で 2022 年春学期に開講された Math 530 講義のために書かれた。この講義のウェブサイトは次の URL から閲覧できる:

同様の講義はミネソタ大学で 2017 年春学期にも開講されている。この講義のウェブサイトは次の URL から閲覧できる:

後者のウェブサイトには一部の練習問題に対する解答や高度な話題に関する解説などの追加資料、および本書の第 1 章の内容がより詳しく解説される短い文書がアップロードされている。もし本書を arXiv からダウンロードして読んでいるなら、これらの追加資料は arXiv に提出された補助ファイルから確認できる。

練習問題: 本書には練習問題が含まれる。その難易度や重要性は問題ごとに異なる。ほぼ全ての練習問題は飛ばすことができる (以降の練習問題を除けば本文中からは参照されない) ものの、練習問題に取り組めば理解を確認でき、新しく学んだ事項が利用される場面や新たな発想を学習できる。ただ当然ながら、同じ問題でも刺激的と感じる人もいれば退屈だと感じる人もいるので、特定の練習問題にあまりにも長い時間をかけることは推奨しない。一つの問題を何時間も考えるよりは、本文を読み進める方がいいだろう。しかし、問題につき十数分ほど考えることは時間の無駄にならない可能性が高い。

謝辞: 著者は Joel Brewster Lewis, Lukas Katthän, Victor Reiner との会話から多くのことを学んだ。Chiara Libera Carnevale と Amanda Johnson は本書の以前のバージョンの誤りを指摘した。ここに挙げた全ての人物に感謝している。これからも本書に対するコメントは歓迎する ── 訂正すべき箇所の指摘や提案があれば、どんなに小さなものでも darijgrinberg@gmail.com から知らせてほしい。