Индекс Хосоя - Hosoya index - Wikipedia
В Индекс Хосоя, также известный как Индекс Z, из график общее количество совпадения в этом. Индекс Хосоя всегда равен как минимум единице, потому что пустой набор ребер засчитывается как соответствие для этой цели. Аналогичным образом, индекс Хосоя - это количество непустых совпадений плюс один. Индекс назван в честь Харуо Хосоя.
История
Этот инвариант графа был представлен Харуо Хосоя в 1971 г.[1] Часто используется в химиоинформатика для исследований органические соединения.[2][3]
В своей статье «Топологический указатель Z до и после 1971 года» об истории этого понятия и связанных с ним внутренних историях Хосоя пишет, что он ввел индекс Z, чтобы сообщить о хорошей корреляции между точки кипения из алкан изомеры и их Z-индексы, основанные на его неопубликованной работе 1957 года, выполненной им, когда он был студентом Токийский университет.[2]
Пример
Линейный алкан, для целей индекса Хосоя, может быть представлен как граф путей без разветвления. Путь с одной вершиной и без ребер (соответствующий метан молекула) имеет одно (пустое) соответствие, поэтому ее индекс Хосоя равен единице; путь с одним краем (этан ) имеет два сопоставления (одно с нулевым ребром и одно с одним ребром), поэтому его индекс Хосоя равен двум. Пропан (Путь длиной два) имеет три сопоставления: либо его ребра, либо пустое сопоставление. п-бутан (путь длиной три) имеет пять соответствий, что отличает его от изобутан который имеет четыре. В более общем смысле, соответствие пути с k ребра либо образуют совпадение в первом k - 1 ребро, или он образует совпадение в первом k - 2 ребра вместе с последним краем дорожки. Таким образом, индексы Хосоя линейных алканов подчиняются повторяемости, определяющей Числа Фибоначчи. Структуру сопоставлений на этих графиках можно визуализировать с помощью Куб Фибоначчи.
Максимально возможное значение индекса Хосоя на графике с п вершин, задается полный график, а индексы Хосоя для полных графов - это телефонные номера
Алгоритмы
Индекс Хосоя равен # P-complete вычислить, даже для планарные графы.[5] Однако его можно рассчитать, оценив совпадающий многочлен мграмм при аргументе 1.[6] На основе этой оценки рассчитывается индекс Хосоя. управляемый с фиксированными параметрами для графов ограниченных ширина дерева[7] и многочлен (с показателем, линейно зависящим от ширины) для графов ограниченного ширина клики.[8]
Примечания
- ^ Хосоя, Харуо (1971), "Топологический указатель. Недавно предложенная величина, характеризующая топологическую природу структурных изомеров насыщенных углеводородов", Бюллетень химического общества Японии, 44 (9): 2332–2339, Дои:10.1246 / bcsj.44.2332.
- ^ а б Хосоя, Харуо (2002), «Топологический указатель Z до и после 1971 года ", Интернет-электронный журнал молекулярного дизайна, 1 (9): 428–442.
- ^ Интернет-электронный журнал молекулярного дизайна, специальные выпуски, посвященные профессору Харуо Хосоя к 65-летию со дня рождения: Том 1 (2002), Номер 9 - Том 2 (2003), Номер 6.
- ^ Тихи, Роберт Ф .; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов комбинаторной химии» (PDF), Журнал вычислительной биологии, 12 (7): 1004–1013, Дои:10.1089 / cmb.2005.12.1004, PMID 16201918.
- ^ Джеррам, Марк (1987), «Двумерные системы мономер-димер вычислительно трудноразрешимы», Журнал статистической физики, 48 (1): 121–134, Дои:10.1007 / BF01010403.
- ^ Гутман, Иван (1991), "Полиномы в теории графов", Бончев, Д .; Rouvray, D.H. (ред.), Химическая теория графов: введение и основы, Математическая химия, 1, Тейлор и Фрэнсис, стр. 133–176, ISBN 978-0-85626-454-2.
- ^ Курсель, Б.; Маковски, Дж. А .; Ротикс, У. (2001), «О сложности с фиксированным параметром задач перечисления графов, определяемых в монадической логике второго порядка» (PDF), Дискретная прикладная математика, 108 (1–2): 23–52, Дои:10.1016 / S0166-218X (00) 00221-3.
- ^ Маковски, Дж. А .; Ротикс, Уди; Авербуш, Илья; Годлин, Бенни (2006), "Вычисление многочленов графа на графах ограниченной ширины клики", Proc. 32-й международный семинар по теоретико-графическим концепциям в компьютерных науках (WG '06) (PDF), Конспект лекций по информатике, 4271, Springer-Verlag, стр. 191–204, Дои:10.1007/11917496_18, ISBN 978-3-540-48381-6.