細矢インデックスのソースを表示

[[File:K4 matchings.svg|thumb|[[完全グラフ]] ''K''<sub>4</sub> には10通りのマッチングがあるので、細矢インデックスは10である。これは4[[グラフ理論|頂点]]グラフがとるインデックスの最大値である。]]
[[グラフ理論]]における'''細矢インデックス'''または'''Zインデックス'''とは、与えられた[[グラフ理論|グラフ]]の[[マッチング (グラフ理論)|マッチング]]の総数のことである。このとき[[グラフ理論|辺]]の[[空集合]]もマッチングの一つとして数えるので、細矢インデックスは必ず1以上である。同じことだが、「グラフの空でないマッチングの個数に1を足した値」と定義してもよい。

==歴史==
この{{仮リンク|グラフ不変量|en|graph invariant}}は1971年に[[細矢治夫]]により導入され<ref>{{citation
 | last=Hosoya | first=Haruo
 | title=Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons
 | journal=Bulletin of the Chemical Society of Japan
 | volume=44
 | issue=9
 | year=1971
 | pages=2332–2339
 | doi=10.1246/bcsj.44.2332
}}.</ref>、[[ケモインフォマティクス]]における[[有機化合物]]の研究によく用いられる<ref name=before>{{citation
 | last=Hosoya | first=Haruo
 | title=The topological index ''Z'' before and after 1971
 | journal=Internet Electronic Journal of Molecular Design
 | year=2002
 | volume=1
 | issue=9
 | pages=428–442
 | url=http://www.biochempress.com/av01_0428.html
}}.</ref><ref>[http://www.biochempress.com/iejmd_ji.html 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.</ref>。

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

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

より一般に、 ''k'' 本の辺から成る道（直鎖構造）のマッチングは、最初の ''k''&nbsp;&minus;&nbsp;1 本の辺のマッチングか、もしくは最初の ''k''&nbsp;&minus;&nbsp;2 本の辺のマッチングに最後の辺を[[和集合|合併]]したもののいずれかだから、直鎖アルカンに対する細矢インデックスは[[フィボナッチ数]]を生む[[漸化式]]に従う。これらのグラフでのマッチングの構造は{{仮リンク|フィボナッチキューブ|en|Fibonacci cube}}を用いて視覚化することができる。

頂点が ''n'' 個のグラフの細矢インデックスが最大になるのは、完全グラフの場合である。これらの完全グラフに対する細矢インデックスは{{仮リンク|telephone number|en|Telephone number (mathematics)}}になる。
:1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... （{{OEIS|A000085}}<ref>{{citation
 | last1 = Tichy | first1 = Robert F.
 | last2 = Wagner | first2 = Stephan
 | doi = 10.1089/cmb.2005.12.1004
 | issue = 7
 | journal = [[Journal of Computational Biology]]
 | pages = 1004–1013
 | title = Extremal problems for topological indices in combinatorial chemistry
 | url = http://www.math.tugraz.at/fosp/pdfs/tugraz_main_0052.pdf
 | volume = 12
 | year = 2005}}.</ref>）

==アルゴリズム==
細矢インデックスの[[複雑性クラス|計算複雑性]]は、グラフを[[平面グラフ]]に限ったとしても{{仮リンク|Sharp-P完全|en|Sharp-P-complete}}である<ref>{{citation
 | last = Jerrum | first = Mark | authorlink = Mark Jerrum
 | doi = 10.1007/BF01010403
 | issue = 1
 | journal = Journal of Statistical Physics
 | pages = 121–134
 | title = Two-dimensional monomer-dimer systems are computationally intractable
 | volume = 48
 | year = 1987}}.</ref>。しかし、{{仮リンク|マッチング多項式|en|matching polynomial}}で[[引数]]を1としたときの値 ''m<sub>G</sub>'' として計算できる<ref>{{citation
 | last = Gutman | first = Ivan
 | editor1-last = Bonchev | editor1-first = D.
 | editor2-last = Rouvray | editor2-first = D. H.
 | contribution = Polynomials in graph theory
 | isbn = 978-0-85626-454-2
 | pages = 133–176
 | publisher = Taylor & Francis
 | series = Mathematical Chemistry
 | title = Chemical Graph Theory: Introduction and Fundamentals
 | volume = 1
 | year = 1991}}.</ref>ことに基づけば、細矢インデックスの計算は{{仮リンク|木幅|en|Treewidth}}（treewidth）の上限をパラメータとする{{仮リンク|固定パラメータ容易性|en|fixed-parameter tractability}}（fixed-parameter tractability,FPT）を持つ<ref>{{citation
 | last1 = Courcelle | first1 = B. | author1-link = Bruno Courcelle
 | last2 = Makowsky | first2 = J. A.
 | last3 = Rotics | first3 = U.
 | doi = 10.1016/S0166-218X(00)00221-3
 | issue = 1–2
 | journal = Discrete Applied Mathematics
 | pages = 23–52
 | title = On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
 | url = http://www.labri.fr/perso/courcell/CoursMaster/CMR-Dam.pdf
 | volume = 108
 | year = 2001}}.</ref>。さらに、{{仮リンク|クリーク幅|en|clique-width}}（clique-width）の上限を ''k'' とするとき次数が ''k'' に線形的に依存するような[[多項式時間]]で計算できる（つまりグラフの頂点数 ''n'' に対し計算量が <math>O({n^{f(k)}})</math> で済む）<ref>{{citation
 | last1 = Makowsky | first1 = J. A.
 | last2 = Rotics | first2 = Udi
 | last3 = Averbouch | first3 = Ilya
 | last4 = Godlin | first4 = Benny
 | contribution = Computing graph polynomials on graphs of bounded clique-width
 | doi = 10.1007/11917496_18
 | pages = 191–204
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '06)
 | url = http://www.cs.technion.ac.il/~admlogic/TR/2006/WG06_makowsky.pdf
 | volume = 4271
 | year = 2006
 | isbn = 978-3-540-48381-6}}.</ref>。

==脚注==
{{reflist}}

==参考文献==
*Roberto Todeschini, Viviana Consonni (2000) "Handbook of Molecular Descriptors", ''[[Wiley-VCH]]'', {{ISBN2|3-527-29913-0}}

{{DEFAULTSORT:ほそやいんてつくす}}
[[Category:理論化学]]
[[Category:グラフ理論]]
[[Category:グラフ不変量]]
[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]