Muestran que un gráfico $G$ limitados con vértices de $n$ $d$-regular si, y sólo si el vector con las coordenadas es igual a 1 es eigenvetor del valor propio $λ = d$ de la % de la matriz de adyacencia $A$del gráfico $G$. La pregunta sí mismo era un poco confuso para mí...
Respuestas
¿Demasiados anuncios?
DiGi
Puntos
1925
Supongamos que $G$ $d$- regular. A continuación, cada vértice de $G$ es adyacente a $d$ otros vértices, de modo que cada fila de la matriz de adyacencia $A$ tendrá $d$ $1$'s y $n-d$ $0$'s. Vamos
$$A=\pmatrix{a_{11}&a_{12}&\dots&a_{1n}\\ a_{21}&a_{22}&\dots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\dots&a_{nn}}\;,$$
y $\vec v$ $n\times 1$ vector cuyas entradas son todas las $1$:
$$\vec v=\pmatrix{1\\1\\\vdots\\1}\;.$$
El producto $\vec u=A\vec v$ $n\times 1$ vector cuyas $i$-ésima es $$u_i=\sum_{j=1}^na_{ij}\cdot1=a_{i1}+a_{i2}+\ldots+a_{in}\;.$$ Since $d$ of the numbers $a_{i1},\dots,a_{en}$ are $1$ and the rest are $0$, $u_i=d$ for every $i$. Thus, $$\vec u=\pmatrix{d\\d\\\vdots\\d}=d\vec v\;.$$ That is, $Un\vec v=d\vec v$, so by definition $\vec v$ is an eigenvector of $$ for the eigenvalue $d$.
Para mostrar la otra dirección, usted puede tratar de revertir este argumento; que funciona. Alternativamente, usted puede asumir que $G$ no $d$-regular y demostrar que $\vec v$ es no un vector propio para un autovalor $d$; que también funciona y puede ser incluso más fácil.
Lo curioso, acabo de enterarme de esto por mí mismo esta semana. Es la proposición 3 de la página 2 de estas excelentes notas de la conferencia por Padraic Bartlett. El conjunto de notas de la conferencia en el gráfico espectral teoría está aquí.
(Prometí en el 2012 a escribir la prueba aquí, pero yo, por la presente se retracte de esa promesa. Yo no sería capaz de mejorar Brian Scott valoración crítica en otros lugares en este hilo.)
