Индекс Рандича

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Индекс Рандича (англ. Randić index), известный также как индекс связности неориентированного графа G=\left \langle A, V \right \rangle, является суммой вкладов по ребрам \frac{1}{\sqrt{d(v_i) d(v_j)}}, где v_i и v_j — вершины, образующие ребро, d(v_k) — степень вершины v_k:

r=\sum_{(v_i, v_j) \in V} \frac{1}{\sqrt{d(v_i) d(v_j)}}.

История[править | править исходный текст]

Этот инвариант графов был введен Миланом Рандичем (англ.) в 1975 г.[1] Он часто используется в математической химии и хемоинформатике при построении количественных корреляций «структура-свойство».

Примеры совпадения индекса для неизоморфных графов[править | править исходный текст]

Индекс Рандича характеризуется неплохой дифференцирующей способностью, однако не является полным инвариантом. Для приведенных ниже пар графов он совпадает, хотя графы не являются изоморфными.

Параметр 1 2
Граф Graph n 6 p 5941.png Graph n 6 p 2012.png
Мини-код \mu_{min} 3885 3576
Индекс Рандича r \frac{4}{3} + \frac{2\sqrt{6}}{3} \approx 2,966 \frac{4}{3} + \frac{2\sqrt{6}}{3} \approx 2,966
Параметр 1 2
Граф Graph n 6 p 7100.png Graph n 6 p 4060.png
Мини-код \mu_{min} 7916 7672
Индекс Рандича r 3 3

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

  1. Randić, M. (1975), "«Characterization of molecular branching»", Journal of the American Chemical Society Т. 97 (23): 6609–6615, DOI 10.1021/ja00856a001 .

Литература[править | править исходный текст]

  • Roberto Todeschini, Viviana Consonni (2009) «Molecular Descriptors for Chemoinformatics», Wiley-VCH, ISBN 978-3-527-31852-0