細矢インデックス

グラフ理論における細矢インデックスまたは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としたときの値 m_G として計算できる^[6]ことに基づけば、細矢インデックスの計算は木幅（英語版）（treewidth）の上限をパラメータとする固定パラメータ容易性（英語版）（fixed-parameter tractability,FPT）を持つ^[7]。さらに、クリーク幅（英語版）（clique-width）の上限を k とするとき次数が k に線形的に依存するような多項式時間で計算できる（つまりグラフの頂点数 n に対し計算量が ${\displaystyle O({n^{f(k)}})}$ で済む）^[8]。

• Roberto Todeschini, Viviana Consonni (2000) "Handbook of Molecular Descriptors", Wiley-VCH, ISBN 3-527-29913-0