Ekspander

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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[edytuj]

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

Ekspansja wierzchołkowa[edytuj]

-ekspansja wierzchołkowa grafu to współczynnik

gdzie oznacza zbiór wszystkich sąsiadów zbioru (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 .

Ekspansja krawędziowa[edytuj]

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

gdzie oznacza zbiór krawędzi które łączą wierzchołek z z wierzchołkiem spoza .

Ekspansja spektralna[edytuj]

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 rzeczywistych wartości własnych . W przypadku grafu regularnego jest równa stopniowi grafu . Różnica nazywana jest przerwą spektralną.

Zależności pomiędzy definicjami[edytuj]

Powyższe zależności są ze sobą powiązane. Oczywista jest zależność: .

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

Przykłady ekspanderów[edytuj]

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.