Wienerův index

Wienerův index ( angl.  Wiener index ; Wiener number , Wiener number ) je topologický index neorientovaného grafu , definovaný jako součet délek nejkratších cest mezi vrcholy grafu:

.

Lze vypočítat pomocí Floyd-Warshallova algoritmu v čase objednávky .

Navrhl jej Harry Wiener v roce 1947 [ 1] , jde o první známý graf topologický index [2] .  Často se používá v matematické chemii a chemoinformatice při konstrukci kvantitativních korelací „ struktura-vlastnost “ pro grafy organických molekul , uvažovaných bez atomů vodíku .

V roce 1988 Bojan Mohar (Sloven . Bojan Mohar ) a Tomasz Pisanski ( Sloven . Tomaž Pisanski ) navrhli účinný algoritmus pro výpočet Wienerova indexu pro stromy [3] [4] [5] [6] [7] [8] [ 9] .

Známé jsou i různé modifikace indexu, například rozšířený Wienerův index [10] .

Poznámky

  1. ↑ Wiener H. Strukturální stanovení bodů varu parafínu // J. Am. Chem. soc. - 1947. - č. 69 (1) . - S. 17-20 .
  2. ↑ Todeschini R., Consonni V. Handbook of Molecular Descriptors. - Wiley-VCH , 2000. - ISBN 3-52-729913-0 .
  3. ↑ Mohar B., Pisanski T. Jak vypočítat Wienerův index grafu // J. Math. Chemie. - 1988. - č. 2 . - S. 267-277 .
  4. ↑ Dobrynin A. A., Gutman I. Wienerův index pro stromy a grafy hexagonálních systémů  // Diskrétní analýza a operační výzkum. Řada 2. - 1998. - V. 5 , č. 2 . - S. 34-60 . — ISSN 1560-7542 .
  5. ↑ Dobrynin AA, Entringer R., Gutman I. Wienerův index pro stromy: teorie a aplikace  // Acta Appl. Matematika. - 2001. - T. 66 , č. 3 . - S. 211-249 . — ISSN 0167-8019 . Archivováno z originálu 27. července 2021.
  6. ↑ Dobrynin AA, Gutman I., Klavžar S., Žigert P. Wienerův index hexagonálních soustav  // Acta Appl. Matematika. - 2002. - T. 72 , č. 3 . - S. 247-294 . — ISSN 0167-8019 . Archivováno z originálu 28. června 2021.
  7. ↑ Dobrynin AA, Mel'nikov LS Wienerův index spojnicových grafů  // Vzdálenost v molekulárních grafech - Teorie, Editoři I. Gutman, B. Furtula, Monografie matematické chemie 12. - 2012. - S. 85-121 . Archivováno z originálu 31. března 2022.
  8. ↑ Knor M., Škrekovski R. Wiener index čárových grafů  // Kvantitativní teorie grafů: matematické základy a aplikace, Editoři M. Dehmer, F. Emmert-Streib, Diskrétní matematika a její aplikace, Chapman a Hall/CRC. - 2014. - S. 279-301 . Archivováno z originálu 18. října 2019.
  9. ↑ Knor M., Škrekovski R., Tepeh A. Matematické aspekty Wienerova indexu  // Ars Mathematica Contemporanea. - 2016. - T. 11 , č. 2 . — S. 327–352 . — ISSN 1855-3966 . Archivováno z originálu 1. července 2021.
  10. ↑ Tratch SS, Stankevitch MI, Zefirov NS  // J. Comp. Chem. - 1990. - č. 11 . - S. 899 .