Ekspander

Szablon:Inne znaczenia Ekspander – graf o niewielkiej liczbie krawędzi, w którym każdy podzbiór wierzchołków ma dużo sąsiadów. Istnieje kilka nierównoważnych formalizacji tej własności, definiujących różne klasy ekspanderów. Ekspandery pozwoliły na uzyskanie kilku istotnych wyników z różnych dziedzin informatyki: dowodów w teorii złożoności, projektowaniu sieci sortujących, kodów korekcji błędów, ekstraktorów losowości i odpornych na błędy schematów komunikacji w sieciach komputerowych.

Definicje

W zależności od kontekstu, używa się różnych sposobów mierzenia ekspansji grafu.

Ekspansja wierzchołkowa

$\alpha$ – ekspansja wierzchołkowa grafu to współczynnik

$g_{\alpha }(G)=\underset{1⩽|S|⩽\alpha n}{\min }\frac{|\mathrm{\Gamma }(S)|}{|S|},$

gdzie $\mathrm{\Gamma }(S)$ oznacza zbiór wszystkich sąsiadów zbioru $S$ (wierzchołków połączonych z tym zbiorem krawędzią). W niektórych zastosowaniach używa się pojęcia ekspansji jednokrawędziowej, gdzie bierze się pod uwagę tylko sąsiadów połączonych dokładnie jedną krawędzią z $S.$

Ekspansja krawędziowa

Współczynnik ekspansji krawędziowej grafu $G$ definiuje się jako:

$h_{\alpha }(G)=\underset{1⩽|S|⩽\alpha n}{\min }\frac{|\partial (S)|}{|S|},$

gdzie $\partial (S)$ oznacza zbiór krawędzi które łączą wierzchołek z $S$ z wierzchołkiem spoza $S.$

Ekspansja spektralna

Przedstawiając graf jako macierz sąsiedztwa, można zdefiniować ekspansję w terminach wartości własnych tej macierzy. Macierz ta jest z definicji symetryczna, posiada zatem $n$ rzeczywistych wartości własnych ${\lambda }_0⩾{\lambda }_1⩾\dots ⩾{\lambda }_{n-1}.$ W przypadku grafu regularnego ${\lambda }_0$ jest równa stopniowi grafu $d.$ Różnica $d-{\lambda }_1$ nazywana jest przerwą spektralną.

Zależności pomiędzy definicjami

Powyższe zależności są ze sobą powiązane. Oczywista jest zależność: $h_{\alpha }(G)⩾g_{\alpha }(G).$

Zależności pomiędzy ekspansją spektralną a pozostałymi zależnościami wyglądają następująco (dla grafu regularnego $G$)

$\frac{1}{2}(d-{\lambda }_1)⩽h_{1/2}(G)⩽\sqrt{2d(d-{\lambda }_1)},$

$g_{\alpha }(G)⩾\frac{1}{(1-\alpha )(\frac{{\lambda }_1}{d}{)}^2+\alpha }.$

Przykłady ekspanderów

Losowo wygenerowany graf (przez łączenie krawędziami losowych wierzchołków) z dużym prawdopodobieństwem będzie miał wysokie współczynniki ekspansji.

Znane są również deterministyczne konstrukcje ekspanderów o dobrych własnościach. Przykładem jest rodzina grafów Ramanujan, o maksymalnej możliwej przerwie spektralnej. Kombinatoryczne konstrukcje takie jak zig-zag product, pozwalają uzyskiwać w prosty sposób grafy o dużej ekspansji wierzchołkowej.