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

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

${\displaystyle W(G)=\sum _{\forall i,j}d(v_{i},v_{j})}$.

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

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

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

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