Matriz de adyacencia

Compartir Imprimir Citar

En teoría de grafos e informática, una matriz de adyacencia es una matriz cuadrada utilizada para representar un gráfico finito. Los elementos de la matriz indican si los pares de vértices son adyacentes o no en el gráfico.

En el caso especial de un gráfico simple finito, la matriz de adyacencia es una matriz (0,1) con ceros en su diagonal. Si el gráfico no está dirigido (es decir, todos sus bordes son bidireccionales), la matriz de adyacencia es simétrica. La relación entre un gráfico y los valores propios y los vectores propios de su matriz de adyacencia se estudia en la teoría de gráficos espectrales.

La matriz de adyacencia de un grafo debe distinguirse de su matriz de incidencia, una representación de matriz diferente cuyos elementos indican si los pares vértice-arista son incidentes o no, y su matriz de grado, que contiene información sobre el grado de cada vértice.

Definición

Para un gráfico simple con el conjunto de vértices U = { u ₁, …, u _n }, la matriz de adyacencia es una matriz A cuadrada n × n tal que su elemento A _ij es uno cuando hay un borde desde el vértice u _i hasta el vértice u _j, y cero cuando no hay arista. Los elementos diagonales de la matriz son todos cero, ya que los bordes de un vértice a sí mismo (bucles) no están permitidos en gráficos simples. A veces también es útil en la teoría de gráficos algebraicos para reemplazar los elementos distintos de cero con variables algebraicas.El mismo concepto se puede extender a multigrafos y gráficos con bucles almacenando el número de aristas entre cada dos vértices en el elemento de matriz correspondiente y permitiendo elementos diagonales distintos de cero. Los bucles se pueden contar una vez (como un solo borde) o dos veces (como dos incidencias de vértice-arista), siempre que se siga una convención consistente. Los gráficos no dirigidos a menudo usan la última convención de contar bucles dos veces, mientras que los gráficos dirigidos suelen usar la primera convención.

De un grafo bipartito

La matriz de adyacencia A de un grafo bipartito cuyas dos partes tienen r y s vértices se puede escribir de la forma ${displaystyle A={begin{pmatrix}0_{r,r}&B\B^{mathsf {T}}&0_{s,s}end{pmatrix}},}$

donde B es una matriz r × s, y 0 _{r, r} y 0 _{s, s} representan las matrices cero r × r y s × s. En este caso, la matriz B más pequeña representa de manera única el gráfico y las partes restantes de A pueden descartarse como redundantes. B a veces se llama la matriz de biadyacencia.

Formalmente, sea G = (U, V, E) un grafo bipartito con partes U = { u ₁, …, u _r }, V = { v ₁, …, v _s } y aristas E. La matriz de biadyacencia es la matriz B r × s 0–1 en la que b _i_,_j = 1 si y sólo si (u _i, v _j) ∈ E.

Si G es un multigrafo bipartito o un grafo ponderado, entonces los elementos b _{i, j} se toman como el número de aristas entre los vértices o el peso de la arista (u _i, v _j), respectivamente.

Variaciones

Una (a, b, c) -matriz A de adyacencia de un grafo simple tiene A _{i, j} = a si (i, j) es una arista, b si no lo es, y c en la diagonal. La matriz de adyacencia de Seidel es una matriz de adyacencia (−1, 1, 0). Esta matriz se utiliza para estudiar grafos fuertemente regulares y dos grafos.

La matriz de distancia tiene en posición (i, j) la distancia entre los vértices v _i y v _j. La distancia es la longitud de un camino más corto que conecta los vértices. A menos que se proporcionen explícitamente las longitudes de los bordes, la longitud de un camino es el número de bordes en él. La matriz de distancia se parece a una potencia alta de la matriz de adyacencia, pero en lugar de decir solo si dos vértices están conectados o no (es decir, la matriz de conexión, que contiene valores booleanos), da la distancia exacta entre ellos.

Ejemplos

Gráficos no dirigidos

