Ekspander

Ten artykuł dotyczy grafu. Zobacz też: Ekspander - przyrząd do ćwiczeń.

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

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

${\displaystyle g_{\alpha }(G)=\min _{1\leqslant |S|\leqslant \alpha {n}}{\frac {|\Gamma (S)|}{|S|}},}$

gdzie ${\displaystyle \Gamma (S)}$ oznacza zbiór wszystkich sąsiadów zbioru ${\displaystyle 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 ${\displaystyle S.}$

Ekspansja krawędziowa

Współczynnik ekspansji krawędziowej grafu ${\displaystyle G}$ definiuje się jako:

${\displaystyle h_{\alpha }(G)=\min _{1\leqslant |S|\leqslant \alpha {n}}{\frac {|\partial (S)|}{|S|}},}$

gdzie ${\displaystyle \partial (S)}$ oznacza zbiór krawędzi które łączą wierzchołek z ${\displaystyle S}$ z wierzchołkiem spoza ${\displaystyle 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 ${\displaystyle n}$ rzeczywistych wartości własnych ${\displaystyle \lambda _{0}\geqslant \lambda _{1}\geqslant \ldots \geqslant \lambda _{n-1}.}$ W przypadku grafu regularnego ${\displaystyle \lambda _{0}}$ jest równa stopniowi grafu ${\displaystyle d.}$ Różnica ${\displaystyle 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ść: ${\displaystyle h_{\alpha }(G)\geqslant g_{\alpha }(G).}$

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

${\displaystyle {\frac {1}{2}}(d-\lambda _{1})\leqslant h_{1/2}(G)\leqslant {\sqrt {2d(d-\lambda _{1})}},}$

${\displaystyle g_{\alpha }(G)\geqslant {\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.