細矢インデックス
グラフ理論における細矢インデックスまたはZインデックスとは、与えられたグラフのマッチングの総数のことである。このとき辺の空集合もマッチングの一つとして数えるので、細矢インデックスは必ず1以上である。同じことだが、「グラフの空でないマッチングの個数に1を足した値」と定義してもよい。
歴史
[編集]このグラフ不変量は1971年に細矢治夫により導入され[1]、ケモインフォマティクスにおける有機化合物の研究によく用いられる[2][3]。
細矢は論文 "The Topological Index Z Before and After 1971" の、概念の歴史と内幕に触れた箇所で、アルカン異性体の沸点とZインデックスの間にある良い相関性を報告するため、東京大学の学部生であった頃の未発表の研究（1957年）に基づいてこの指標を導入したと書いている[2]。
例
[編集]直鎖アルカンは、細矢インデックスを求める上では枝分かれのない道 (グラフ理論)と見なして差し支えない。頂点1個、辺0本の道（メタン分子に対応）にはマッチングが1つ（空集合）存在するので、細矢インデックスは1である。2個の頂点を結ぶ1本の辺から成る道（エタン分子に対応）にはマッチングが2つ（空集合、1本の辺から成る集合）存在するので、細矢インデックスは2である。プロパン（長さ2の道）には3つのマッチング（空集合、2本の辺のいずれかから成る集合）がある。 n-ブタン（長さ3の道）には5つのマッチングがあり、マッチングの数が4であるイソブタンと識別される。
より一般に、 k 本の辺から成る道（直鎖構造）のマッチングは、最初の k − 1 本の辺のマッチングか、もしくは最初の k − 2 本の辺のマッチングに最後の辺を合併したもののいずれかだから、直鎖アルカンに対する細矢インデックスはフィボナッチ数を生む漸化式に従う。これらのグラフでのマッチングの構造はフィボナッチキューブを用いて視覚化することができる。
頂点が n 個のグラフの細矢インデックスが最大になるのは、完全グラフの場合である。これらの完全グラフに対する細矢インデックスはtelephone numberになる。
- 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... （オンライン整数列大辞典の数列 A000085[4]）
アルゴリズム
[編集]細矢インデックスの計算複雑性は、グラフを平面グラフに限ったとしてもSharp-P完全である[5]。しかし、マッチング多項式で引数を1としたときの値 mG として計算できる[6]ことに基づけば、細矢インデックスの計算は木幅（treewidth）の上限をパラメータとする固定パラメータ容易性（fixed-parameter tractability,FPT）を持つ[7]。さらに、クリーク幅（clique-width）の上限を k とするとき次数が k に線形的に依存するような多項式時間で計算できる（つまりグラフの頂点数 n に対し計算量が で済む）[8]。
脚注
[編集]- ^ Hosoya, Haruo (1971), “Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons”, Bulletin of the Chemical Society of Japan 44 (9): 2332–2339, doi:10.1246/bcsj.44.2332.
- ^ a b Hosoya, Haruo (2002), “The topological index Z before and after 1971”, Internet Electronic Journal of Molecular Design 1 (9): 428–442.
- ^ Internet Electronic Journal of Molecular Design, special issues dedicated to Professor Haruo Hosoya on the occasion of the 65th birthday: Volume 1 (2002), Number 9 — Volume 2 (2003), Number 6.
- ^ Tichy, Robert F.; Wagner, Stephan (2005), “Extremal problems for topological indices in combinatorial chemistry”, Journal of Computational Biology 12 (7): 1004–1013, doi:10.1089/cmb.2005.12.1004.
- ^ Jerrum, Mark (1987), “Two-dimensional monomer-dimer systems are computationally intractable”, Journal of Statistical Physics 48 (1): 121–134, doi:10.1007/BF01010403.
- ^ Gutman, Ivan (1991), “Polynomials in graph theory”, in Bonchev, D.; Rouvray, D. H., Chemical Graph Theory: Introduction and Fundamentals, Mathematical Chemistry, 1, Taylor & Francis, pp. 133–176, ISBN 978-0-85626-454-2.
- ^ Courcelle, B.; Makowsky, J. A.; Rotics, U. (2001), “On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic”, Discrete Applied Mathematics 108 (1–2): 23–52, doi:10.1016/S0166-218X(00)00221-3.
- ^ Makowsky, J. A.; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006), “Computing graph polynomials on graphs of bounded clique-width”, Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '06), Lecture Notes in Computer Science, 4271, Springer-Verlag, pp. 191–204, doi:10.1007/11917496_18, ISBN 978-3-540-48381-6.
参考文献
[編集]- Roberto Todeschini, Viviana Consonni (2000) "Handbook of Molecular Descriptors", Wiley-VCH, ISBN 3-527-29913-0