細矢インデックス

グラフ理論における細矢インデックスまたはZインデックスとは、与えられたグラフのマッチングの総数のことである。このとき辺の空集合もマッチングの一つとして数えるので、細矢インデックスは必ず1以上である。同じことだが、「グラフの空でないマッチングの個数に1を足した値」と定義してもよい。

歴史
このは1971年に細矢治夫により導入され.、ケモインフォマティクスにおける有機化合物の研究によく用いられる.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.。

細矢は論文 "The Topological Index Z Before and After 1971" の、概念の歴史と内幕に触れた箇所で、アルカン異性体の沸点とZインデックスの間にある良い相関性を報告するため、東京大学の学部生であった頃の未発表の研究（1957年）に基づいてこの指標を導入したと書いている。

例
直鎖アルカンは、細矢インデックスを求める上では枝分かれのない道 (グラフ理論)と見なして差し支えない。頂点1個、辺0本の道（メタン分子に対応）にはマッチングが1つ（空集合）存在するので、細矢インデックスは1である。2個の頂点を結ぶ1本の辺から成る道（エタン分子に対応）にはマッチングが2つ（空集合、1本の辺から成る集合）存在するので、細矢インデックスは2である。プロパン（長さ2の道）には3つのマッチング（空集合、2本の辺のいずれかから成る集合）がある。  n-ブタン（長さ3の道）には5つのマッチングがあり、マッチングの数が4であるイソブタンと識別される。

より一般に、 k 本の辺から成る道（直鎖構造）のマッチングは、最初の k − 1 本の辺のマッチングか、もしくは最初の k − 2 本の辺のマッチングに最後の辺を合併したもののいずれかだから、直鎖アルカンに対する細矢インデックスはフィボナッチ数を生む漸化式に従う。これらのグラフでのマッチングの構造はを用いて視覚化することができる。

頂点が n 個のグラフの細矢インデックスが最大になるのは、完全グラフの場合である。これらの完全グラフに対する細矢インデックスはになる。
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... （.）

アルゴリズム
細矢インデックスの計算複雑性は、グラフを平面グラフに限ったとしてもである.。しかし、で引数を1としたときの値 mG として計算できる.ことに基づけば、細矢インデックスの計算は（treewidth）の上限をパラメータとする（fixed-parameter tractability,FPT）を持つ.。さらに、（clique-width）の上限を k とするとき次数が k に線形的に依存するような多項式時間で計算できる（つまりグラフの頂点数 n に対し計算量が  で済む）.。

脚注

参考文献
Roberto Todeschini, Viviana Consonni (2000) "Handbook of Molecular Descriptors", Wiley-VCH, 

Category:理論化学
Category:グラフ理論
Category:グラフ不変量
Category:計算複雑性理論
Category:数学に関する記事
Category:数学のエポニム