5 votos

¿Un grafo regular conexo tiene k bucles?

Supongamos que $A$ es una orden- $n$ matriz de ceros y unos tal que $A^2 = J$ la matriz de todos los unos. Demuestre que $A$ tiene exactamente $k$ a lo largo de la diagonal, donde $k^2 = n$ .

Puedo demostrar que $AJ=JA=kJ$ en términos de teoría de grafos, $A$ es un grafo regular de orden $k$ . Y $A$ está conectado, o bien $A^2$ tendría ceros. Me pregunto si existe un teorema que pueda establecer que la gráfica tiene exactamente $k$ ¿bucle? O quizá sea más obvio desde una perspectiva matricial.

Sé que la regularidad y la conectividad por sí solas no son suficientes, ya que por ejemplo la matriz

$$A_\varnothing=\begin{bmatrix}1& & &1\\ &1&1& \\1& &1& \\&1&&1\end{bmatrix}$$

est $k$ -regular y conectado, pero no satisface $A_\varnothing^2 = J$ y no tiene $k$ a lo largo de la diagonal.

Un ejemplo hace exhibir esta propiedad es

$$A_\checkmark = \begin{bmatrix}1&1&&\\&&1&1\\1&1&&\\&&1&1\end{bmatrix}$$

0 votos

¿Y si $n$ no es un entero cuadrado?

0 votos

Entonces creo que la condición $A^2 = J$ es imposible de satisfacer.

0 votos

En $ij$ entrada de $A^{2}$ representa el número de paseos de longitud 2 entre vértices $v_{i}$ y $v_{j}$ . Como no supones que tu matriz sea simétrica, estás trabajando con digrafos. ¿Qué puedes decir de un vértice que no tiene un bucle?

3voto

user326210 Puntos 26

He descubierto que puedo demostrarlo como un teorema utilizando propiedades de los valores propios.

El truco está en que para una matriz de ceros y unos, el número de unos a lo largo de la diagonal es igual a la suma de los valores a lo largo de la diagonal (la traza de la matriz). Pero la traza de una matriz también es igual a la suma de sus valores propios (generalizados). Por lo tanto, basta con demostrar que $A$ tiene valores propios generalizados $0$ (con multiplicidad $n-1$ ) y $k$ (con multiplicidad 1).

Un aspecto positivo de este enfoque es que se generaliza a potencias mayores de $A$ y a matrices cuyas entradas no son sólo ceros y unos:

Sea $r$ sea un número entero positivo y $A$ ser cualquier $n\times n$ tal que $A^r = J$ . Entonces :

  • Cada fila y columna de $A$ suma a $k \equiv n^{1/r}$ .
  • El rastro de $A$ es igual a $k$ .

En detalle:

  1. Se nos da que $A^2 = J$ .
  2. A partir de aquí podemos demostrar que $AJ = JA = kJ$ para algún valor escalar $k$ . [Ver prueba más abajo.]
  3. Observando una sola columna de $AJ = kJ$ encontramos que el vector de unos es un vector propio de $A$ con valor propio $k$ .
  4. Combinación de $A^2 = J$ y $AJ = kJ$ obtenemos $A^3 = kA^2$ . Esto nos permite reescribir todas las potencias superiores de $A$ en términos de $A^2$ .
  5. Utilización de la regla de reescritura $A^3 = kA^2$ encontramos que los valores propios generalizados de $A$ son $k$ (con multiplicidad 1) y 0 (con multiplicidad $n-1$ ). [Véase la prueba más adelante].
  6. La traza de una matriz es la suma de sus valores propios generalizados; por tanto, la traza de $A$ es sólo $k+0+0+\ldots+0 = k$ .
  7. La traza de una matriz de ceros y unos es igual al número de unos a lo largo de la diagonal. Por lo tanto, hay exactamente $k$ a lo largo de la diagonal (exactamente $k$ vértices con bucles); QED.

Prueba de (2) observamos que la matriz $J$ calcula las sumas de columna/fila de una matriz: Para cualquier orden $n$ matriz $M$ , dejemos que $r_1, \ldots, r_n$ sean sus sumas de filas. Nótese que por las reglas de multiplicación de matrices, $MJ$ i $$MJ = \begin{bmatrix}r_1 & r_1 & \ldots & r_1\\r_2 & r_2 & \ldots & r_2\\\vdots & \vdots & &\vdots\\ r_n & r_n & \ldots & r_n\\\end{bmatrix}$$ y de forma similar $JM$ es la matriz de sumas de columnas.

