Ekspander

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Ujednoznacznienie Ten artykuł dotyczy grafu. Zobacz też: Ekspander - przyrząd do ćwiczeń.

W teorii grafów, ekspander oznacza 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[edytuj | edytuj kod]

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

Ekspansja wierzchołkowa[edytuj | edytuj kod]

\alpha-ekspansja wierzchołkowa grafu to współczynnik

g_\alpha(G) = \min_{1 \le |S|\le \alpha{n}} \frac{|\Gamma(S)|}{|S|}

gdzie \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[edytuj | edytuj kod]

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

h_\alpha(G) = \min_{1 \le |S|\le \alpha{n} } \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[edytuj | edytuj kod]

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 \ge \lambda_1 \ge \ldots \ge \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[edytuj | edytuj kod]

Powyższe zależności są ze sobą powiązane. Oczywista jest zależność: h_\alpha(G) \ge 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) \le h_{1/2}(G) \le \sqrt{2d(d - \lambda_1)}
g_\alpha(G) \ge \frac{1}{(1-\alpha)(\frac{\lambda_1}{d})^2+\alpha}

Przykłady ekspanderów[edytuj | edytuj kod]

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.