グラフの数え上げ―母関数を礎にして― 

書籍情報
ISBN978-4-320-11086-1
判型A5 
ページ数182ページ
発行年月2014年05月
本体価格3,300円
グラフの数え上げ 書影
グラフの数え上げ

 本書は,現在はグラフ理論の一つの分野をなしているグラフの数え上げに焦点を当て,その強力な道具となる母関数も含めて解説した,本邦初の書である。グラフの数え上げに限らず,他の分野の数え上げにも有用な知識を提供する。
 まずはグラフの数え上げに限らず,離散的問題の解法にも強力な道具となる母関数に関して1章を割き,解説する。その後にグラフとは何かを概説し,グラフの数え上げへと話を移していく。各点にラベルを付けた標識グラフ,その構造にのみ注目した非標識グラフ,双方の数え上げを解説し,そのあとでポリアの定理の一般化,最後には自己補グラフの数え上げ,特に1963年以来,未解決であったが,著者自身が解決した問題「標識づけられた自己補グラフを数え上げよ」をとり上げる。
 随所に母関数が使われており,グラフの数え上げだけでなく,母関数に興味のある読者にとっても有用なものとなろう。

目次

第1章 母関数
1.1 母関数とは
1.2 母関数の代数的性質
1.3 漸化式
1.4 組合せ論的等式
1.5 反転公式

第2章 グラフとは
2.1 グラフとは
2.2 標識グラフの描画

第3章 標識グラフの数え上げ
3.1 数え上げの基本的理解
3.2 いろいろな標識グラフ

第4章 非標識グラフの数え上げ
4.1 配置とその同値性
4.2 グラフと群
4.3 Cauchy-Frobenius
4.4 Cauchy-Frobeniusの補題の応用
4.5 重み関数
4.6 巡回指数
4.7 数え上げの基本定理
4.8 グラフの数え上げ
4.9 連結グラフの数え上げ
4.10 互いに同型でない非標識な連結成分を持つ非標識グラフの数え上げ
4.11 2部グラフの数え上げ
4.12 木の数え上げ

第5章 べき群数え上げ定理
5.1 べき群による数え上げ
5.2 べき群による配置数え上げ級数

第6章 自己補グラフ
6.1 自己補グラフと群
6.2 Readによる非標識自己補グラフの数え上げ
6.3 Royle予想
6.4 標識自己補グラフの数え上げ

付録A 補題1.5.5の証明

付録B 位数5の標識グラフとそれの群の位数
B.1 位数5の標識グラフ
B.2 対応する群の位数

付録C 共役類

付録D 巡回指数
D.1 Snの巡回指数
D.2 交代群Anの巡回指数
D.3 巡回群の巡回指数
D.4 二面体群の巡回指数
D.5 対群Pnの巡回指数
D.6 Sm×Snの巡回指数
D.7 S2[Sn]の巡回指数
D.8 (S2[Sn)′の巡回指数
D.9 べき群BAの巡回指数