Indeks Wienera

W teorii grafów chemicznych indeks Wienera (również liczba Wienera ) wprowadzony przez Harry'ego Wienera jest indeksem topologicznym cząsteczki , definiowanym jako suma długości najkrótszych ścieżek między wszystkimi parami wierzchołków grafu chemicznego reprezentującego nie- atomy wodoru w cząsteczce.

Indeks Wienera może być używany do reprezentacji sieci komputerowych i zwiększania bezpieczeństwa sprzętu kratowego .

Historia

Indeks Wienera nosi imię Harry'ego Wienera , który wprowadził go w 1947 roku; w tamtym czasie Wiener nazywał to „numerem ścieżki”. Jest to najstarszy indeks topologiczny związany z rozgałęzieniami molekularnymi. W oparciu o jego sukces, po pracach Wienera opracowano wiele innych indeksów topologicznych grafów chemicznych, opartych na informacjach zawartych w macierzy odległości wykresu.

Ta sama wielkość była również badana w czystej matematyce pod różnymi nazwami, w tym statusem brutto, odległością wykresu i transmisją. Indeks Wienera jest również ściśle powiązany z bliskością centralności wierzchołka na grafie, wielkością odwrotnie proporcjonalną do sumy wszystkich odległości między danym wierzchołkiem a wszystkimi innymi wierzchołkami, która była często używana w socjometrii i teorii sieci społecznych .

Przykład

Butan (C ₄ H ₁₀ ) ma dwa różne izomery strukturalne : n -butan o liniowej strukturze czterech atomów węgla i izobutan o strukturze rozgałęzionej. Graf chemiczny dla n -butanu to czterowierzchołkowy wykres ścieżkowy , a wykres chemiczny dla izobutanu to drzewo z jednym środkowym wierzchołkiem połączonym z trzema liśćmi.

Dwa izomery butanu
n-butan
izobutan

Cząsteczka n -butanu ma trzy pary wierzchołków w odległości jeden od siebie, dwie pary w odległości dwa i jedną parę w odległości trzech, więc jej indeks Wienera wynosi

{\ Displaystyle 3 \ razy 1 + 2 \ razy 2 + 1 \ razy 3 = 10.}

Cząsteczka izobutanu ma trzy pary wierzchołków w odległości jednej od siebie (trzy pary środek liścia) i trzy pary w odległości drugiej (pary liść-liść). Dlatego jego indeks Wienera wynosi

{\ Displaystyle 3 \ razy 1 + 3 \ razy 2 = 9.}

Liczby te są instancjami formuł dla szczególnych przypadków indeksu Wienera: jest to dla dowolnej $Displaystyle$ - wierzchołka $(n ^ {3} -n) / 6}$ $n$ , taki jak wykres -butanu i dla dowolnej $wierzchołka$ , wykres

Tak więc, chociaż te dwie cząsteczki mają ten sam wzór chemiczny i taką samą liczbę wiązań węgiel-węgiel i węgiel-wodór, ich różne struktury powodują różne indeksy Wienera.

Związek z właściwościami chemicznymi

, że liczba indeksu Wienera jest ściśle skorelowana z temperaturami wrzenia cząsteczek alkanu . Późniejsze prace nad ilościowymi zależnościami struktura-aktywność wykazały, że jest ona również skorelowana z innymi wielkościami, w tym parametrami punktu krytycznego , gęstością , napięciem powierzchniowym i lepkością fazy ciekłej oraz powierzchnią van der Waalsa cząsteczki.

Obliczenia w dowolnych wykresach

Indeks Wienera można obliczyć bezpośrednio za pomocą algorytmu obliczania wszystkich odległości parami na wykresie. Gdy wykres jest nieważony (a więc długość ścieżki to tylko liczba jej krawędzi), odległości te można obliczyć, powtarzając algorytm przeszukiwania wszerz , raz dla każdego wierzchołka początkowego. Całkowity czas dla tego podejścia wynosi O( nm ), gdzie n to liczba wierzchołków grafu, a m to liczba jego krawędzi.

