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

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

Содержание

ИсторияПравить

Этот инвариант графа ввёл Харо Хосойя[en] в 1971[1]. Он часто используется в хемоинформатике для исследования органических веществ[2][3].

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

ПримерПравить

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

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

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

АлгоритмыПравить

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

В статье Трофимова дана оценка вычислительной сложности как  , где   — число ребер[9].

ПримечанияПравить

  1. Hosoya, 1971, с. 2332–2339.
  2. 1 2 Hosoya, 2002, с. 428–442.
  3. 65 лет Haruo Hosoya, 2002/2003.
  4. Tichy, Wagner, 2005, с. 1004–1013.
  5. Jerrum, 1987, с. 121–134.
  6. Gutman, 1991, с. 133–176.
  7. Courcelle, Makowsky, Rotics, 2001, с. 23–52.
  8. Makowsky, Rotics, Averbouch, Godlin, 2006, с. 191–204.
  9. Trofimov, 1991, с. 327.

ЛитератураПравить