(Топологический) индекс Хосойи, известный также как Z индекс, графа — это полное число паросочетаний на нём. Индекс Хосойи всегда больше либо равен одному, поскольку пустое множество рёбер считается как паросочетание. Эквивалентно, индекс Хосойи — это число непустых паросочетаний плюс один.
История Этот инвариант графа ввёл в 1971. Он часто используется в хемоинформатике для исследования органических веществ.
В статье «The Topological Index Z Before and After 1971» («Топологический Индекс Z До и После 1971») об истории понятия и сопутствующих историях Хосойя пишет, что он ввёл индекс Z, чтобы указать на высокую корреляцию между температурой кипения алкановых изомеров и их Z-индексами, основываясь на неопубликованную работу 1957 года, когда он был студентом бакалавриата в Токийском университете.
Пример Линейные алканы в контексте индекса Хосойи могут быть представлены как пути без ветвлений. Путь с одной вершиной без рёбер (соответствующий молекуле метана) имеет одно (пустое) паросочетание, так что его индекс Хосойи равен единице. Путь с одним ребром (этан) имеет два паросочетания (одно – с пустым набором рёбер, другое с одним ребром), так что его индекс Хосойи равен двум. Пропан (путь длиной два) имеет три паросочетания — любое из его рёбер, плюс пустой набор рёбер. n-Бутан (путь длиной три) имеет пять паросочетаний, что отличает его от изобутана, который имеет четыре. В общем случае паросочетания в пути с k рёбрами либо образуют паросочетание с начальными рёбрами, либо образует паросочетание из первых рёбер плюс ребро, соединяющее две последние вершины. Таким образом, индексы Хосойи линейных алканов удовлетворяют рекуррентному соотношению чисел Фибоначчи. Структуры паросочетаний в этих графах могут быть визуализированы с помощью куба Фибоначчи.
Наибольшее возможное значение индекса Хосойи на графе с n вершинами задаётся полными графами, а индексы Хосойи для полных графов являются (телефонное число — это количество путей, которыми n телефонов могут быть соединены друг с другом, где каждый телефон соединяется только с одним другим телефоном (нет конференций). 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... ().
Алгоритмы Относится к трудновычислимым топологическим индексам. Вычисление индекса Хосойи является даже для планарных графов. Однако он может быть вычислен путём вычисления многочлена паросочетаний с аргументом 1. Основываясь на этом вычислении индекса Хосойи, задача является для графов ограниченной древовидной ширины и полиномиальной (с экспонентой, зависящей линейно от ширины) для графов ограниченной кликовой ширины.
В статье Трофимова дана оценка вычислительной сложности как , где — число ребер.
Примечания
Литература
Серия выпусков, посвящённая Haruo Hosoya по поводу 65 летия.
Категория:Инварианты графов Категория:Математическая химия Категория:Хемоинформатика Категория:Паросочетания