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

Индекс Рандича (Шаблон:Lang-en), известный также как индекс связности неориентированного графа $G=⟨A,V⟩$, является суммой вкладов по ребрам $\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)}}$.

История

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

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

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

Параметр	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

См. также

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

Литература

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