¿Qué es un rango bajo intuitivamente para una matriz de adyacencia?

Question

Si se tiene un grafo representado por una matriz de adyacencia, ¿qué intuitivamente en términos del gráfico original correspondería un rango bajo a un rango bajo?

Me interesa esto tanto para los grafos dirigidos como para los no dirigidos.

Esto es relevante porque el bajo rango es muy importante en técnicas comunes como la factorización de matrices no negativas y sería interesante entender qué significan los supuestos para los gráficos.

Answer 1

No estoy seguro de que tu pregunta sea fácil de responder, pero intentaré dar una intuición. No soy un experto en la factorización de matrices no negativas, así que no puedo explicar las conexiones allí.

Limitemos nuestra atención a los grafos simples y no dirigidos $G$ con $n$ vértices. Asumo que por bajo rango te refieres a bajo rango de la matriz de adyacencia. Estas propiedades se derivan de aquí Aquí hay una caracterización de los gráficos de bajo rango:

• el gráfico sin vértices es el único con rango 0
• un grafo bipartito completo es el único grafo conectado de rango 2
• un grafo tripartito completo es el único grafo conectado de rango 3

Se sabe que el rango se preserva entre subgrafos de la siguiente manera:

• si H es un subgrafo inducido de G, entonces $rank(H) \leq rank(G) $ .
• Dejemos que $G = G1 \cup G2 \cup··· \cup G_n$ , donde $G_1, G_2,...,G_n$ son componentes conectados de G, entonces $rank(G) = \sum_i^n rank(G_i)$

Dado que el gráfico completo tiene rango $n$ De ello se deduce que $largest \_clique(G) \leq rank(G)$ .

¿Cuál es el rango de un gráfico promedio? Considere este modelo simple de un gráfico aleatorio $G$ para cada par de vértices lanza una moneda justa para determinar si hay una arista entre ellos. Se ha demostrado que que con muy alta probabilidad $G$ tiene rango $n$ .

Esto me sugiere que los grafos de bajo rango son localmente dispersos o tienen una componente densamente conectada pero tienen muchos vértices aislados. Sin embargo, es probable que un gráfico elegido al azar sea de rango completo.