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

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

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

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

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

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

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

См. также

Винеровский каркас — средство максимизации эффективности соединений «выделенных вершин» в сети.