En teoría de grafos e informática , una matriz de adyacencia es una matriz cuadrada que se utiliza 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, todas sus aristas son bidireccionales), la matriz de adyacencia es simétrica . La relación entre un gráfico y los valores propios y vectores propios de su matriz de adyacencia se estudia en la teoría de grafos espectrales .
La matriz de adyacencia de un gráfico debe distinguirse de su matriz de incidencia , una representación matricial diferente cuyos elementos indican si los pares vértice-arista son incidentes o no, y su matriz de grados , que contiene información sobre el grado de cada vértice.
Para un gráfico simple con conjunto de vértices U = { u 1 , …, u n } , la matriz de adyacencia es una matriz A cuadrada n × n tal que su elemento A ij es uno cuando hay una arista desde el vértice u i al vértice u j y cero cuando no hay arista. [1] Los elementos diagonales de la matriz son todos cero, ya que las aristas desde un vértice hacia sí mismo ( bucles ) no están permitidas en gráficos simples. A veces también es útil en teoría de grafos algebraicos reemplazar los elementos distintos de cero con variables algebraicas. [2] 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 una sola arista) o dos veces (como dos incidencias de vértice-arista), siempre y cuando se siga una convención consistente. Los gráficos no dirigidos suelen utilizar la última convención de contar bucles dos veces, mientras que los gráficos dirigidos suelen utilizar la primera convención.
La matriz de adyacencia A de un gráfico bipartito cuyas dos partes tienen vértices r y s se puede escribir en la forma
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 forma única el gráfico y las partes restantes de A pueden descartarse como redundantes. A B a veces se le llama matriz de biadyacencia .
Formalmente, sea G = ( U , V , E ) un gráfico bipartito con partes U = { u 1 , ..., u r } , V = { v 1 , ..., v s } y aristas E . La matriz de biaadyacencia es la matriz B r × s 0–1 en la que bi , j = 1 si y sólo si ( u i , v j ) ∈ E.
Si G es un multigrafo bipartito o un gráfico ponderado , entonces los elementos bi , j se toman como el número de aristas entre los vértices o el peso de la arista ( u i , v j ) , respectivamente.
Una matriz de adyacencia ( a , b , c ) A de un gráfico 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 gráficos fuertemente regulares y dos gráficos . [3]
La matriz de distancias tiene en posición ( i , j ) la distancia entre los vértices v i y v j . La distancia es la longitud del 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 que contiene. La matriz de distancia se asemeja a una potencia alta de la matriz de adyacencia, pero en lugar de decir sólo si dos vértices están conectados o no (es decir, la matriz de conexión, que contiene valores booleanos ), proporciona la distancia exacta entre ellos.
La convención seguida aquí (para gráficos no dirigidos) es que cada arista suma 1 a la celda apropiada de la matriz y cada bucle suma 2. [4] Esto permite encontrar fácilmente el grado de un vértice tomando la suma de los valores. en su respectiva fila o columna en la matriz de adyacencia.
La matriz de adyacencia de un gráfico dirigido puede ser asimétrica. Se puede definir la matriz de adyacencia de un gráfico dirigido de tal manera que
La primera definición se utiliza comúnmente en teoría de grafos y análisis de redes sociales (p. ej., sociología, ciencias políticas, economía, psicología). [5] Este último es más común en otras ciencias aplicadas (por ejemplo, sistemas dinámicos, física, ciencia de redes) donde A se utiliza a veces para describir dinámica lineal en gráficos. [6]
Usando la primera definición, los grados de entrada de un vértice se pueden calcular sumando las entradas de la columna correspondiente y los grados de salida del vértice sumando las entradas de la fila correspondiente. Cuando se utiliza 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 está dado por la suma de la columna correspondiente.
La matriz de adyacencia de un gráfico completo contiene todos 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 .
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. [7] Es común denotar los valores propios por
El mayor valor propio está limitado arriba por el grado máximo. Esto puede verse como resultado del teorema de Perron-Frobenius , pero puede demostrarse fácilmente. Sea v un vector propio asociado a y x el componente en el que v tiene el valor absoluto máximo. Sin pérdida de generalidad, suponga que v x es positivo ya que de lo contrario simplemente toma el vector propio , también asociado a . Entonces
Para d -gráficos 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 al límite anterior). La multiplicidad de este valor propio es el número de componentes conectados de G , en particular para gráficos conectados. Se puede demostrar que para cada valor propio , su opuesto también es un valor propio de A si G es un gráfico bipartito . [8] En particular, − d es un valor propio de cualquier d gráfico bipartito regular.
La diferencia se llama brecha espectral y está relacionada con la expansión de G. También es útil introducir el radio espectral de denotado por . Este número está limitado por . Este límite es estrecho en los gráficos de Ramanujan , que tienen aplicaciones en muchas áreas.
Supongamos que se dan dos gráficos dirigidos o no dirigidos G 1 y G 2 con matrices de adyacencia A 1 y A 2 . G 1 y G 2 son isomorfos si y sólo si existe una matriz de permutación P tal que
En particular, A 1 y A 2 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 gráficos. Sin embargo, dos gráficos pueden poseer el mismo conjunto de valores propios pero no ser isomórficos. [9] Se dice que estos operadores lineales son isoespectrales .
Si A es la matriz de adyacencia del grafo dirigido o no dirigido G , entonces la matriz An (es decir , el producto matricial de n copias de A ) tiene una interpretación interesante: el elemento ( i , j ) da el número de (dirigidos o no). no dirigido) paseos de longitud n desde el vértice i al vértice j . Si n es el entero no negativo más pequeño, tal que para algunos i , j , el elemento ( i , j ) de An es positivo, entonces n es la distancia entre el vértice i y el vértice j . Un gran ejemplo de cómo esto es útil es contar el número de triángulos en un gráfico no dirigido G , que es exactamente la traza de A 3 dividida por 3 o 6 dependiendo de si el gráfico está dirigido o no. Dividimos por esos valores para compensar el conteo excesivo de cada triángulo. En un gráfico no dirigido, cada triángulo se contará dos veces para los tres nodos, porque el camino se puede seguir en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj: ijk o ikj. La matriz de adyacencia se puede utilizar para determinar si el gráfico es conexo o no .
Si un gráfico dirigido tiene una matriz de adyacencia nilpotente ( es decir, si existe n tal que An es la matriz cero), entonces es un gráfico acíclico dirigido . [10]
La matriz de adyacencia se puede utilizar como estructura de datos para la representación de gráficos en programas informáticos para manipular gráficos. La principal estructura de datos alternativa, que también se utiliza para esta aplicación, es la lista de adyacencia . [11] [12]
El espacio necesario para representar una matriz de adyacencia y el tiempo necesario para realizar operaciones en ellas depende de la representación matricial elegida para la matriz subyacente. Las representaciones de matrices dispersas solo almacenan entradas de matrices distintas de cero e implícitamente representan las entradas de cero. Pueden, por ejemplo, usarse para representar gráficos dispersos sin incurrir en la sobrecarga de espacio al almacenar las muchas entradas cero en la matriz de adyacencia del gráfico disperso. En la siguiente sección se supone que la matriz de adyacencia está representada por una estructura de datos de matriz , de modo que las entradas cero y distintas de cero se representan directamente en el almacenamiento.
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 | 2/8 bytes para representar un gráfico dirigido, o (usando un formato triangular empaquetado y almacenando solo la parte triangular inferior de la matriz) aproximadamente | V | 2/16 bytes para representar un gráfico no dirigido. Aunque son posibles representaciones ligeramente más concisas, este método se acerca al límite inferior teórico de la información para el número mínimo de bits necesarios para representar todos los gráficos de n -vértices. [13] 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 . [14] Además de evitar el desperdicio de espacio, esta compacidad fomenta 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 representando bordes que no están presentes. [12] [15]
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 bordes). [15] También es posible almacenar pesos de borde directamente en los elementos de una matriz de adyacencia. [12]
Además de la compensación espacial, las diferentes estructuras de datos también facilitan diferentes operaciones. Encontrar todos los vértices adyacentes a un vértice determinado en una lista de adyacencia es tan simple como leer la lista y requiere 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 al número de vértices en todo el gráfico. Por otro lado, probar si existe una arista 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. [12] [15]
