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

Індекс Вінера (Шаблон: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)$.

Запропонований Шаблон:Iw 1947 року, є першим з відомих графових топологічних індексів. Часто використовується в математичній хімії і хемоінформатиці під час побудови кількісних кореляцій «структура-властивість» для графів органічних молекул, що розглядаються без атомів водню.

1988 року Боян Мохар (Шаблон:Lang-sl) і Шаблон:Iw запропонували ефективний алгоритм обчислення індексу Вінера для дерев.

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

Див. також

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