Wiener index

Wiener index ( eng.  Wiener index ; Wiener number , Wiener number ) är ett topologiskt index för en oriktad graf , definierad som summan av längderna av de kortaste vägarna mellan grafens hörn:

.

Kan beräknas med Floyd-Warshall-algoritmen i ordningstid .

Föreslog av Harry Wiener 1947 [ 1 ] , det är det första kända graftopologiska indexet [2] .  Används ofta inom matematisk kemi och kemoinformatik när man konstruerar kvantitativa " struktur-egenskaps " -korrelationer för grafer av organiska molekyler , betraktade utan väteatomer .

1988 föreslog Bojan Mohar (Sloven . Bojan Mohar ) och Tomasz Pisanski ( Sloven . Tomaž Pisanski ) en effektiv algoritm för att beräkna Wienerindex för träd [3] [4] [5] [6] [7] [8] [ 9] .

Olika modifieringar av indexet är också kända, till exempel det utökade Wienerindexet [10] .

Anteckningar

  1. ↑ Wiener H. Strukturell bestämning av paraffinkokpunkter // J. Am. Chem. soc. - 1947. - Nr 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. Hur man beräknar Wiener-indexet för en graf // J. Math. Kemi. - 1988. - Nr 2 . - S. 267-277 .
  4. ↑ Dobrynin A. A., Gutman I. Wiener index för träd och grafer av hexagonala system  // Diskret analys och operationsforskning. Serie 2. - 1998. - V. 5 , nr 2 . - S. 34-60 . — ISSN 1560-7542 .
  5. ↑ Dobrynin AA, Entringer R., Gutman I. Wienerindex för träd: teori och tillämpningar  // Acta Appl. Matematik. - 2001. - T. 66 , nr 3 . - S. 211-249 . — ISSN 0167-8019 . Arkiverad från originalet den 27 juli 2021.
  6. ↑ Dobrynin AA, Gutman I., Klavžar S., Žigert P. Wiener index of hexagonal systems  // Acta Appl. Matematik. - 2002. - T. 72 , nr 3 . - S. 247-294 . — ISSN 0167-8019 . Arkiverad från originalet den 28 juni 2021.
  7. ↑ Dobrynin AA, Mel'nikov LS Wiener index of line graphs  // Distance in molecular graphs - Theory, Editors I. Gutman, B. Furtula, Mathematical chemistry monographs 12. - 2012. - S. 85-121 . Arkiverad från originalet den 31 mars 2022.
  8. ↑ Knor M., Škrekovski R. Wiener index över linjediagram  // Kvantitativ grafteori: matematiska grunder och tillämpningar, Redaktörer M. Dehmer, F. Emmert-Streib, Diskret matematik och dess tillämpningar, Chapman och Hall/CRC. - 2014. - S. 279-301 . Arkiverad från originalet den 18 oktober 2019.
  9. ↑ Knor M., Škrekovski R., Tepeh A. Mathematical aspects of Wiener index  // Ars Mathematica Contemporanea. - 2016. - T. 11 , nr 2 . — S. 327–352 . — ISSN 1855-3966 . Arkiverad från originalet den 1 juli 2021.
  10. ↑ Tratch SS, Stankevitch MI, Zefirov NS  // J. Comp. Chem. - 1990. - Nr 11 . - S. 899 .