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 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 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 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.
Kategoria:Klasy grafów