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> является симметричной, согласно спектральной теореме, <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> и вторым максимальным по модулю собственным значением:
