Hosoyya index

A (topológiai) Hosoya-index , más néven Z-index , a gráfon található egyezések teljes száma . A Hosoya index mindig nagyobb vagy egyenlő, mint egy, mivel az üres élhalmaz egyezésnek számít. Ezzel egyenértékűen a Hosoya index a nem üres egyezések száma plusz egy.

Történelem

Ezt a gráfinvariánst Haro Hosoya vezette be 1971-ben [1] . A kemoinformatikában gyakran használják szerves anyagok tanulmányozására [2] [3] .

A fogalom történetéről és a kapcsolódó történetekről szóló "The Topological Index Z Before and After 1971" című cikkében Hosoya azt írja, hogy bevezette a Z indexet, hogy jelezze az alkánizomerek forráspontja és a Z- indexeik közötti magas korrelációt. egy kiadatlan dolgozaton 1957-ből, amikor a Tokiói Egyetem egyetemi hallgatója volt [2] .

Példa

A lineáris alkánok a Hosoyya index összefüggésében nem elágazó útvonalakként ábrázolhatók . Egy élek nélküli csúcsot tartalmazó útvonalnak (amely metánmolekulának felel meg ) van egy (üres) egyezése, tehát a Hosoyya indexe egy. Egy élű útvonalnak ( etan ) két egyezése van (az egyik üres élkészlettel, a másik egy éllel), így a Hosoyya indexe kettő. A propánnak (kettes hosszúságú út) három illesztése van – bármelyik éle, plusz egy üres élkészlet. n - A bután (három hosszúságú út) öt egyezést tartalmaz, ami megkülönbözteti az izobutántól , amelynek négy. Általánosságban elmondható, hogy a k élű útvonal illesztései vagy a kezdeti élekkel illeszkednek, vagy pedig az első élekből és az utolsó két csúcsot összekötő élből alkotnak egyezést. Így a lineáris alkánok Hosoya indexei kielégítik a Fibonacci-számok ismétlődő összefüggését . Ezekben a grafikonokban az illeszkedő struktúrák a Fibonacci-kocka segítségével jeleníthetők meg .

A Hosoyya index lehetséges legnagyobb értékét egy n csúcsú gráfon komplett gráfok adják , a teljes gráfok Hosoyya indexei pedig másik telefonszám telefonszámai (konferenciahívás nélkül).

Algoritmusok

Nehezen kiszámítható topológiai indexekre utal. A Hosoya-index kiszámítása #P-teljes még síkgráfok esetében is [5] . Ez azonban kiszámítható az 1-es argumentumú illeszkedő polinom kiszámításával [6] . A Hosoya-index ezen számítása alapján a probléma megoldható fix-paraméteres korlátos faszélességű gráfok esetén [7] és polinomiális (a szélességtől lineárisan függő kitevővel) korlátos klikkszélességű gráfok esetén [ 8] .

Trofimov cikke a számítási bonyolultság becslését adja meg , ahol az élek száma [9] .

Jegyzetek

1. ↑ Hosoya, 1971 , p. 2332–2339.
2. ↑ 1 2 Hosoya, 2002 , p. 428–442.
3. ↑ Haruo Hosoya 65 éve, 2002/2003 .
4. ↑ Tichy, Wagner, 2005 , p. 1004–1013.
5. ↑ Jerrum, 1987 , p. 121–134.
6. ↑ Gutman, 1991 , p. 133–176.
7. ↑ Courcelle, Makowsky, Rotics, 2001 , p. 23–52.
8. ↑ Makowsky, Rotics, Averbouch, Godlin, 2006 , p. 191–204.
9. ↑ Trofimov, 1991 , p. 327.

Irodalom

• haruo hosoya. topológiai index. Egy újonnan javasolt mennyiség, amely a telített szénhidrogének szerkezeti izomereinek topológiai természetét jellemzi  // Bulletin of the Chemical Society of Japan. - 1971. - T. 44 , sz. 9 . – S. 2332–2339 . - doi : 10.1246/bcsj.44.2332 .
• haruo hosoya. A Z topológiai index 1971 előtt és után  // Internet Electronic Journal of Molecular Design. - 2002. - 1. évf. , szám. 9 . – S. 428–442 .
• különszámok Haruo Hosoya professzornak a 65. születésnap alkalmából  // Internet Electronic Journal of Molecular Design. - 2002/2003. - T. 1#9 - 2#6 . Haruo Hosoyának szentelt számsorozat a 65. évforduló alkalmából.
• Robert F. Tichy, Stephan Wagner. Extrém problémák topológiai indexekkel a kombinatorikus kémiában  // Journal of Computational Biology . - 2005. - T. 12 , sz. 7 . – S. 1004–1013 . - doi : 10.1089/cmb.2005.12.1004 .
• Mark Jerrum. A kétdimenziós monomer-dimer rendszerek számításilag nehezen kezelhetők // Journal of Statistical Physics. - 1987. - T. 48 , sz. 1 . – S. 121–134 . - doi : 10.1007/BF01010403 .
• Gutman Iván. Polinomok a gráfelméletben // Chemical Graph Theory: Introduction and Fundamentals / Bonchev D., Rouvray DH. - Taylor & Francis, 1991. - T. 1. - S. 133-176. — (Matematikai kémia). - ISBN 978-0-85626-454-2 .
• Courcelle B., Makowsky JA, Rotics U. A monadikus másodrendű logikában definiálható gráffelszámítási problémák fixparaméteres összetettségéről  // Discrete Applied Mathematics. - 2001. - T. 108 , sz. 1–2 . – S. 23–52 . - doi : 10.1016/S0166-218X(00)00221-3 .
• Makowsky JA, Udi Rotics, Ilya Averbouch, Benny Godlin. Gráfpolinomok számítása korlátos klikkszélességű gráfokon // Proc. 32. nemzetközi műhely a gráfelméleti fogalmakról a számítástechnikában (WG '06) . - Springer-Verlag, 2006. - T. 4271. - S. 191-204. — (Számítástechnikai előadásjegyzetek). - ISBN 978-3-540-48381-6 . - doi : 10.1007/11917496_18 .
• Roberto Todeschini, Viviana Consonni. A molekuláris leírók kézikönyve. - Wiley-VCH , 2000. - ISBN 3-527-29913-0 .
• Trofimov MI A Hosoya-index számítási eljárásának optimalizálása // J. Math. Chem.. - 1991. - Issue. 9 .