92
правки
Изменения
м
'''Граф-экспандер''' (или расширяющийся граф, англ. ''expander graph'') {{---}} в комбинаторике сильно разреженный [[Основные определения теории графов#Ориентированные графы|граф]], при этом связность определяется по вершинам, дугам или спектру. Это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность. Различные формализации этих понятий дают различные типы экспандеров: [[Графы-экспандеры#Реберное расширение|рёберный расширитель]], [[Графы-экспандеры#Вершинное расширение|вершинный расширитель]], и [[Графы-экспандеры#Спектральное расширение|спектральный расширитель]].
Нет описания правки
'''Замечание:''' Несвязный [[Основные определения теории графов#Ориентированные графы|граф]] не является экспандером. Любой связный граф является экспандером, однако различные связные графы имеют различные параметры расширителя. [[Основные определения теории графов#Часто используемые графы|Полный граф]] имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.
