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

Индекс Винера (англ. Wiener index), известный также как число Винера (англ. Wiener number), — топологический индекс неориентированного графа $G=\left \langle A, V \right \rangle$, определяемый как сумма кратчайших путей (англ.) $d(v_i, v_j)$ между вершинами графа:

$w=\sum_{\forall i, j} d(v_i, v_j)$.

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

История

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

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

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

См. также

• Топологический индекс
• Инвариант графа

Примечания

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. ↑ Tratch S. S., Stankevitch M. I., Zefirov N. S.  // J. Comp. Chem. — 1990. — № 11. — С. 899.