Si $A^2 = J$ por hipótesis, entonces $A^3 = AJ = JA$ . Pero $AJ$ es la matriz de sumas de filas de $A$ y $JA$ es la matriz de sumas de columnas de $A$ . Si son iguales, entonces cada fila y columna de $A$ deben tener la misma suma- llámalo $k$ .

En consecuencia, $AJ = JA = kJ$ (la matriz en la que cada entrada es $k$ .)

Como corolario, podemos demostrar que $k^2 = n$ (el orden de la matriz) porque $J^2 = nJ$ (las sumas de filas de $J$ son todos $n$ ) y $J^2 = JA^2 = (JA)A = kJA = k(JA) = k(kJ) = k^2J$ Así que $nJ = k^2 J$ lo que significa que $k^2 = n$ .

Prueba de (5) : La fórmula generalizada de los valores propios est $$(A - \lambda I)^n v = 0.$$

A partir de (3), sabemos que $k$ es un valor propio y, por tanto, un valor propio generalizado. Si $n=1$ este debe ser el único valor propio y hemos terminado. De lo contrario, vamos a demostrar que 0 es otro valor propio generalizado y que tiene multiplicidad $n-1$ . Porque hay exactamente $n$ valores propios generalizados, podemos concluir que 0 es el sólo otro valor propio, y que $k$ tiene multiplicidad 1.

Considerando el valor propio $\lambda = 0$ la ecuación generalizada de valores propios se reduce a $A^n = 0$ . Pero porque $A^2 = J$ implica que $A^3 = kA^2$ podemos demostrar por inducción que $A^{r+2} = k^r A^2$ para números enteros $r \geq 0$ . Por lo tanto $A^n = k^{n-2} A^2 = k^{n-2} J$ . (Nota: $n>2$ porque $n$ es un cuadrado perfecto y estamos considerando sólo el caso $n>1$ .)

Por lo tanto, los vectores propios generalizados de $A$ con valor propio 0 son vectores $v$ tal que $$k^{n-2} J v = 0$$ o, eliminando la constante positiva $k^{n-2}$ , sólo $$Jv = 0.$$

Pero $Jv$ devuelve un vector en el que cada entrada es la suma de las entradas de $v$ :

$$Jv = (\sum_i v_i)\begin{bmatrix}1\\1\\\vdots \\ 1\end{bmatrix}$$

así que $J$ envía a cero sólo aquellos vectores cuyas entradas suman cero. El conjunto de todos estos vectores suma cero es un subespacio de dimensión $n-1$ por lo que hemos demostrado que $0$ es un valor propio generalizado de $A$ con multiplicidad algebraica $n-1$ .

Porque $k$ es un valor propio de $A$ y hay exactamente $n$ valores propios generalizados, se deduce que $k$ es el único otro valor propio generalizado y que tiene multiplicidad 1. Q.E.D.

0 votos

¿Quieres decir que $k$ es el único distinto de cero ¿Valor propio?

0 votos

Sí, lo he dicho en el punto (7) y creo que he demostrado que es cierto.

0 votos

Pero al principio dices que $A$ tiene exactamente un valor propio; pero en realidad $A$ tendrá exactamente 2 valores propios, $k$ y $0$ . Ahora veo que lo dice correctamente en el punto (7).

1voto

Morgan Rodgers Puntos 3629

Es poco probable que encuentres un teorema que diga esto, sólo tienes que argumentar combinatoriamente.

En primer lugar, si $G$ est $k$ -regular, y tenemos un vértice $v$ con un bucle, entonces el número de vértices de $G$ viene dada por $1+(k-1)+(k-1)k) = k^{2}$ ( $v$ vértices con una arista de salida de $v$ , vértices con una arista de salida de uno de los conjuntos anteriores; todos ellos son distintos porque de lo contrario habría dos caminos). Por lo tanto $n=k^{2}$ .

Consideremos los vértices con bucles; no puede haber aristas entre estos vértices porque eso daría dos paseos de longitud 2 entre ellos (bucle luego arista, o arista luego bucle). Por tanto, si fijamos un vértice $v$ con un bucle, entonces hay $(k-1)$ vértices sin bucles en su conjunto de salida. Cualquier otro vértice $v^{\prime}$ con un bucle debe estar a una distancia 2 de $v$ por lo que debe haber un $w$ en el conjunto de $v$ con un borde exterior a $v^{\prime}$ . Pero sólo debe haber un camino de longitud 2 desde $v$ à $v^{\prime}$ así que $w$ es única. Esto nos dice que puede haber como máximo $k-1$ vértices distintos de $v$ con bucles, lo que da un total de como máximo $k$ vértices con bucles.

Le dejo a usted la tarea de demostrar que la igualdad se cumple realmente.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X