Hosoyya indeksi

Kaavion (topologinen) Hosoya-indeksi , joka tunnetaan myös nimellä Z-indeksi , on siinä olevien vastaavuuksien kokonaismäärä . Hosoya-indeksi on aina suurempi tai yhtä suuri kuin yksi, koska tyhjät reunat lasketaan osuviksi. Vastaavasti Hosoya-indeksi on ei-tyhjien vastaavuuksien lukumäärä plus yksi.

Historia

Tämän graafiinvariantin esitteli Haro Hosoya vuonna 1971 [1] . Sitä käytetään usein kemoinformatiikassa orgaanisten aineiden tutkimiseen [2] [3] .

Artikkelissa "The Topological Index Z Before and After 1971" käsitteen historiasta ja siihen liittyvistä historiasta Hosoya kirjoittaa, että hän otti käyttöön Z-indeksin osoittamaan suurta korrelaatiota alkaani - isomeerien kiehumispisteen ja niiden Z-indeksien välillä. julkaisemattomassa paperissa vuodelta 1957, kun hän opiskeli Tokion yliopistossa [2] .

Esimerkki

Lineaariset alkaanit Hosoyya-indeksin yhteydessä voidaan esittää ei-haarautuneina poluina . Polulla, jossa on yksi kärki ilman reunoja (vastaa metaanimolekyyliä ), on yksi (tyhjä) vastaavuus, joten sen Hosoyya-indeksi on yksi. Polulla, jossa on yksi reuna ( etan ), on kaksi yhteensopivuutta (toisessa on tyhjä joukko, toisessa yksi reuna), joten sen Hosoyya-indeksi on kaksi. Propaanilla (reitillä, jonka pituus on kaksi) on kolme yhteensopivuutta - mikä tahansa sen reuna sekä tyhjä reunojen joukko. n - Butaanilla (polku, jonka pituus on kolme) on viisi vastaavuutta, mikä erottaa sen isobutaanista , jolla on neljä. Yleensä sovitukset polussa, jossa on k reunaa, joko muodostavat sovituksen alkureunojen kanssa tai muodostavat sovituksen ensimmäisistä reunoista plus reunan, joka yhdistää kaksi viimeistä kärkeä. Siten lineaaristen alkaanien Hosoya-indeksit täyttävät Fibonacci-lukujen toistuvan suhteen . Näiden kaavioiden yhteensopivuusrakenteet voidaan visualisoida Fibonacci-kuution avulla .

Suurin mahdollinen Hosoyya-indeksin arvo graafissa, jossa on n kärkeä, saadaan täydellisillä kaavioilla , ja kokonaisten graafien Hosoyya-indeksit puhelinnumeroita , jotka ovat toinen puhelin (ei neuvottelupuheluita).

Algoritmit

Viittaa vaikeasti laskettaviin topologisiin indekseihin. Hosoya-indeksin laskeminen on #P-täydellinen jopa tasokaavioille [5] . Se voidaan kuitenkin laskea laskemalla vastaava polynomi argumentilla 1 [6] . Tämän Hosoya-indeksin laskennan perusteella ongelma on kiinteäparametrisesti ratkaistavissa rajatun puunleveyden [7] kuvaajille ja polynomi (jossa eksponentti riippuu lineaarisesti leveydestä) graafisille, joilla on rajoitettu klikkin leveys [8] .

Trofimovin artikkeli antaa arvion laskennallisesta monimutkaisuudesta kuten , missä on reunojen lukumäärä [9] .

Muistiinpanot

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

Kirjallisuus

• haruo hosoya. topologinen indeksi. Äskettäin ehdotettu määrä, joka luonnehtii tyydyttyneiden hiilivetyjen rakenteellisten isomeerien topologista luonnetta  // Bulletin of the Chemical Society of Japan. - 1971. - T. 44 , no. 9 . — S. 2332–2339 . - doi : 10.1246/bcsj.44.2332 .
• haruo hosoya. Topologinen indeksi Z ennen ja jälkeen 1971  // Internet Electronic Journal of Molecular Design. - 2002. - Vol. 1 , numero. 9 . — S. 428–442 .
• erikoisnumerot omistettu professori Haruo Hosoyalle 65-vuotissyntymäpäivän kunniaksi  // Internet Electronic Journal of Molecular Design. - 2002/2003. - T. 1#9 - 2#6 . Sarja Haruo Hosoyalle omistettu numerosarja 65-vuotisjuhlan kunniaksi.
• Robert F. Tichy, Stephan Wagner. Äärimmäiset ongelmat topologisille indekseille kombinatorisessa kemiassa  // Journal of Computational Biology . - 2005. - T. 12 , no. 7 . — S. 1004–1013 . - doi : 10.1089/cmb.2005.12.1004 .
• Mark Jerrum. Kaksiulotteiset monomeeri-dimeerijärjestelmät ovat laskennallisesti vaikeita // Journal of Statistical Physics. - 1987. - T. 48 , no. 1 . — S. 121–134 . - doi : 10.1007/BF01010403 .
• Ivan Gutman. Polynomit graafiteoriassa // Chemical Graph Theory: Introduction and Fundamentals / Bonchev D., Rouvray DH. - Taylor & Francis, 1991. - T. 1. - S. 133-176. — (Matemaattinen kemia). - ISBN 978-0-85626-454-2 .
• Courcelle B., Makowsky JA, Rotics U. Monadisessa toisen asteen logiikassa määritettävissä olevien graafien luettelointiongelmien kiinteän parametrin monimutkaisuudesta  // Discrete Applied Mathematics. - 2001. - T. 108 , no. 1-2 . - S. 23-52 . - doi : 10.1016/S0166-218X(00)00221-3 .
• Makowsky JA, Udi Rotics, Ilya Averbouch, Benny Godlin. Graafipolynomien laskeminen rajatun klikkinleveyden kuvaajilla // Proc. 32. kansainvälinen työpaja tietojenkäsittelytieteen graafiteoreettisista käsitteistä (WG '06) . - Springer-Verlag, 2006. - T. 4271. - S. 191-204. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - ISBN 978-3-540-48381-6 . - doi : 10.1007/11917496_18 .
• Roberto Todeschini, Viviana Consonni. Molecular Descriptors -käsikirja. - Wiley-VCH , 2000. - ISBN 3-527-29913-0 .
• Trofimov MI Hosoyan indeksin laskentamenettelyn optimointi // J. Math. Chem.. - 1991. - Numero. 9 .