Expander (graf)

Expander je graf, v němž pro každou množinu vrcholů V velikosti menší než k a pro množinu V' obsahující právě sousedy vrcholů z množiny V platí, že velikost V' je větší než velikost V.

Jako ε-expander označujeme takový expander, kde |V'| ≥ (1+ε) |V|

Kategorie:Typy grafů