W przypadku wykresów ważonych można zamiast tego użyć algorytmu Floyda-Warshalla lub algorytmu Johnsona , odpowiednio z czasem działania O ( n ³ ) lub O ( nm + n ² log n ). W literaturze z zakresu informatyki chemicznej opracowano również alternatywne, ale mniej wydajne algorytmy oparte na wielokrotnym mnożeniu macierzy .

Obliczenia w specjalnych typach grafów

Gdy podstawowym wykresem jest drzewo (jak to jest prawdą na przykład w przypadku alkanów pierwotnie badanych przez Wienera), indeks Wienera można obliczyć wydajniej. Jeśli graf jest podzielony na dwa poddrzewa przez usunięcie pojedynczej krawędzi e , to jego indeks Wienera jest sumą indeksów Wienera dwóch poddrzew wraz z trzecim terminem reprezentującym ścieżki przechodzące przez e . Ten trzeci wyraz można obliczyć w czasie liniowym, obliczając sumę odległości wszystkich wierzchołków od e w każdym poddrzewie i mnożąc te dwie sumy. Ten algorytm dziel i zwyciężaj można uogólnić z drzew na grafy o ograniczonej szerokości drzewa i prowadzi do algorytmów w czasie prawie liniowym dla takich grafów.

Alternatywna metoda obliczania indeksu Wienera drzewa, autorstwa Bojana Mohara i Tomaža Pisanskiego , polega na uogólnieniu problemu na wykresy z ważonymi wierzchołkami, gdzie waga ścieżki jest iloczynem jej długości i wag jej dwóch punktów końcowych. Jeśli v jest wierzchołkiem liścia drzewa, to indeks Wienera drzewa można obliczyć, łącząc v z jego rodzicem (dodając razem ich wagi), obliczając indeks wynikowego mniejszego drzewa i dodając prosty składnik korygujący dla ścieżek które przechodzą przez krawędź z v do swojego rodzica. Wielokrotnie usuwając liście w ten sposób, można obliczyć wskaźnik Wienera w czasie liniowym.

W przypadku wykresów, które są zbudowane jako iloczyn prostszych wykresów, indeks Wienera wykresu produktu można często obliczyć za pomocą prostej formuły, która łączy wskaźniki jego czynników. Benzenoidy (wykresy utworzone przez sklejenie sześciokątów foremnych od krawędzi do krawędzi) można osadzić izometrycznie w iloczynie kartezjańskim trzech drzew, umożliwiając obliczenie ich indeksów Wienera w czasie liniowym przy użyciu wzoru iloczynu wraz z algorytmem drzewa czasu liniowego.

Problem odwrotny

Gutman i Yeh (1995) rozważali problem określenia, które liczby mogą być reprezentowane jako indeks Wienera grafu. Pokazali, że wszystkie dodatnie liczby całkowite z wyjątkiem dwóch mają taką reprezentację; dwoma wyjątkami są liczby 2 i 5, które nie są indeksem Wienera żadnego wykresu. W przypadku grafów, które muszą być dwudzielne, odkryli, że ponownie można przedstawić prawie wszystkie liczby całkowite, z większym zestawem wyjątków: żadna z liczb w zestawie

{2, 3, 5, 6, 7, 11, 12, 13, 15, 17, 19, 33, 37, 39}

można przedstawić jako indeks Wienera wykresu dwudzielnego.

Gutman i Yeh przypuszczali, ale nie byli w stanie udowodnić, podobnego opisu liczb, które można przedstawić jako wskaźniki Wienera drzew, z zestawem 49 wyjątkowych wartości:

2, 3, 5, 6, 7, 8, 11, 12, 13, 14, 15, 17, 19, 21, 22, 23, 24, 26, 27, 30, 33, 34, 37, 38, 39, 41, 43, 45, 47, 51, 53, 55, 60, 61, 69, 73, 77, 78, 83, 85, 87, 89, 91, 99, 101, 106, 113, 147, 159 (sekwencja A122686 w OIS )

Przypuszczenie zostało później udowodnione przez Wagnera, Wanga i Yu.

Linki zewnętrzne

Weisstein, Eric W. „Indeks Wienera” . MathWorld .