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

Этот инвариант графа ввёл Харо Хосойя в 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].