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

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

Предложен

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

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

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