WikiSort.ru - Не сортированное

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

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

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

См. также

• Топологический индекс
• Инвариант графа

Примечания

Это заготовка статьи по химии. Вы можете помочь проекту, дополнив её.