106
правок
Изменения
→Спектральное расширение
Если <tex>G</tex> является d-регулярным, возможно определение в терминах линейной алгебры на основе собственных значений матрицы смежности <tex>A = A(G)</tex> графа <tex>G</tex>, где <tex>A_{ij}</tex> — число дуг между вершинами <tex>i</tex> и <tex>j</tex>. Поскольку <tex>A</tex> является симметричной, согласно спектральной теореме, <tex>A</tex> имеет <tex>n</tex> действительных собственных значений <tex>\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_{n}</tex>. Известно, что эти значения лежат в промежутке <tex>[−d, d]</tex>.
Граф регулярен тогда и только тогда, когда вектор <tex>u\in \mathbb {R} ^{n} с u_{i}=1</tex> для всех <tex>i = 1, …, n</tex> является собственным вектором матрицы <tex>A</tex>, а его собственное число будет постоянной степенью графа. Таким образом, мы имеем <tex>Au = du</tex>, и <tex>u</tex> — собственный вектор матрицы <tex>A</tex> с собственными значениями <tex>λ1 = d</tex>, где <tex>d</tex> — степень вершин графа <tex>G</tex>. Спектральный зазор графа <tex>G</tex> определяется как <tex>d−λ2<t/extex> и является мерилом спектрального расширения графа <tex>G</tex>.
Известно, что <tex>λ_n \lambda_n = −d</tex> тогда и только тогда, когда <tex>G</tex> — двудольный. Во многих случаях, например в лемме о перемешивании, необходимо ограничить снизу не только зазор между <tex>λ1\lambda_1</tex> и <tex>λ2\lambda_2</tex>, но и зазор между <tex>λ1\lambda_1</tex> и вторым максимальным по модулю собственным значением:
<tex>// formuli\lambda=\max\{|\lambda_2|, |\lambda_{n}|\}</tex>
Поскольку это собственное значение соответствует некоторому собственному вектору, ортогональному <tex>u</tex>, его можно определить, используя отношение Рэлея:
<tex>//formulas\lambda=\max_{0\neq v\perp u} \frac{\|Av\|_2}{\|v\|_2},</tex>
gde
<tex>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1//formulas2}</tex>
— евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>.
