Индекс Винера

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Индекс Винера (англ. Wiener index), известный также как число Винера (англ. Wiener number), — топологический индекс неориентированного графа , определяемый как сумма длин кратчайших путей (англ.) между вершинами графа:

.

Индекс может быть вычислен с использованием алгоритма Флойда — Уоршелла за время порядка .

История[править | править вики-текст]

Был предложен Х. Винером в 1947 году [1] и является наиболее старым из известных топологических индексов [2]. Часто используется в математической химии и хемоинформатике при построении количественных корреляций «структура-свойство» для графов органических молекул, рассматриваемых без атомов водорода.

В 1988 году Б. Мохаром (англ. Bojan Mohar) и Т. Писански (англ.) (англ. Tomaž Pisanski) был предложен эффективный алгоритм вычисления индекса Винера для деревьев [3]. Обсуждение математических свойств индекса Винера можно найти в ряде обзоров [4][5][6][7][8][9].

Известны также различные модификации индекса Винера (например, расширенный индекс Винера [10]).


См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Wiener H. Structural determination of paraffin boiling points // J. Am. Chem. Soc. — 1947. — № 69 (1). — С. 17-20.
  2. Todeschini R., Consonni V. Handbook of Molecular Descriptors. — Wiley-VCH (англ.), 2000. — ISBN 3-52-729913-0.
  3. Mohar B., Pisanski T. How to compute the Wiener index of a graph // J. Math. Chemistry. — 1988. — № 2. — С. 267-277.
  4. Добрынин А. А., Гутман И. Индекс Винера для деревьев и графов гексагональных систем // Дискретный анализ и исследование операций. Серия 2. — 1998. — Т. 5, № 2. — С. 34-60. — ISSN 1560-7542.
  5. Dobrynin A. A., Entringer R., Gutman I. Wiener index for trees: theory and applications // Acta Appl. Math. — 2001. — Т. 66, № 3. — С. 211-249. — ISSN 0167-8019.
  6. Dobrynin A. A., Gutman I., Klavžar S., Žigert P. Wiener index of hexagonal systems // Acta Appl. Math. — 2002. — Т. 72, № 3. — С. 247-294. — ISSN 0167-8019.
  7. Dobrynin A. A., Mel'nikov L. S. Wiener index of line graphs // Distance in molecular graphs - Theory, Editors I. Gutman, B. Furtula, Mathematical chemistry monographs 12. — 2012. — С. 85-121.
  8. Knor M., Škrekovski R. Wiener index of line graphs // Quantitative graph theory: mathematical foundations and applications, Editors M. Dehmer, F. Emmert-Streib, Discrete Mathematics and Its Applications, Chapman and Hall/CRC. — 2014. — С. 279-301.
  9. Knor M., Škrekovski R., Tepeh A. Mathematical aspects of Wiener index // Ars Mathematica Contemporanea. — 2016. — Т. 11, № 2. — С. 327–352. — ISSN 1855-3966.
  10. Tratch S. S., Stankevitch M. I., Zefirov N. S.  // J. Comp. Chem. — 1990. — № 11. — С. 899.