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

Индекс Винера (Шаблон:Lang-en; число Винера, Шаблон:Lang-en2) — топологический индекс неориентированного графа $G=⟨A,V⟩$, определяемый как сумма длин кратчайших путей $d(v_i,v_j)$ между вершинами графа:

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

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

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

В 1988 году Бояном Мохаром (Шаблон:Lang-sl) и Шаблон:Нп2 был предложен эффективный алгоритм вычисления индекса Винера для деревьев.

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

См. также

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