Русская Википедия:Индекс Рандича

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

История

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

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

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

Параметр	1	2
Граф	Файл:Graph n 6 p 5941.png	Файл:Graph n 6 p 2012.png
Мини-код <math>\mu_{min}</math>	3885	3576
Индекс Рандича <math>r</math>	<math>\frac{4}{3} + \frac{2\sqrt{6}}{3} \approx 2,966</math>	<math>\frac{4}{3} + \frac{2\sqrt{6}}{3} \approx 2,966</math>

Параметр	1	2
Граф	Файл:Graph n 6 p 7100.png	Файл:Graph n 6 p 4060.png
Мини-код <math>\mu_{min}</math>	7916	7672
Индекс Рандича <math>r</math>	3	3

См. также

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

Литература

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