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