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

${\displaystyle r=\sum _{(v_{i},v_{j})\in V}{\frac {1}{\sqrt {d(v_{i})d(v_{j})}}}}$ .

История

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

Примеры совпадения индекса для неизоморфных графов

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

Параметр	1	2
Граф
Мини-код ${\displaystyle \mu _{min}}$	3885	3576
Индекс Рандича ${\displaystyle r}$	${\displaystyle {\frac {4}{3}}+{\frac {2{\sqrt {6}}}{3}}\approx 2,966}$	${\displaystyle {\frac {4}{3}}+{\frac {2{\sqrt {6}}}{3}}\approx 2,966}$

Параметр	1	2
Граф
Мини-код ${\displaystyle \mu _{min}}$	7916	7672
Индекс Рандича ${\displaystyle r}$	3	3

См. также

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

Ссылки

Литература

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