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

Индекс Рандича (англ. 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	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

См. также

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

Литература

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