Hosoyya index

(Topologický) Hosoyův index , také známý jako Z index , v grafu je celkový počet shod v grafu . Hosoyův index je vždy větší nebo roven jedné, protože prázdná množina hran se počítá jako shoda. Ekvivalentně je Hosoyův index počet neprázdných shod plus jedna.

Historie

Tento grafový invariant zavedl Haro Hosoya v roce 1971 [1] . Často se používá v chemoinformatice ke studiu organických látek [2] [3] .

V článku „Topologický index Z před a po roce 1971“ o historii konceptu a souvisejících dějinách Hosoya píše, že zavedl index Z, aby ukázal vysokou korelaci mezi bodem varu alkanových izomerů a jejich Z-indexy, založenými na na nepublikovaném článku z roku 1957, kdy byl vysokoškolským studentem na univerzitě v Tokiu [2] .

Příklad

Lineární alkany v kontextu Hosoyyova indexu mohou být reprezentovány jako nevětvené cesty . Cesta s jedním vrcholem bez hran (odpovídající molekule metanu ) má jednu (prázdnou) shodu, takže její Hosoyyův index je jedna. Cesta s jednou hranou ( etan ) má dvě shody (jedna s prázdnou sadou hran, druhá s jednou hranou), takže její Hosoyya index je dva. Propan (cesta délky dvě) má tři shody - kteroukoli z jeho hran a prázdnou sadu hran. n - Butan (cesta délky tři) má pět shod, což jej odlišuje od isobutanu , který má čtyři. Obecně platí, že shody v cestě s k hranami buď tvoří shodu s počátečními hranami, nebo tvoří shodu z prvních hran plus hrany spojující poslední dva vrcholy. Hosoyovy indexy lineárních alkanů tedy splňují rekurentní vztah Fibonacciho čísel . Odpovídající struktury v těchto grafech lze vizualizovat pomocí Fibonacciho kostky .

Největší možná hodnota Hosoyyova indexu na grafu s n vrcholy je dána úplnými grafy a Hosoyyovy indexy pro kompletní grafy telefonní čísla jednoho jiného telefonu (žádné konferenční hovory).

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (sekvence A000085 v OEIS ) [4] .

Algoritmy

Odkazuje na těžko vypočítatelné topologické indexy. Výpočet Hosoyova indexu je #P-complete i pro rovinné grafy [5] . Nicméně, to může být počítáno počítáním shody polynomial s argumentem 1 [6] . Na základě tohoto výpočtu Hosoyova indexu je problém pevně parametricky řešitelný pro grafy omezené šířky stromu [7] a polynom (s exponentem, který lineárně závisí na šířce) pro grafy šířky omezené kliky [8] .

Trofimovův článek uvádí odhad výpočetní složitosti jako , kde je počet hran [9] .

Poznámky

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

Literatura