Hola de nuevo a todos,
Estoy leyendo Fan Chung monografía Espectral de la Teoría de grafos. En ella, tiene dos fórmulas para el mínimo autovalor de un gráfico. Ella no explica por qué son equivalentes, y estoy teniendo dificultades para que la justifican. A continuación, voy a explicar todo y mi pregunta precisamente.
Deje $G=(V,E)$ un gráfico y deje $d_v$ denotar el grado de $v\in V$. Deje $T$ denotar la matriz diagonal cuyas $(v,v)^{\text{th}}$ entrada $d_v$. El Laplaciano $\mathcal{L}$ $G$ es la matriz definida por $$ \mathcal{L}_{i,j} := \Bigg\{ \begin{array}{cc} 1 & \text{if } u=v \\ -1/\sqrt{d_v d_u} & \text{if } \{u,v\} \in E \\ 0 & \text{otherwise} \end{array} $$ Los autovalores $\lambda_0 \leq \lambda_1 \leq \dots \leq \lambda_{n-1}$ $\mathcal{L}$ son llamados los autovalores de a $G$. Ya que no es demasiado duro para demostrar que $0=\lambda_0$ para cada gráfico, llamamos a $\lambda_1$ el mínimo autovalor de a $G$.
Desde $\mathcal{L}$ es Hermitian, sus autovalores son todos no negativos reales y el mínimo autovalor es determinada por la de Rayleigh-Ritz ratio (ver, por ejemplo, el Teorema 4.2.2 de Horn & Johnson): $$ \lambda_1 = \min \frac{\langle g,\mathcal{L}g \rangle}{\langle g,g\rangle} $$ Aquí el mínimo se toma sobre todos los $g : V\rightarrow \mathbb{R}$ no idéntica a $0$, lo que nosotros consideramos como la longitud de la-$V$% real vectores. Con algunos manipulación algebraica de que la relación se convierte en $$ \lambda_1 = \inf \frac{\sum_{\{u,v\}\in E} (f(u)-f(v))^2}{\sum_v f(v)^2d_v} $$ donde $g=T^{-1/2} f$ y el infimum se toma sobre todas las funciones de $f$ tal que $f \bot T1$ donde $1$ es$1$ vector.
Que fórmula tiene sentido, creo. Sin embargo, más adelante (en la prueba del teorema 2.2) afirma que $$ \lambda_1 = \frac{\sum_{v \en V_+} f(v) \sum_{\{u,v\}\en E_+} (f(v)-f(u))}{\sum_{v\en V_+} f^2(v) d_v} $$ donde$V_+ := \{ v : f(v) \geq 0\}$$E_+ := \{ \{u,v\} \in E : u \text { or } v \in V_+\}$.
No puedo entender por qué estas dos fórmulas para $\lambda_1$ son equivalentes. Chung silencio sobre este punto puede ser debido a que la equivalencia es obvio. Pero alguien podría arrojar luz sobre esto para mí?
