Interested Article - Индекс Хосойи

Полный граф K ₄ имеет десять (как показано) паросочетаний, так что индекс Хосойи равен десяти, это максимальный индекс для графов с четырьмя вершинами.

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

История

Этот инвариант графа ввёл в 1971 . Он часто используется в хемоинформатике для исследования органических веществ .

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

Пример

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

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

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

Алгоритмы

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

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

Примечания

, с. 2332–2339.
↑ , с. 428–442.
.
, с. 1004–1013.
, с. 121–134.
, с. 133–176.
, с. 23–52.
, с. 191–204.
, с. 327.

Литература

Haruo Hosoya. // Bulletin of the Chemical Society of Japan. — 1971. — Т. 44 , вып. 9 . — С. 2332–2339 . — doi : .
Haruo Hosoya. // Internet Electronic Journal of Molecular Design. — 2002. — Т. 1 , вып. 9 . — С. 428–442 .
// Internet Electronic Journal of Molecular Design. — 2002/2003. — Т. 1#9 – 2#6 . Серия выпусков, посвящённая Haruo Hosoya по поводу 65 летия.
Robert F. Tichy, Stephan Wagner. // . — 2005. — Т. 12 , вып. 7 . — С. 1004–1013 . — doi : .
Mark Jerrum. Two-dimensional monomer-dimer systems are computationally intractable // Journal of Statistical Physics. — 1987. — Т. 48 , вып. 1 . — С. 121–134 . — doi : .
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. // Discrete Applied Mathematics. — 2001. — Т. 108 , вып. 1–2 . — С. 23–52 . — doi : .
Makowsky J. A., Udi Rotics, Ilya Averbouch, Benny Godlin. Computing graph polynomials on graphs of bounded clique-width // . — Springer-Verlag, 2006. — Т. 4271. — С. 191–204. — (Lecture Notes in Computer Science). — ISBN 978-3-540-48381-6 . — doi : .
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 .