Изменения

Перейти к: навигация, поиск

Графы-экспандеры

20 байт добавлено, 19:44, 21 декабря 2017
м
Спектральное расширение
где
<tex>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{\tfrac{1/}{2}}</tex>
{{---}} евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>.
Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\frac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>-1</tex> и <tex>1</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения [[Матрица Кирхгофа|матрицы Кирхгофа]]. Для направленного графа используются сингулярные значения матрицы сопряжения <tex>A</tex>, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</tex>.
==Конструирование==
92
правки

Навигация