内容説明
グラフ理論の1つの分野を成す、「グラフの数え上げ」の本。グラフの数え上げについて、その強力な道具となる母関数も含めて解説。グラフに限らず他の分野の数え上げにも有用な知識を提供する。
目次
表紙
まえがき
目 次
第1章 母関数
1.1 母関数とは?
1.2 母関数の代数的性質
1.3 漸化式
1.4 組合せ論的等式
1.5 反転公式
第2章 グラフとは
2.1 グラフとは
2.2 標識グラフの描画
第3章 標識グラフの数え上げ
3.1 数え上げの基本的理解
3.2 いろいろな標識グラフ
3.2.1 連結グラフ
3.2.2 奇点個数による数え上げ
3.2.3 標識木
3.2.4 標識ブロック
第4章 非標識グラフの数え上げ
4.1 配置とその同値性
4.2 グラフと群
4.3 Cauchy-Frobenius
4.3.1 Cauchy-Frobenius の補題
4.4 Cauchy-Frobenius の補題の応用
4.4.1 RD への応用
4.4.2 非標識グラフへの応用
4.5 重み関数
4.6 巡回指数
4.7 数え上げの基本定理
4.7.1 Po lya の定理
4.7.1.1 1 変数の場合
4.7.1.2 2 変数の場合
4.7.2 1 : 1 写像
4.8 グラフの数え上げ
4.9 連結グラフの数え上げ
4.9.1 位数をパラメータとした場合
4.9.2 位数および大きさをパラメータにした場合
4.10 互いに同型でない非標識な連結成分を持つ非標識グラフの数え上げ
4.11 2 部グラフの数え上げ
4.12 木の数え上げ
4.12.1 根つき木の数え上げ
4.12.2 非標識木の数え上げ
第5章 べき群数え上げ定理
5.1 べき群による数え上げ
5.2 べき群による配置数え上げ級数
第6章 自己補グラフ
6.1 自己補グラフと群
6.2 Read による非標識自己補グラフの数え上げ
6.3 Royle 予想
6.4 標識自己補グラフの数え上げ
6.4.1 自己補グラフを数える
付録A 補題1.5.5の証明
付録B 位数5の標識グラフとそれの群の位数
B.1 位数5 の標識グラフ
B.2 対応する群の位数
付録C 共役類
付録D 巡回指数
D.1 Sの巡回指数
D.2 交代群An の巡回指数
D.3 巡回群の巡回指数
D.4 二面体群の巡回指数
D.5 対群Pn の巡回指数
D.6 Sm × Sn の巡回指数
D.6.1 m ≠ n の場合
D.6.2 m = n の場合
D.7 S2[Sn] の巡回指数
D.8 (S2[Sn)′ の巡回指数
D.9 べき群BA の巡回指数
D.9.1 A = Sn,B = S2 の場合
D.9.2 A = 巡回群Cn,B = S2 の場合
D.9.3 A = 二面体群Dn,B = S2 の場合
D.9.4 A = 対群Pn,B = S2 の場合
参考文献
索 引