Индекс Хосоя

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

Полные графы имеют наибольший индекс Хосоя для любого заданного количества вершин; их индексы Хосоя — это телефонные номера .

История

Этот инвариант графа был введен Харуо Хосоей в 1971 году. ^[1] Его часто используют в хемоинформатике для исследования органических соединений . ^[2]^[3]

«Топологический индекс Z до и после 1971 года», посвященной истории этого понятия и связанным с ним внутренним историям, Хосоя пишет, что он ввел индекс Z, чтобы сообщить о хорошей корреляции температур кипения алкановых В своей статье изомеров и их Z. индексы, основанные на его неопубликованной работе 1957 года, выполненной, когда он был студентом Токийского университета . ^[2]

Пример

Линейный алкан для целей индекса Хосоя может быть представлен в виде графа путей без какого-либо разветвления. Путь с одной вершиной и без ребер (соответствующий молекуле метана ) имеет одно (пустое) сопоставление, поэтому его индекс Хосоя равен единице; путь с одним ребром ( этан ) имеет два паросочетания (одно с нулевым ребром и одно с одним ребром), поэтому его индекс Хосоя равен двум. Пропан (путь длиной два) имеет три паросочетания: либо его ребра, либо пустое паросочетание. n - бутан (путь длиной три) имеет пять совпадений, в отличие от изобутана , у которого их четыре. В более общем смысле, совпадение в пути с $k$ ребра либо образуют паросочетание в первом $k-1$ ребра, или образует паросочетание в первом $k-2$ края вместе с последним краем пути. Анализ этого случая показывает, что индексы Хосоя линейных алканов подчиняются повторяемости, управляющей числами Фибоначчи , и, поскольку они также имеют один и тот же базовый случай, они должны равняться числам Фибоначчи. Структуру паросочетаний на этих графиках можно визуализировать с помощью куба Фибоначчи .

Максимально возможное значение индекса Хосоя на графике с $n$ вершин, задается полным графом $K_{n}$ . Индексами Хосоя для полных графов являются номера телефонов.

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (последовательность A000085 в OEIS ).

Эти числа можно выразить формулой суммирования , включающей факториалы , как $\sum _{k=0}^{\lfloor n/2\rfloor }{\frac {n!}{2^{k}\cdot k!\cdot \left(n-2k\right)!}}.$ Каждый неполный граф имеет индекс Хосоя меньший, чем эта верхняя граница . ^[4]

Алгоритмы

Индекс Хосоя является #P-полным для вычисления даже для плоских графов . ^[5] Однако его можно вычислить, оценив согласующий полином m _G по аргументу 1. ^[6] На основе этой оценки расчет индекса Хосоя является управляемым с фиксированными параметрами для графов с ограниченной шириной дерева. ^[7] и полиномиальный (с показателем, линейно зависящим от ширины) для графов ограниченной кликовой ширины . ^[8]Индекс Хосоя можно эффективно аппроксимировать до любого желаемого постоянного коэффициента аппроксимации, используя полностью полиномиальную рандомизированную схему аппроксимации . ^[9]

Примечания

