Индекс Винера ( англ. 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 году , является первым из известных графовых топологических индексов . Часто используется в математической химии и хемоинформатике при построении количественных корреляций « структура-свойство » для графов органических молекул , рассматриваемых без атомов водорода .

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

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

Примечания

См. также

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