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