Індекс Вінера

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

Запропонований Гаррі Вінером^[en] 1947 року^[1], є першим з відомих графових топологічних індексів^[2]. Часто використовується в математичній хімії і хемоінформатиці під час побудови кількісних кореляцій «структура-властивість» для графів органічних молекул, що розглядаються без атомів водню.

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

Відомі також різні модифікації індексу, наприклад, розширений індекс Вінера^[10].

Див. також

• Хімічна теорія графів