La convención que se sigue aquí (para gráficos no dirigidos) es que cada arista suma 1 a la celda correspondiente de la matriz, y cada ciclo suma 2. Esto permite encontrar fácilmente el grado de un vértice tomando la suma de los valores en cualquiera de sus respectiva fila o columna en la matriz de adyacencia.

{displaystyle {begin{pmatrix}2&1&0&0&1&0\1&0&1&0&0\end{pmatrix}}}

Gráfico etiquetado	Matriz de adyacencia
	${displaystyle {begin{pmatrix}2&1&0&0&1&0\1&0&1&0&0\end{pmatrix}}}$ Las coordenadas son 1–6.
Gráfico de Nauru	Las coordenadas son 0–23.Los campos blancos son ceros, los campos coloreados son unos.

Grafos dirigidos

La matriz de adyacencia de un gráfico dirigido puede ser asimétrica. Uno puede definir la matriz de adyacencia de un gráfico dirigido de tal manera que

un elemento distinto de cero A _ij indica un borde de i a j o
indica un borde de j a i.

La primera definición se usa comúnmente en teoría de grafos y análisis de redes sociales (por ejemplo, sociología, ciencias políticas, economía, psicología). Este último es más común en otras ciencias aplicadas (p. ej., sistemas dinámicos, física, ciencia de redes) donde A se usa a veces para describir dinámicas lineales en gráficos.

Usando la primera definición, los grados de entrada de un vértice se pueden calcular sumando las entradas de la columna correspondiente y el grado de salida del vértice sumando las entradas de la fila correspondiente. Cuando se usa la segunda definición, el grado de entrada de un vértice viene dado por la suma de la fila correspondiente y el grado de salida viene dado por la suma de la columna correspondiente.

Gráfico etiquetado	Matriz de adyacencia
Gráfico de Cayley dirigido de S ₄	Las coordenadas son 0–23.Como se dirige el gráfico, la matriz no es necesariamente simétrica.

Gráficos triviales

La matriz de adyacencia de un gráfico completo contiene todos los unos excepto a lo largo de la diagonal donde solo hay ceros. La matriz de adyacencia de un gráfico vacío es una matriz cero.

Propiedades

Espectro

La matriz de adyacencia de un gráfico simple no dirigido es simétrica y, por lo tanto, tiene un conjunto completo de valores propios reales y una base de vector propio ortogonal. El conjunto de valores propios de un gráfico es el espectro del gráfico. Es común denotar los valores propios por ${ estilo de visualización lambda _ {1} geq lambda _ {2} geq cdots geq lambda _ {n}.}$

El mayor valor propio $lambda _{1}$ está acotado arriba por el grado máximo. Esto se puede ver como resultado del teorema de Perron-Frobenius, pero se puede probar fácilmente. Sea v un vector propio asociado a $lambda _{1}$ y x el componente en el que v tiene el máximo valor absoluto. Sin pérdida de generalidad suponga que v _x es positivo ya que de lo contrario simplemente toma el vector propio $-v$ , también asociado a $lambda _{1}$ . Después ${displaystyle lambda_{1}v_{x}=(Av)_{x}=sum_{y=1}^{n}A_{x,y}v_{y}leq sum_{ y=1}^{n}A_{x,y}v_{x}=v_{x}grado(x).}$

Para grafos d -regulares, d es el primer valor propio de A para el vector v = (1, …, 1) (es fácil comprobar que es un valor propio y es el máximo debido a la cota anterior). La multiplicidad de este valor propio es el número de componentes conexas de G, en particular ${ estilo de visualización lambda _ {1}> lambda _ {2}}$ para grafos conexos. Se puede demostrar que para cada valor propio $lambda _{i}$ , su opuesto ${ estilo de visualización - lambda _ {i} = lambda _ {n + 1-i}}$ también es un valor propio de A si G es un gráfico bipartito. En particular, − d es un valor propio de cualquier gráfico bipartito d -regular.

