92
правки
Изменения
м
→Спектральное расширение
===Спектральное расширение===
Если <tex>G</tex> является [[Основные определения теории графов#Часто используемые графы|d-регулярным]], возможно определение в терминах [[Линейная алгебра 1 курсАлгебра|линейной алгебры]] на основе собственных значений [[Матрица смежности графа|матрицы смежности]] <tex>A = A(G)</tex> графа <tex>G</tex>, где <tex>A_{ij}</tex> {{---}} число дуг между вершинами <tex>i</tex> и <tex>j</tex>. Поскольку <tex>A</tex> является симметричной, согласно спектральной теореме<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B5%D0%BA%D1%82%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0]</ref>, <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}</tex> с <tex>u_{i}=1</tex> для всех <tex>i = 1 \ldots n</tex> является собственным вектором матрицы <tex>A</tex>, а его собственное число будет постоянной степенью графа. Таким образом, мы имеем <tex>Au = du</tex>, и <tex>u</tex> — собственный вектор матрицы <tex>A</tex> с собственными значениями <tex>\lambda_{1} = d</tex>, где <tex>d</tex> — степень вершин графа <tex>G</tex>. Спектральный зазор графа <tex>G</tex> определяется как <tex>d-\lambda_{2}</tex> и является мерилом спектрального расширения графа <tex>G</tex>.
Известно, что <tex>\lambda_{n} = -d</tex> тогда и только тогда, когда <tex>G</tex> {{---}} [[Двудольные графы|двудольный]]. Во многих случаях, например в [[Графы-экспандеры#Лемма о перемешивании|лемме о перемешивании]], необходимо ограничить снизу не только зазор между <tex>\lambda_{1}</tex> и <tex>\lambda_{2}</tex>, но и зазор между <tex>\lambda_{1}</tex> и вторым максимальным по модулю собственным значением:
<tex>\lambda=\max\{|\lambda_{2}|, |\lambda_{n}|\}</tex>
Поскольку это собственное значение соответствует некоторому собственному вектору, ортогональному <tex>u</tex>, его можно определить, используя отношение Рэлея:
<tex>\lambda=\max\limits_{0\neq v\perp u} \fraccfrac{\|Av\|_2}{\|v\|_2},</tex>
где
{{---}} евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>.
Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\tfrac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>-1</tex> и <tex>1</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения [[Матрица Кирхгофа|матрицы Кирхгофа]]. Для направленного графа используются сингулярные значения матрицы сопряжения A, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</tex>.
==Конструирование==
