Gráfica conectada, cada matriz de poder de adyacencia tiene ceros.

Question

Me podrían ayudar con lo siguiente?

Encontrar un grafo conexo para que cada una de las matrices de $A^{k}_{G}, \ k \ge 0$ contiene $0$s.

Y otro:

Demostrar que un grafo es conectado si y sólo si $(I+A_{G})^{n}$ no contiene $0$s $n$s lo suficientemente grande.

Sé que en una matriz de $A^{k}_{G} \ \ a_{ij}^{k}$ es el número de los paseos de longitud k de$v_{i}$$v_{j}$. Y si multiplicamos las matrices que son simplemente una concatenación de paseos. Pero no sé cómo (o si) podemos usar probar la primera.

En cuanto a la segunda, estoy totalmente en pérdida.

Answer 1

SUGERENCIA: Para la primera pregunta, considere la gráfica con dos vértices y aristas. Más generalmente, considere la posibilidad de cualquier gráfico bipartito. El punto es que un paseo con extremos en diferentes conjuntos de vértices tiene longitud impar, mientras que un paseo con termina en el mismo vértice tiene longitud.

Una dirección de la segunda pregunta es fácil. En el otro sentido, supongamos que $G$ está conectado. Entonces existe un entero positivo $m$ tal que para cualquier par de vértices $u$ $v$ $G$ hay un paseo de $u$ $v$de la longitud en la mayoría de las $m$. Mostrar que $(I+A_G)^n$ no tiene ceros si $n\ge m$. La clave es mostrar que el $(i,j)$ entrada en $(I+A_G)^n$ es el número de caminos de longitud en la mayoría de las $n$ $v_i$ $v_j$. Pruebe primero para $n=2$; tratar de ver por qué la $1$'s de la diagonal principal de a $I+A_G$ corresponden a pie en lugar de en un vértice de un 'paso' en lugar de la que realmente mueve a otro vértice.

Answer 2

Sugerencia: cada potencia$k$ le da el número de rutas de$k$ legnths entre vértices$i,j$ para la entrada de la matriz$a_{ij}$. Puede pensar en gráficos que restrinjan algún tipo de rutas, por ejemplo, gráficos bipartitos: dos vértices del mismo conjunto solo pueden tener rutas de longitud uniforme, y dos de conjuntos diferentes solo pueden tener rutas de longitudes impares ...