WikiSort.ru - Не сортированное

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

История

Этот инвариант графа ввёл Харо Хосойя^[en] в 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 вершинами задаётся полными графами, а индексы Хосойи для полных графов являются телефонными числами^[en] (телефонное число — это количество путей, которыми n телефонов могут быть соединены друг с другом, где каждый телефон соединяется только с одним другим телефоном (нет конференций).

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

Алгоритмы

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

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

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.