En comparación con los espectros de gráficos no dirigidos, que corresponden a matrices simétricas, los espectros de gráficos dirigidos no son muy conocidos:
Se sabe que un gráfico dirigido tiene una matriz de adyacencia cuyos valores propios son binarios si es a-cíclico. Esto se sigue por la clasificación de los vértices en componentes fuertemente conectados: Esto fija una enumeración de los vértices tal que el acuerdo Laplaciano permutada a este ordenamiento es triangular superior con entradas.
Pero lo que se sabe si es el otro extremo, es decir, es un gráfico fuertemente conectado en vértices, lo que significa que hay un camino dirigido entre cualquier par de vértices.
Generalmente, uno necesitaría calcular el polinomio característico de y calcular sus raíces. A pesar de que es una matriz , esto parece una tarea desalentadora. En particular, las raíces de este polinomio son en general números complejos.
El teorema de Perron-Frobenius implica que al menos el valor propio superior es real y simple, pero no revela información sobre el resto de los valores propios.
Sin embargo, ¿qué pasa si solo nos interesan los límites muy débiles de la siguiente forma:
: Sea un gráfico dirigido sobre vértices. Entonces, o bien todos los valores propios de son reales, o existe al menos un valor propio tal que .
¿Estos límites siguen trivialmente de los teoremas conocidos? Alternativamente, ¿puede un gráfico dirigido tener un valor propio con un componente imaginario exponencialmente pequeño?
Respuestas:
La respuesta a "alternativamente, puede una gráfica dirigida tener un valor propio con un componente imaginario exponencialmente pequeño" es SÍ (aunque no entiendo qué es "alternativa" acerca de esta declaración, ya que de ninguna manera refuta la conjetura).
Schönhage [1] enumera varios ejemplos de polinomios con separación de raíces exponencialmente pequeña, en particular la familia de polinomios atribuidos a Mignotte [ 2] (que no puedo verificar ya que no tengo acceso a él en este momento). Ahora, estos polinomios tienen cada uno un par de raíces reales cerca de en una distancia , mientras que necesitamos un par de raíces complejas . Sin embargo, esto se logra fácilmente modificando ligeramente el polinomio: sea Claramente, este polinomio no tiene raíz real positiva (y tampoco tiene raíz real negativa si
Finalmente, los valores propios de se incluyen entre los valores propios del gráfico dirigido no ponderado en vértices con bordes e para ; y para ; , ; y , , , paraG0 G1 2n+6
Referencias
[1] A. Schönhage, Ejemplos de separación de raíces polinomiales , Journal of Symbolic Computation 41 (2006), no. 10, págs. 1080-1090, doi: 10.1016 / j.jsc.2006.06.003 .
[2] M. Mignotte, Algunos límites útiles , en: Buchberger, Collins, Loos (eds.), Computer Algebra: Symbolic and Algebraic Computation, 2nd ed., Springer-Verlag, 1983, pp. 259–263, doi: 10.1007 / 978-3-7091-7551-4_16 .
fuente
Siento que los límites dependerán en gran medida de la estructura de conectividad particular del gráfico.
Un ejemplo sería un ciclo de una sola vía de longitud . Con el orden correcto, no es difícil ver que , por lo que los valores propios son todos los raíces-ésima de la unidad, es decir, con yendo de a .A ( G ) N - I = 0 N e 2 π i n / N n 0 N - 1N A(G)N−I=0 N e2πin/N n 0 N−1
Incluso para , tiene garantizados algunos valores propios puramente imaginarios y .i - iN i −i
Ahora, por otro lado, fui a Wolframalpha y conecté el gráfico completo de tamaño 4, luego eliminé un solo borde. El gráfico resultante tiene valores propios puramente reales (a pesar de no tener una matriz de adyacencia simétrica; sí, eso puede suceder). Lo que me dice que no hay una declaración general.
fuente