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

Индекс Винера (англ. 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})}$.

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

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

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