^ Хосоя, Харуо (1971), «Топологический индекс. Недавно предложенная величина, характеризующая топологическую природу структурных изомеров насыщенных углеводородов», Бюллетень Химического общества Японии , 44 (9): 2332–2339, doi : 10.1246/bcsj. 44.2332 .
^ Jump up to: Перейти обратно: ^а ^б Хосоя, Харуо (2002), «Топологический индекс Z до и после 1971 года» , Интернет-электронный журнал молекулярного дизайна , 1 (9): 428–442 .
^ Интернет-электронный журнал молекулярного дизайна , специальные выпуски, посвященные профессору Харуо Хосоя по случаю 65-летия: Том 1 (2002 г.), номер 9 — Том 2 (2003 г.), номер 6.
^ Тичи, Роберт Ф.; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов в комбинаторной химии» (PDF) , Journal of Computational Biology , 12 (7): 1004–1013, doi : 10.1089/cmb.2005.12.1004 , PMID 16201918 .
^ Джеррум, Марк (1987), «Двумерные системы мономер-димер вычислительно неразрешимы», Journal of Statistical Physics , 48 (1): 121–134, Bibcode : 1987JSP....48..121J , doi : 10.1007/ БФ01010403 , S2CID 189854401 .
^ Гутман, Иван (1991), «Полиномы в теории графов», Бончев, Д.; Рувре, Д.Х. (ред.), Химическая теория графов: введение и основы , Математическая химия, том. 1, Тейлор и Фрэнсис, стр. 133–176, ISBN. 978-0-85626-454-2 .
^ Курсель, Б. ; Маковский, Дж. А.; Ротикс, У. (2001), «О сложности задач перечисления графов с фиксированным параметром, определяемых в монадической логике второго порядка» (PDF) , Discrete Applied Mathematics , 108 (1–2): 23–52, doi : 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 .
^ Джеррам, Марк ; Синклер, Алистер (1996), «Глава 12: Метод Монте-Карло для цепей Маркова: подход к приближенному подсчету и интегрированию», Алгоритмы аппроксимации для NP-сложных задач (PDF) , PWS Publishing, стр. 482–520

Ссылки

Роберто Тодескини, Вивиана Консонни (2000) «Справочник по молекулярным дескрипторам», Wiley-VCH , ISBN 3-527-29913-0

[1] Хосоя, Харуо (1971), «Топологический индекс. Недавно предложенная величина, характеризующая топологическую природу структурных изомеров насыщенных углеводородов», Бюллетень Химического общества Японии , 44 (9): 2332–2339, doi : 10.1246/bcsj. 44.2332 .

[before-2] Jump up to: Перейти обратно: ^а ^б Хосоя, Харуо (2002), «Топологический индекс Z до и после 1971 года» , Интернет-электронный журнал молекулярного дизайна , 1 (9): 428–442 .

[3] Интернет-электронный журнал молекулярного дизайна , специальные выпуски, посвященные профессору Харуо Хосоя по случаю 65-летия: Том 1 (2002 г.), номер 9 — Том 2 (2003 г.), номер 6.

[4] Тичи, Роберт Ф.; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов в комбинаторной химии» (PDF) , Journal of Computational Biology , 12 (7): 1004–1013, doi : 10.1089/cmb.2005.12.1004 , PMID 16201918 .

[5] Джеррум, Марк (1987), «Двумерные системы мономер-димер вычислительно неразрешимы», Journal of Statistical Physics , 48 (1): 121–134, Bibcode : 1987JSP....48..121J , doi : 10.1007/ БФ01010403 , S2CID 189854401 .

[6] Гутман, Иван (1991), «Полиномы в теории графов», Бончев, Д.; Рувре, Д.Х. (ред.), Химическая теория графов: введение и основы , Математическая химия, том. 1, Тейлор и Фрэнсис, стр. 133–176, ISBN. 978-0-85626-454-2 .

[7] Курсель, Б. ; Маковский, Дж. А.; Ротикс, У. (2001), «О сложности задач перечисления графов с фиксированным параметром, определяемых в монадической логике второго порядка» (PDF) , Discrete Applied Mathematics , 108 (1–2): 23–52, doi : 10.1016/S0166 -218X(00)00221-3 .

[8] Маковский, Дж. А.; Ротикс, Уди; Авербуш, Илья; Годлин, Бенни (2006), «Вычисление полиномов графа на графах ограниченной ширины клики», Proc. 32-й международный семинар по теоретико-графовым концепциям в информатике (WG '06) (PDF) , Конспекты лекций по информатике, том. 4271, Springer-Verlag, стр. 191–204, номер документа : 10.1007/11917496_18 , ISBN. 978-3-540-48381-6 .

[9] Джеррам, Марк ; Синклер, Алистер (1996), «Глава 12: Метод Монте-Карло для цепей Маркова: подход к приближенному подсчету и интегрированию», Алгоритмы аппроксимации для NP-сложных задач (PDF) , PWS Publishing, стр. 482–520

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]