Como se ha mostrado anteriormente, la forma de demostrar el rango de la matriz de incidencia es $V-1$ ? En primer lugar, deduzco que la matriz de incidencia de un dígrafo tendrá 1 o -1 (y también cero) en cada columna (que son aristas). Luego, a partir de este hecho, demuestro que los vectores columna en $M$ son linealmente dependientes, por lo que, el rango $M < V$ y por lo tanto, el rango $M \leq V-1$ . Pero de repente me doy cuenta de que el dígrafo sólo está "conectado". Es posible que exista una arista que sólo se conecte a un vértice. Entonces la prueba y la lógica anteriores son erróneas. Sólo se pueden utilizar en un dígrafo si contiene un "ciclo". ¿Es el caso? ¿Cómo se puede ir más allá de esta pregunta?
Respuesta
¿Demasiados anuncios?
Tienes razón en que la dependencia lineal entre las columnas de las matrices de incidencia proviene de los ciclos. Sin embargo, una dependencia lineal entre columnas no es lo que buscas, de todos modos. El número de columnas es $E$ el número de aristas; si las columnas son linealmente dependientes, entonces el rango es menor que $E$ sin embargo, $E$ puede ser mucho mayor que $V$ Así que esto no ayuda necesariamente.
En cambio, debería buscar una dependencia lineal entre las filas de la matriz de incidencia. Por defecto, el rango de la matriz es como máximo $V$ el número de vértices (y por tanto el número de filas). Si se encuentra una dependencia entre las filas, entonces el rango de la matriz es como máximo $V-1$ .
Para empezar, hay que observar que la suma de las filas de la matriz de incidencia es $0$ . Esto garantiza que la matriz es tiene rango como máximo $V-1$ . Entonces, convénzase de que en un gráfico conectado, ésta es la única dependencia lineal entre las filas.
