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

Индекс Рандича (англ. 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
Граф
Мини-код $\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
Граф
Мини-код $\mu _{min}$	7916	7672
Индекс Рандича $r$	3	3

См. также

Ссылки

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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