Индекс Хосоя

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

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

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

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

История

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

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

Пример

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

Наибольшее возможное значение индекса Хосоя на графе с вершинами задается полным графом . Индексы Хосоя для полных графов — это телефонные номера ${\displaystyle n}$ ${\displaystyle K_{n}}$

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

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

Алгоритмы

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

Примечания

1. Хосоя, Харуо (1971), «Топологический индекс. Недавно предложенная величина, характеризующая топологическую природу структурных изомеров насыщенных углеводородов», Бюллетень химического общества Японии , 44 (9): 2332–2339, doi : 10.1246/bcsj.44.2332.
2. Hosoya, Haruo (2002), «Топологический индекс Z до и после 1971 года», Internet Electronic Journal of Molecular Design , 1 (9): 428–442.
3. Интернет-электронный журнал молекулярного дизайна, специальные выпуски, посвященные профессору Харуо Хосоя по случаю 65-летия: Том 1 (2002), Номер 9 — Том 2 (2003), Номер 6.
4. Тичи, Роберт Ф.; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов в комбинаторной химии» (PDF) , Журнал вычислительной биологии , 12 (7): 1004–1013, doi :10.1089/cmb.2005.12.1004, PMID  16201918.
5. Джеррум, Марк (1987), «Двумерные системы мономер-димер вычислительно неразрешимы», Журнал статистической физики , 48 (1): 121–134, Bibcode : 1987JSP....48..121J, doi : 10.1007/BF01010403, S2CID  189854401.
6. Гутман, Иван (1991), «Многочлены в теории графов», в Bonchev, D.; Rouvray, DH (ред.), Химическая теория графов: Введение и основы , Математическая химия, т. 1, Taylor & Francis, стр. 133–176, ISBN 978-0-85626-454-2.
7. Курсель, Б .; Маковски, JA; Ротикс, У. (2001), «О сложности с фиксированными параметрами задач перечисления графов, определяемых в монадической логике второго порядка» (PDF) , Дискретная прикладная математика , 108 (1–2): 23–52, doi :10.1016/S0166-218X(00)00221-3.
8. Makowsky, JA; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006), "Вычисление графовых полиномов на графах ограниченной ширины клики", Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '06) (PDF) , Lecture Notes in Computer Science, т. 4271, Springer-Verlag, стр. 191–204, doi :10.1007/11917496_18, ISBN 978-3-540-48381-6.
9. Джеррум, Марк ; Синклер, Алистер (1996), «Глава 12: Метод Монте-Карло с использованием цепей Маркова: подход к приближенному подсчету и интегрированию», Аппроксимационные алгоритмы для NP-трудных задач (PDF) , PWS Publishing, стр. 482–520

Ссылки

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