Indeks Hosoya

Kompletny graf K ₄ ma dziesięć pokazanych dopasowań, więc jego indeks Hosoya wynosi dziesięć, maksimum dla dowolnego grafu z czterema wierzchołkami.

Indeks Hosoya , znany również jako indeks Z , wykresu to całkowita liczba dopasowań w nim. Indeks Hosoya wynosi zawsze co najmniej jeden, ponieważ pusty zbiór krawędzi jest liczony jako dopasowanie. Równoważnie indeks Hosoya to liczba niepustych dopasowań plus jeden. Indeks nosi imię Haruo Hosoya . Jest używany jako indeks topologiczny w chemicznej teorii grafów .

Pełne grafy mają największy indeks Hosoya dla dowolnej liczby wierzchołków; ich indeksy Hosoya to numery telefonów .

Historia

Ten niezmiennik wykresu został wprowadzony przez Haruo Hosoyę w 1971 roku. Jest często używany w chemoinformatyce do badań związków organicznych .

After 1971”, na temat historii tego pojęcia i związanych z nim historii wewnętrznych, Hosoya pisze, że wprowadził indeks Z, aby zgłosić dobrą korelację temperatur wrzenia izomerów alkanów i ich Z indeksy, opierając się na jego niepublikowanej pracy z 1957 roku, wykonanej podczas studiów licencjackich na Uniwersytecie Tokijskim .

Przykład

Alkan liniowy , dla celów indeksu Hosoya, może być przedstawiony jako wykres ścieżkowy bez rozgałęzień. Ścieżka z jednym wierzchołkiem i bez krawędzi (odpowiadająca metanu ) ma jedno (puste) dopasowanie, więc jej indeks Hosoya wynosi jeden; ścieżka z jedną krawędzią ( etan ) ma dwa dopasowania (jedno z zerowymi krawędziami i jedno z jedną krawędzią), więc jej indeks Hosoya wynosi dwa. Propan (ścieżka o długości dwóch) ma trzy dopasowania: jedną z jego krawędzi lub puste dopasowanie. n - butan (ścieżka o długości trzech) ma pięć dopasowań, co odróżnia ją od izobutanu , który ma cztery. Mówiąc bardziej ogólnie, dopasowanie na ścieżce z $-$ albo tworzy dopasowanie na pierwszych $1$ , albo tworzy dopasowanie na pierwszych krawędziach $-2}$${\ displaystyle$ krawędzi razem z końcową krawędzią ścieżki. Ta analiza przypadku pokazuje, że indeksy Hosoya liniowych alkanów są zgodne z rekurencją rządzącą liczbami Fibonacciego , a ponieważ mają również ten sam przypadek bazowy, muszą być równe liczbom Fibonacciego. Strukturę dopasowań na tych wykresach można zobrazować za pomocą kostki Fibonacciego .

Największą możliwą wartość indeksu Hosoya na wykresie z $n}}$${$ \ displaystyle . Indeksy Hosoya dla pełnych wykresów to numery telefonów

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (sekwencja A000085 w OEIS ).

Liczby te można wyrazić za pomocą formuły sumowania obejmującej silnie , as

$${\ Displaystyle \ suma _ {k = 0} ^ {\ lfloor n/2 \ rfloor} {\ Frac {n!} {2 ^ {k} \ cdot k! \ cdot \ lewo (n-2k \ prawo)! }}.}$$

Każdy wykres, który nie jest kompletny, ma mniejszy indeks Hosoya niż ta górna granica .

Algorytmy

Indeks Hosoya jest #P-zupełny do obliczenia, nawet dla grafów planarnych . Można go jednak obliczyć, oceniając pasujący wielomian m _G w argumencie 1. Na podstawie tej oceny obliczenie indeksu Hosoya jest wykonalne dla grafów o ograniczonej szerokości drzewa i wielomianu (z wykładnikiem, który zależy liniowo od width) dla wykresów o ograniczonej szerokości kliki . Indeks Hosoya można skutecznie przybliżyć do dowolnego pożądanego stałego współczynnika przybliżenia przy użyciu w pełni wielomianowego losowego schematu aproksymacji .

Notatki

•   Roberto Todeschini, Viviana Consonni (2000) „Podręcznik deskryptorów molekularnych”, Wiley-VCH , ISBN 3-527-29913-0