Индекс Хосойи (Nu;ytv }kvkwn)

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

История

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

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

Пример

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

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

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

Алгоритмы

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

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

Примечания

↑ Hosoya, 1971, с. 2332–2339.
↑ ¹ ² Hosoya, 2002, с. 428–442.
↑ 65 лет Haruo Hosoya, 2002/2003.
↑ Tichy, Wagner, 2005, с. 1004–1013.
↑ Jerrum, 1987, с. 121–134.
↑ Gutman, 1991, с. 133–176.
↑ Courcelle, Makowsky, Rotics, 2001, с. 23–52.
↑ Makowsky, Rotics, Averbouch, Godlin, 2006, с. 191–204.
↑ 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.

[_0c71afc96755741c-1] Hosoya, 1971, с. 2332–2339.

[_1a6458bd3f66d8df-2] ¹ ² Hosoya, 2002, с. 428–442.

[_3d350374328458df-3] 65 лет Haruo Hosoya, 2002/2003.

[_129df94e56d2c3a8-4] Tichy, Wagner, 2005, с. 1004–1013.

[_b2a1fa748dbcbd24-5] Jerrum, 1987, с. 121–134.

[_d667cb13ccc5bfa9-6] Gutman, 1991, с. 133–176.

[_9284e345975df30b-7] Courcelle, Makowsky, Rotics, 2001, с. 23–52.

[_130b9f9e919fe11b-8] Makowsky, Rotics, Averbouch, Godlin, 2006, с. 191–204.

[_1c04619d18a48f6d-9] Trofimov, 1991, с. 327.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]