Łączność algebraiczna

Przykładowy wykres z 6 wierzchołkami, średnicą 3, łącznością 1 i łącznością algebraiczną 0,722

Łączność algebraiczna (znana również jako wartość Fiedlera lub wartość własna Fiedlera od Miroslava Fiedlera ) wykresu G jest drugą najmniejszą wartością własną (licząc oddzielnie wiele wartości własnych) macierzy Laplaca G . Ta wartość własna jest większa od 0 wtedy i tylko wtedy, gdy G jest grafem spójnym . Jest to następstwem faktu, że liczba razy 0 pojawiających się jako wartość własna w Laplace'u to liczba połączonych elementów na wykresie. Wielkość tej wartości odzwierciedla, jak dobrze połączony jest ogólny wykres. Został wykorzystany do analizy odporności i synchronizowalności sieci.

Nieruchomości

Ścięty dwudziestościan lub graf Buckminsterfullerene ma tradycyjną łączność 3 i łączność algebraiczną 0,243.

Łączność algebraiczna grafów nieskierowanych z nieujemnymi wagami, $czym$ nierówność jest ścisła wtedy i tylko wtedy, gdy Jednak spójność algebraiczna może być ujemna dla grafów ogólnie skierowanych, nawet jeśli G jest grafem spójnym . Ponadto wartość łączności algebraicznej jest ograniczona powyżej przez tradycyjną (wierzchołkową) łączność grafu, ${\ Displaystyle {\ tekst {łączność algebraiczna}} \ leq {\ tekst {łączność}}}$ . Jeśli liczba wierzchołków nieskierowanego połączonego wykresu z nieujemnymi wagami krawędzi wynosi n , a średnica wynosi D , wiadomo również, że spójność algebraiczna jest ograniczona poniżej ${\ displaystyle {\ tekst {łączność algebraiczna}} \ geq {\ frac {1}{nD}}}$ i faktycznie (w wyniku Brendana McKay'a ) przez ${\ displaystyle {\ frac {4} {nD}}}$ . Dla wykresu z 6 węzłami pokaż powyżej (n=6, D=3) te związane średnie, 4/18 = 0,222 ≤ łączność algebraiczna 0,722 ≤ łączność 1.

W przeciwieństwie do tradycyjnej łączności ^{[ wymagane wyjaśnienie ]} , łączność algebraiczna zależy od liczby wierzchołków, a także od sposobu, w jaki wierzchołki są połączone. W grafach losowych spójność algebraiczna maleje wraz z liczbą wierzchołków i rośnie ze średnim stopniem .

Dokładna definicja łączności algebraicznej zależy od rodzaju użytego języka laplacyjskiego. Fan Chung opracował obszerną teorię, używając przeskalowanej wersji Laplace'a, eliminując zależność od liczby wierzchołków, tak że granice są nieco inne.

W modelach synchronizacji w sieciach, takich jak model Kuramoto , macierz Laplaca powstaje naturalnie, więc łączność algebraiczna wskazuje, jak łatwo sieć będzie się synchronizować. Można również zastosować inne miary, takie jak średnia odległość (charakterystyczna długość ścieżki), a w rzeczywistości łączność algebraiczna jest ściśle związana z (odwrotnością) średniej odległości.

Łączność algebraiczna odnosi się również do innych atrybutów łączności, takich jak liczba izoperymetryczna , która jest ograniczona od dołu przez połowę łączności algebraicznej.

Wektor Fiedlera

Oryginalna teoria związana z łącznością algebraiczną została stworzona przez Miroslava Fiedlera . Na jego cześć wektor własny związany z łącznością algebraiczną został nazwany wektorem Fiedlera . Wektor Fiedlera może być użyty do podzielenia wykresu.

Podział grafu za pomocą wektora Fiedlera

Podział na dwa połączone grafy.

Na przykładowym wykresie w części wprowadzającej wektor Fiedlera to ${\textstyle {\zaczynać{pmatrix}0,415&0,309&0,069&-0,221&0,221&-0,794\koniec {pmatrix} }}$ . Wartości ujemne są związane ze słabo połączonym wierzchołkiem 6 i sąsiednim punktem przegubu , wierzchołkiem 4; podczas gdy wartości dodatnie są powiązane z innymi wierzchołkami. Znaki wartości w wektorze Fiedlera można zatem wykorzystać do podzielenia tego wykresu na dwa składniki: ${\ textstyle \ {1,2,3,5 \} ,\{4,6\}}$ . Alternatywnie, wartość 0,069 (która jest bliska zeru) może być umieszczona we własnej klasie, dzieląc wykres na trzy składowe: ${\ textstyle \{1,2,5\},\{3\},\{4,6\}}$ lub przeniesiony do innej partycji ${\ textstyle \ { 1,2,5\},\{3,4,6\}}$ , jak na zdjęciu. Kwadratowe wartości składowych wektora Fiedlera, sumujące się do jednego, ponieważ wektor jest znormalizowany, można interpretować jako prawdopodobieństwa odpowiednich punktów danych, które mają zostać przypisane do partycji opartej na znakach.

Zobacz też