Demostrar que un fuertemente conectado dígrafo tiene un irreductible de la matriz de adyacencia?

Question

En nuestra tarea se pide demostrar esta realidad. Si alguien estaría dispuesto a dar un consejo yo estaría muy agradecido.

Gracias

Answer 1

Supongo que usted está usando la siguiente definición:

La matriz $A$ es irreducible si no es reducible.

En tal caso, se asume que la matriz es reducible, que es el espacio de estado de la gráfica permite la descomposición $V = V_1\cup V_2$ donde establece $V_1$ $V_2$ son disjuntas y $$ a_{ij} = 0 \etiqueta{1} $$ para todos los $i\in V_1$$j\in V_2$. Desde $V$ está fuertemente conectado, existe un camino de $i_1i_2\dots i_n$ donde $i_1$ es algún punto en $V_1$ $i_2$ es algún punto en $V_2$. Mostrar que contradice $(1)$.

Answer 2

Sugerencia:

Suponga que la matriz es reducible, vamos a $V_1, V_2, \ldots, V_k$ ser los vértices que forman los bloques en la forma reducida de la matriz (es decir, es triangular superior con respecto a los bloques). Demostrar que no existe ninguna arista $v_{k+l}\to v_k$ $v_k \in V_k$ $v_{k+l} \in V_{k+l}$ mediante la observación de que el número en la matriz es 0 (cero).

Buena suerte!