細矢インデックス

完全グラフ K₄ には10通りのマッチングがあるので、細矢インデックスは10である。これは4頂点グラフがとるインデックスの最大値である。

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

歴史

このテンプレート:仮リンクは1971年に細矢治夫により導入され、ケモインフォマティクスにおける有機化合物の研究によく用いられる。

細矢は論文 "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, ... （テンプレート:OEIS）

アルゴリズム

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

参考文献

• Roberto Todeschini, Viviana Consonni (2000) "Handbook of Molecular Descriptors", Wiley-VCH, テンプレート:ISBN2