Este es un seguimiento a una pregunta anterior. Lo gráficos tienen incidencia matrices de rango completo?
Obvio que los miembros de la clase: completa los gráficos.
Obvio contraejemplos: Gráfico con más de dos vértices, pero sólo uno de los bordes.
Estoy tentado a suponer que la respuesta es los gráficos que contienen árboles de expansión como subdiagramas. Sin embargo, no he pensado mucho en esto.
La primera respuesta que se identifica "incidencia de la matriz" con la "matriz de adyacencia". El último es el los vértices por los vértices de la matriz que Sciriha escribe. Pero la pregunta original aparece la preocupación de la incidencia de la matriz, que es vértices por los bordes. La precisa la respuesta es la siguiente.
Teorema: Las filas de la matriz de incidencia de un grafo son linealmente independientes sobre los reales si y solo si no hay ningún componente conectado es bipartito.
Prueba. Algunos de los pasos que se deja para el lector :-)
Nota: primero que la suma de las filas indexado por los vértices en una clase de color de un bipartito componente es igual a la suma de las filas indexados por la otra clase de color. Por lo tanto, si algún componente es bipartito, las filas de la matriz de incidencia son linealmente dependientes.
Por el contrario, tenemos que demostrar que la incidencia de la matriz de conexión de un no-bipartita gráfica tiene rango completo. Seleccione un árbol de expansión TT de nuestro gráfico de G. Desde G no es bipartito, hay una ventaja e G de manera tal que el subgrafo H formado por T e no es bipartito.
El truco es mostrar que las columnas de la incidencia de la matriz indexada por los bordes de H forma una matriz invertible. Vemos que H está integrado por "la plantación de árboles en un extraño ciclo". Completamos la prueba por inducción sobre el número de aristas no en el ciclo.
El caso base es al H es un extraño ciclo. Es fácil demostrar que la incidencia de la matriz es invertible. De lo contrario existe un vértice de valencia uno, x decir, que H∖x está conectado y no bipartito. A continuación, la incidencia de la matriz de H∖x es invertible y, de nuevo, es fácil ver esto implica que la incidencia de la matriz de H es invertible.
Comentario: yo no conozco el primero que escribió este resultado. Es viejo, y es redescubierto a intervalos regulares.
Un interesante ejemplo de una clase de gráficos para el que no se sabe para cuando la adyacencia de la matriz A tiene rango completo es el de los diagramas de Hasse de las celosías L(k,j). Consulte las páginas 21 y 22 de arXiv:matemáticas/0501230. Lo que hace este interesante es que explícita fórmulas trigonométricas son conocidos por los autovalores de a A y sus multiplicidades, pero no está claro a partir de estas fórmulas si hay un cero autovalor positivo de la multiplicidad.
Como Chris señaló, esta respuesta está fuera de la marca. Los gráficos con matrices de adyacencia (no de la incidencia de las matrices) de los no-rango completo se llama singular gráficos. Parece que es un conocido y difícil problema abierto a las caracterizan. Ver este documento por Sciriha.
Creo que puedo encontrar un gráfico con un árbol de expansión que no tiene una matriz de adyacencia de rango completo. Empezar con un camino de longitud cinco participar en el primer punto de la cuarta y la quinta dos el secod. A continuación, el primero y el quinto va a tener el mismo adyacencia fila y que va a ser una dependencia y que será un gráfico con un árbol de expansión que no tiene rango completo. Sin embargo, la pregunta no es acerca de las matrices de adyacencia pero la incidencia de las matrices. Sin embargo, desde cualquier gráfico con la conexión de un bipartito componente no tiene una incidencia matriz de rango completo como se señaló en otro post podemos tomar cualquier conectados árbol y que el gráfico se tiene un árbol de expansión y tendrá bipartito componente por lo que no tendrá un singular matriz de rango completo.
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.
