平博順・地嵜頌子・一森哲男 : グラフ理論 改訂版

概要

「はしがき」から引用する。

本書はコンピュータサイエンスやさまざまなシステムを学ぶ人々に必須の内容をわかりやすく解説している．

本書は（明示されていはいないが）一森哲男「グラフ理論」をもとにした改訂版と思われる。

全域木の総数

3.3 節では、完全グラフ `K_n` に含まれる全域木の総数が `n^(n-2)` であることの証明がなされている。 この証明では、各全域木を 1 つの頂点列で表現できること、 その頂点列の個数から全域木の総数がわかることを導いている。 この頂点列は「プリューファー列」とか「プリューファーコード」と呼ばれているが、 この呼び名の紹介は本書にはない。

さて、p.45 の練習問題 3.6 にはこんな問題がある。

無向完全グラフ `K_5` の異なる全域木 125 個をすべて図に示せ．

p.167 の練習問題の略解を見ると、無向完全グラフ `K_5` の異なる全域木 125 個の一部を図に示す． という説明とともに、そのうちの 20 個の全域木が載っていた。読者にすべてといっておきながら紙面では一部に止めるのはずるい、 と思った。しかし、全部が載っていたら「図ばかりで紙面を稼ぐなよ」と悪態をつくかもしれない。 これは略解なのだから、一部でもよしとすべきだろう。

なお、コンピュータで書こうとして書けなかった苦闘のあとを、全域木とプリューファー列というページに残した。

平面的グラフ

「第７章 グラフの平面性」を読んでいて、次の個所があった。pp.100-101 である。

一般に，辺を表す線分（曲線）を交差させずに平面上に描くことのできるグラフを平面的グラフ（planar graph）という．

上記で示したように，完全グラフ `K_5` は平面的グラフではない．平面的グラフではないものとして，完全２部グラフ `K_(3,3)` も有名である．

完全２部グラフが平面的グラフでないことを使ったパズルがある。A,B,C３軒の家に、電気、ガス、水道を平面的に供給するとき、必ず線が交差する、ということだったと思う。

用語

p.49 では有名なグラフの一例としてピーターセングラフが取り上げられていて、 p.111 の練習問題や p.139 の練習問題でも出てきている。以前の版は p.49 に相当する箇所だけペテルセングラフだったので、今回の改訂版で誤植が直ったといえる。

書誌情報