Индекс Хосойи

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

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

История

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

В статье «The Topological Index Z Before and After 1971» («Топологический Индекс Z До и После 1971») об истории понятия и сопутствующих историях Хосойя пишет, что он ввёл индекс Z, чтобы указать на высокую корреляцию между температурой кипения алкановых изомеров и их Z-индексами, основываясь на неопубликованную работу 1957 года, когда он был студентом бакалавриата в Токийском университете^[2].

Пример

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

Наибольшее возможное значение индекса Хосойи на графе с n вершинами задаётся полными графами, а индексы Хосойи для полных графов являются телефонными числами^[англ.] (телефонное число — это количество путей, которыми n телефонов могут быть соединены друг с другом, где каждый телефон соединяется только с одним другим телефоном (нет конференций).

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

Алгоритмы

Относится к трудновычислимым топологическим индексам. Вычисление индекса Хосойи является #P-полной задачей^[англ.] даже для планарных графов^[5]. Однако он может быть вычислен путём вычисления многочлена паросочетаний ${\displaystyle m_{G}}$ с аргументом 1^[6]. Основываясь на этом вычислении индекса Хосойи, задача является фиксированно-параметрически разрешимой^[англ.] для графов ограниченной древесной ширины^[7] и полиномиальной (с экспонентой, зависящей линейно от ширины) для графов ограниченной кликовой ширины^[8].

В статье Трофимова дана оценка вычислительной сложности как ${\displaystyle O(\exp(E))}$, где ${\displaystyle E}$ — число ребер^[9].

Примечания

1. Hosoya, 1971, с. 2332–2339.
2. Hosoya, 2002, с. 428–442.
3. 65 лет Haruo Hosoya, 2002/2003.
4. Tichy, Wagner, 2005, с. 1004–1013.
5. Jerrum, 1987, с. 121–134.
6. Gutman, 1991, с. 133–176.
7. Courcelle, Makowsky, Rotics, 2001, с. 23–52.
8. Makowsky, Rotics, Averbouch, Godlin, 2006, с. 191–204.
9. Trofimov, 1991, с. 327.

Литература

• Haruo Hosoya. Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons // Bulletin of the Chemical Society of Japan. — 1971. — Т. 44, вып. 9. — С. 2332–2339. — doi:10.1246/bcsj.44.2332.
• Haruo Hosoya. The topological index Z before and after 1971 // Internet Electronic Journal of Molecular Design. — 2002. — Т. 1, вып. 9. — С. 428–442.
• special issues dedicated to Professor Haruo Hosoya on the occasion of the 65th birthday // Internet Electronic Journal of Molecular Design. — 2002/2003. — Т. 1#9 – 2#6. Серия выпусков, посвящённая Haruo Hosoya по поводу 65 летия.
• Robert F. Tichy, Stephan Wagner. Extremal problems for topological indices in combinatorial chemistry // Journal of Computational Biology. — 2005. — Т. 12, вып. 7. — С. 1004–1013. — doi:10.1089/cmb.2005.12.1004.
• Mark Jerrum. Two-dimensional monomer-dimer systems are computationally intractable // Journal of Statistical Physics. — 1987. — Т. 48, вып. 1. — С. 121–134. — doi:10.1007/BF01010403.
• Ivan Gutman. Polynomials in graph theory // Chemical Graph Theory: Introduction and Fundamentals / Bonchev D., Rouvray D. H.. — Taylor & Francis, 1991. — Т. 1. — С. 133–176. — (Mathematical Chemistry). — ISBN 978-0-85626-454-2.
• Courcelle B., Makowsky J. A., Rotics U. On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic // Discrete Applied Mathematics. — 2001. — Т. 108, вып. 1–2. — С. 23–52. — doi:10.1016/S0166-218X(00)00221-3.
• Makowsky J. A., Udi Rotics, Ilya Averbouch, Benny Godlin. Computing graph polynomials on graphs of bounded clique-width // Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '06). — Springer-Verlag, 2006. — Т. 4271. — С. 191–204. — (Lecture Notes in Computer Science). — ISBN 978-3-540-48381-6. — doi:10.1007/11917496_18.
• Roberto Todeschini, Viviana Consonni. Handbook of Molecular Descriptors. — Wiley-VCH, 2000. — ISBN 3-527-29913-0.
• Trofimov M. I. An Optimization of Procedure for Calculation of Hosoya’s Index // J. Math. Chem.. — 1991. — Вып. 9.