¿Hay alguna propiedad gráfica que sea equivalente a que el radio espectral de su matriz de adyacencia sea menor que 111?

Dejar GRAMO sea ​​un grafo dirigido y A Sea la matriz de adyacencia correspondiente . Dejar ρ denote el radio espectral , y sea I Sea la matriz identidad .

  1. ¿Qué podemos decir sobre GRAMO cuando el radio espectral de A es menos que 1 ?

  2. ¿Hay alguna propiedad gráfica que nos muestre ese hecho? Más generalmente, ¿cuál es equivalente a él?

Sé que este es un tema de teoría de gráficos espectrales, pero no soy un experto en este campo. Conozco ese resultado clásico, que [ A k ] i j muestra el k largas caminatas desde i a j , y cuando ρ ( A ) < 1 , entonces existe ( I − A ) − 1 , y la serie de Neumann de A converge a él. Además porque A es no negativo ρ ( A ) = λ máximo sin valor absoluto, y ( I − A ) − 1 también es no negativo. Eso es todo lo que sé. ¿Hay algún resultado, que diga alguna propiedad gráfica que sea equivalente a ρ ( A ) < 1 ?

Respuestas (1)

El polinomio característico de una matriz entera es un polinomio entero mónico. El producto de los valores propios distintos de cero es, por lo tanto, igual a un número entero distinto de cero, por lo que la única forma de ρ ( A ) < 1 es que este sea un producto vacío, eso si ρ ( A ) = 0 y todos los valores propios son cero.

Esto es equivalente a la propiedad de que A es nilpotente, es decir A norte = 0 para algunos norte . Si piensa en la interpretación del "número de caminatas", esto es, a su vez, equivalente a A sin ciclos dirigidos.

@ user153012 ¿Por qué sería equivalente? Esa afirmación no es cierta, al menos según las respuestas. Sospecho que el artículo de wikipedia está confundiendo erróneamente la invertibilidad de I − A y la convergencia de la serie formal de potencias.
Quizás entonces no entendí bien la última oración de tu respuesta.
@user153012 Oh, sí, ρ ( A ) < 1 es equivalente a A sin ciclos dirigidos. Pero ninguno es equivalente a I − A siendo invertible.
Sí, tienes razón, pero creo que no es negativo. A matrices ρ ( A ) < 1 es equivalente a I − A ser invertible y ( I − A ) − 1 es no negativo. ¿Podríamos usarlo de alguna manera para ver alguna propiedad gráfica?
@ usuario153012 no es " A ¿Es acíclico" una propiedad muy gráfica?
¿Hay alguna propiedad gráfica que sea equivalente a que el radio espectral de su matriz de adyacencia sea menor que 111?
RespuestasAquíPolítica de privacidad1y, 0v