Индекс Хосоя , также известный как индекс Z , графа - это общее количество совпадений в нем. Индекс Хосоя всегда равен по крайней мере единице, потому что пустой набор ребер считается сопоставлением для этой цели. Эквивалентно, индекс Хосоя - это количество непустых совпадений плюс один. Указатель назван в честь Харуо Хосоя .
История
Этот инвариант графа был введен Харуо Хосоя в 1971 году. [1] Он часто используется в хемоинформатике для исследования органических соединений . [2] [3]
В своей статье «топологический индекс Z до и после 1971 года» по истории понятия и связанному с ним внутри историй, Хосой пишет , что он ввел индекс Z , чтобы сообщить хорошую корреляцию кипения с алканами изомеров и их Z индексы, основанные на его неопубликованной работе 1957 года, выполненной во время учебы в Токийском университете . [2]
Пример
Линейный алкан для целей индекса Хосоя может быть представлен в виде графа путей без какого-либо ветвления. Путь с одной вершиной и без ребер (соответствующий молекуле метана ) имеет одно (пустое) соответствие, поэтому его индекс Хосоя равен единице; Путь с одним ребром ( этан ) имеет два сопоставления (одно с нулевым ребром и одно с одним ребром), поэтому его индекс Хосоя равен двум. Пропан (путь длиной два) имеет три соответствия: либо его края, либо пустое соответствие. п - бутан (длина-три путь) имеет пять паросочетаний, отличающий его от изобутана , который имеет четыре. В более общем смысле сопоставление в пути с k ребрами либо формирует сопоставление в первых k - 1 ребрах, либо оно формирует сопоставление в первых k - 2 ребрах вместе с последним ребром пути. Таким образом, индексы Hosoya линейных алканов подчиняются повторяемости, определяющей числа Фибоначчи . Структуру сопоставлений на этих графиках можно визуализировать с помощью куба Фибоначчи .
Наибольшее возможное значение индекса Хосоя на графе с n вершинами дается полным графом , а индексы Хосоя для полных графов - это телефонные номера
Алгоритмы
Индекс Хосоя является # P-полным для вычисления даже для плоских графов . [5] Однако его можно вычислить, оценив совпадающий многочлен m G в аргументе 1. [6] На основе этой оценки вычисление индекса Хосоя является управляемым с фиксированным параметром для графов с ограниченной шириной дерева [7] и полиномиальных значений. (с показателем, линейно зависящим от ширины) для графов ограниченной ширины клики . [8]
Заметки
- ^ Хосой, Хаий (1971), «Топологическая индекс Недавно предложенная величина , характеризующая топологической природу структурных изомеров насыщенных углеводородов.», Бюллетень химического общества Японии , 44 (9): 2332-2339, DOI : 10,1246 / bcsj .44.2332.
- ^ а б Хосоя, Харуо (2002), «Топологический индекс Z до и после 1971 года» , Internet Electronic Journal of Molecular Design , 1 (9): 428–442.
- ^ Интернет-электронный журнал молекулярного дизайна , специальные выпуски, посвященные профессору Харуо Хосоя по случаю 65-летия: Том 1 (2002), Номер 9 - Том 2 (2003), Номер 6.
- ^ Тихи, Роберт Ф .; Вагнер, Стефан (2005), "Экстремальные задачи для топологических индексов в комбинаторной химии" (PDF) , Журнал вычислительной биологии , 12 (7): 1004-1013, DOI : 10,1089 / cmb.2005.12.1004 , PMID 16201918.
- ^ Jerrum, Марк (1987), "Двумерные мономер-димер системы являются вычислительно неразрешимыми", Журнал статистической физики , 48 (1): 121-134, DOI : 10.1007 / BF01010403.
- ^ Гутман, Иван (1991), "Многочлены в теории графов", Бончев, Д .; Rouvray, DH (ред.), Химическая теория графов: Введение и основы , математическая химия, 1 , Taylor & Francis, стр. 133–176, ISBN 978-0-85626-454-2.
- ^ Курсель, Б .; Маковски, JA; Rotics, U. (2001), "О фиксированной сложности параметра проблем перечисления графов , определимый в монадической логике второго порядка" (PDF) , дискретная прикладная математика , 108 (1-2): 23-52, DOI : 10.1016 / S0166 -218X (00) 00221-3.
- ^ Маковски, JA; Ротикс, Уди; Авербуш Илья; Годлин, Бенни (2006), "Вычисление многочленов графа на графах ограниченной ширины клики", Proc. 32-й международный семинар по теоретико-графическим концепциям в компьютерных науках (WG '06) (PDF) , Lecture Notes in Computer Science, 4271 , Springer-Verlag, pp. 191–204, doi : 10.1007 / 11917496_18 , ISBN 978-3-540-48381-6.
Рекомендации
- Роберто Тодескини, Вивиана Консонни (2000) "Справочник молекулярных дескрипторов", Wiley-VCH , ISBN 3-527-29913-0