一森 哲男 : グラフ理論

作成日 : 2022-02-14
最終更新日 :

概要

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

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

全域木の総数

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

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

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

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

全域木とプリューファー列

誤植

p.143 の参考文献のページで [1] の著者が伊里正夫になっている。正しくは《伊理正夫》である。

p.43 では有名なグラフの一例としてペーターセングラフを取り上げているが、 p.98 の練習問題や p.124 の練習問題、およびこれらの解答(p.140 と p.142) ではピーターセングラフになっている。どちらかに統一すべきだろう。 Wikipedia では「ピーターセングラフ」または「ペテルセングラフ」となっている。

書誌情報

書名グラフ理論
著者一森 哲男
発行日2002 年 10 月 1 日(初版 1 刷)
発行元共立出版
定価 2200 円(本体)
サイズ A5 版 156 ページ
ISBN4-320-01708-0
NDC

まりんきょ学問所数学の部屋数学の本 > 一森 哲男 : グラフ理論


MARUYAMA Satosi