La diferencia ${ estilo de visualización lambda _ {1} - lambda _ {2}}$ se denomina brecha espectral y está relacionada con la expansión de G. También es útil introducir el radio espectral de $A$ denotado por ${displaystyle lambda (G)=max _{left|lambda _{i}right|<d}|lambda _{i}|}$ . Este número está acotado por ${displaystyle lambda (G)geq 2{sqrt {d-1}}-o(1)}$ . Este límite es estrecho en los gráficos de Ramanujan, que tienen aplicaciones en muchas áreas.

Isomorfismo e invariantes

Supongamos que se dan dos gráficos dirigidos o no dirigidos G ₁ y G ₂ con matrices de adyacencia A ₁ y A ₂. G ₁ y G ₂ son isomorfos si y solo si existe una matriz de permutación P tal que $PA_{1}P^{-1}=A_{2}.$

En particular, A ₁ y A ₂ son similares y por lo tanto tienen el mismo polinomio mínimo, polinomio característico, valores propios, determinante y traza. Por lo tanto, estos pueden servir como invariantes de isomorfismo de los gráficos. Sin embargo, dos gráficos pueden poseer el mismo conjunto de valores propios pero no ser isomorfos. Se dice que tales operadores lineales son isoespectrales.

Poderes de la matriz

Si A es la matriz de adyacencia del grafo dirigido o no dirigido G, entonces la matriz A (es decir, el producto matricial de n copias de A) tiene una interpretación interesante: el elemento (i, j) da el número de (dirigido o no dirigido)) paseos de longitud n desde el vértice i hasta el vértice j. Si n es el entero no negativo más pequeño, tal que para algún i, j, el elemento (i, j) de Aes positivo, entonces n es la distancia entre el vértice i y el vértice j. Esto implica, por ejemplo, que el número de triángulos en un gráfico no dirigido G es exactamente la traza de A dividida por 6. La matriz de adyacencia se puede usar para determinar si el gráfico es conexo o no.

Estructuras de datos

La matriz de adyacencia puede usarse como una estructura de datos para la representación de gráficos en programas informáticos para manipular gráficos. La principal estructura de datos alternativa, también en uso para esta aplicación, es la lista de adyacencia.

Debido a que cada entrada en la matriz de adyacencia requiere solo un bit, se puede representar de una manera muy compacta, ocupando solo | V | / 8 bytes para representar un gráfico dirigido, o (utilizando un formato triangular empaquetado y almacenando solo la parte triangular inferior de la matriz) aproximadamente | V | / 16 bytes para representar un gráfico no dirigido. Aunque son posibles representaciones un poco más sucintas, este método se acerca al límite inferior de la teoría de la información para el número mínimo de bits necesarios para representar todos los gráficos de n vértices. Para almacenar gráficos en archivos de texto, se pueden usar menos bits por byte para garantizar que todos los bytes sean caracteres de texto, por ejemplo, usando una representación Base64.Además de evitar el desperdicio de espacio, esta compacidad favorece la localidad de referencia. Sin embargo, para un gráfico disperso grande, las listas de adyacencia requieren menos espacio de almacenamiento porque no desperdician espacio para representar bordes que no están presentes.

Una forma alternativa de matriz de adyacencia (que, sin embargo, requiere una mayor cantidad de espacio) reemplaza los números en cada elemento de la matriz con punteros a objetos de borde (cuando hay bordes presentes) o punteros nulos (cuando no hay borde). También es posible almacenar pesos de borde directamente en los elementos de una matriz de adyacencia.

Además de la compensación de espacio, las diferentes estructuras de datos también facilitan diferentes operaciones. Encontrar todos los vértices adyacentes a un vértice dado en una lista de adyacencia es tan simple como leer la lista y lleva un tiempo proporcional al número de vecinos. Con una matriz de adyacencia, se debe escanear una fila completa, lo que lleva una mayor cantidad de tiempo, proporcional a la cantidad de vértices en el gráfico completo. Por otro lado, probar si hay un borde entre dos vértices dados se puede determinar de inmediato con una matriz de adyacencia, mientras que requiere un tiempo proporcional al grado mínimo de los dos vértices con la lista de adyacencia.