Matriz de adyacencia

Matriz cuadrada utilizada para representar un gráfico o red

En teoría de grafos y ciencias de la computación , una matriz de adyacencia es una matriz cuadrada que se utiliza para representar un grafo finito . Los elementos de la matriz indican si los pares de vértices son adyacentes o no en el grafo.

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

La matriz de adyacencia de un grafo 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.

Definición

Para un grafo simple con conjunto de vértices U = { u ₁ , …, u _n } , la matriz de adyacencia es una matriz cuadrada n  ×  n A tal que su elemento A _ij es uno cuando hay una arista desde el vértice u _i hasta el 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 hasta sí mismo ( bucles ) no están permitidas en grafos simples. También es útil a veces en la teoría de grafos algebraicos reemplazar los elementos distintos de cero con variables algebraicas. ^[2] El mismo concepto se puede extender a multigrafos y grafos 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 vértice-arista), siempre que se siga una convención consistente. Los gráficos no dirigidos a menudo utilizan la última convención de contar los bucles dos veces, mientras que los gráficos dirigidos normalmente utilizan la primera convención.

De un gráfico bipartito

La matriz de adyacencia A de un grafo bipartito cuyas dos partes tienen r y s vértices se puede escribir en 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 más pequeña B representa únicamente el gráfico, y las partes restantes de A pueden descartarse por ser redundantes. A B a veces se la denomina 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 r  ×  s 0–1 B en la que b _{i , j} = 1 si y solo 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 matriz de adyacencia ( a , b , c ) A 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 bigrafos . ^[3]

La matriz de distancia tiene en la 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 las aristas, la longitud de un camino es el número de aristas que tiene. La matriz de distancia se parece a una alta potencia de la matriz de adyacencia, pero en lugar de indicar solo 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.

Ejemplos

Grafos no dirigidos

La convención seguida aquí (para gráficos no dirigidos) es que cada borde suma 1 a la celda apropiada en la matriz, y cada bucle (un borde desde un vértice hacia sí mismo) suma 2 a la celda apropiada en la diagonal de la matriz. ^[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.

Grafos dirigidos

La matriz de adyacencia de un grafo dirigido puede ser asimétrica. Se puede definir la matriz de adyacencia de un grafo dirigido de tal manera que

1. un elemento distinto de cero A _ij indica una arista de i a j o
2. Indica un borde de j a i .

La primera definición se utiliza comúnmente en la teoría de grafos y el análisis de redes sociales (por ejemplo, sociología, ciencias políticas, economía, psicología). ^[5] La última es más común en otras ciencias aplicadas (por ejemplo, sistemas dinámicos, física, ciencia de redes) donde A a veces se utiliza para describir la dinámica lineal en grafos. ^[6]

Utilizando 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 utiliza la segunda definición, el grado de entrada de un vértice se da por la suma de la fila correspondiente y el grado de salida se da por la suma de la columna correspondiente.

Gráficos triviales

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

Propiedades

Espectro

La matriz de adyacencia de un grafo simple no dirigido es simétrica y, por lo tanto, tiene un conjunto completo de valores propios reales y una base de vectores propios ortogonal . El conjunto de valores propios de un grafo es el espectro del grafo. ^[7] Es común denotar los valores propios por ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}.}$

El mayor valor propio está acotado por encima del grado máximo. Esto puede verse como resultado del teorema de Perron-Frobenius , pero se puede demostrar 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 se toma el vector propio , también asociado a . Entonces ${\displaystyle \lambda _{1}}$ ${\displaystyle \lambda _{1}}$ ${\displaystyle -v}$ ${\displaystyle \lambda _{1}}$

${\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}\deg(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 que es el máximo debido a la cota anterior). La multiplicidad de este valor propio es el número de componentes conexos de G , en particular para grafos conexos. Se puede demostrar que para cada valor propio , su opuesto también es un valor propio de A si G es un grafo bipartito . ^[8] En particular − d es un valor propio de cualquier grafo bipartito d -regular. ${\displaystyle \lambda _{1}>\lambda _{2}}$ ${\displaystyle \lambda _{i}}$ ${\displaystyle -\lambda _{i}=\lambda _{n+1-i}}$

La diferencia se denomina 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á acotado por . Este límite es estricto en los grafos de Ramanujan , que tienen aplicaciones en muchas áreas. ${\displaystyle \lambda _{1}-\lambda _{2}}$ ${\displaystyle A}$ ${\displaystyle \lambda (G)=\max _{\left|\lambda _{i}\right|<d}|\lambda _{i}|}$ ${\displaystyle \lambda (G)\geq 2{\sqrt {d-1}}-o(1)}$

Isomorfismo e invariantes

Supóngase que se dan dos grafos dirigidos o no dirigidos G ₁ y G ₂ con matrices de adyacencia A ₁ y A _2. G ₁ y G ₂ son isomorfos si y sólo si existe una matriz de permutación P tal que

${\displaystyle 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 grafos. Sin embargo, dos grafos pueden poseer el mismo conjunto de valores propios pero no ser isomorfos. ^[9] Se dice que tales operadores lineales son isoespectrales .

Potencias 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 paseos (dirigidos o no dirigidos) 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 algún i , j , el elemento ( i , j ) de A ⁿ 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 grafo no dirigido G , que es exactamente la traza de A ³ dividida por 3 o 6 dependiendo de si el grafo es dirigido o no. Dividimos por esos valores para compensar el recuento excesivo de cada triángulo. En un grafo no dirigido, cada triángulo se contará dos veces para los tres nodos, porque el camino puede seguirse en el sentido de las agujas del reloj o en el sentido contrario: ijk o ikj. La matriz de adyacencia se puede utilizar para determinar si el grafo es conexo o no .

Si un grafo dirigido tiene una matriz de adyacencia nilpotente (es decir, si existe n tal que A ⁿ es la matriz cero), entonces es un grafo acíclico dirigido . ^[10]

Estructuras de datos

La matriz de adyacencia puede utilizarse 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, también utilizada 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 dependen de la representación matricial elegida para la matriz subyacente. Las representaciones de matriz dispersa solo almacenan entradas de matriz distintas de cero y representan implícitamente las entradas cero. Por ejemplo, se pueden utilizar para representar grafos dispersos sin incurrir en la sobrecarga de espacio que supone almacenar las numerosas entradas cero en la matriz de adyacencia del grafo 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  | ²  / 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 ligeramente más sucintas, 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, utilizando una representación Base64 . ^[14] Además de evitar el espacio desperdiciado, 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 ningún espacio que represente aristas 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 borde). ^[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 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, en cambio, se debe escanear una fila entera, lo que lleva una mayor cantidad de tiempo, proporcional al número de vértices en todo el grafo. Por otro lado, comprobar si hay una arista entre dos vértices dados se puede determinar de inmediato con una matriz de adyacencia, mientras que con la lista de adyacencia se requiere un tiempo proporcional al grado mínimo de los dos vértices. ^{[12] [15]}

Véase también

• Matriz laplaciana
• Matriz de autosimilitud

Referencias

1. Biggs, Norman (1993), Teoría de grafos algebraicos , Cambridge Mathematical Library (2.ª ed.), Cambridge University Press, Definición 2.1, pág. 7.
2. Harary, Frank (1962), "El determinante de la matriz de adyacencia de un grafo", SIAM Review , 4 (3): 202–210, Bibcode :1962SIAMR...4..202H, doi :10.1137/1004057, MR  0144330.
3. Seidel, JJ (1968). "Gráficos fuertemente regulares con matriz de adyacencia (−1, 1, 0) con valor propio 3". Lin. Alg. Appl. 1 (2): 281–298. doi :10.1016/0024-3795(68)90008-6.
4. Shum, Kenneth; Blake, Ian (18 de diciembre de 2003). "Gráficos y códigos de expansión". Volumen 68 de la serie DIMACS en matemáticas discretas y ciencias de la computación teórica . Teoría de codificación algebraica y teoría de la información: Taller DIMACS, Teoría de codificación algebraica y teoría de la información. Sociedad Matemática Estadounidense. pág. 63. ISBN 9780821871102.
5. Borgatti, Steve; Everett, Martin; Johnson, Jeffrey (2018), Análisis de redes sociales (2.ª ed.), SAGE, pág. 20
6. Newman, Mark (2018), Redes (2.ª ed.), Oxford University Press, pág. 110
7. Biggs (1993), Capítulo 2 ("El espectro de un gráfico"), págs. 7-13.
8. Brouwer, Andries E.; Haemers, Willem H. (2012), "1.3.6 Gráficos bipartitos", Spectra of Graphs , Universitext, Nueva York: Springer, págs. 6-7, doi :10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, Sr.  2882891
9. Godsil, Chris ; Royle, Gordon Teoría de grafos algebraicos , Springer (2001), ISBN 0-387-95241-1 , p.164 
10. Nicholson, Victor A (1975). "Matrices con constantes iguales a uno" (PDF) . Álgebra lineal y sus aplicaciones (12): 187.
11. Goodrich y Tamassia (2015), pág. 361: "Hay dos estructuras de datos que la gente suele utilizar para representar gráficos: la lista de adyacencia y la matriz de adyacencia".
12. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "Sección 22.1: Representaciones de grafos", Introducción a los algoritmos (segunda edición), MIT Press y McGraw-Hill, págs. 527–531, ISBN 0-262-03293-7.
13. Turán, György (1984), "Sobre la representación sucinta de grafos", Discrete Applied Mathematics , 8 (3): 289–294, doi :10.1016/0166-218X(84)90126-4, MR  0749658.
14. McKay, Brendan , Descripción de las codificaciones graph6 y sparse6, archivado desde el original el 30 de abril de 2001 , consultado el 10 de febrero de 2012.
15. Goodrich, Michael T .; Tamassia, Roberto (2015), Diseño y aplicaciones de algoritmos , Wiley, pág. 363.

Enlaces externos

• Weisstein, Eric W. "Matriz de adyacencia". MathWorld .
• Fluffschack: un juego web educativo Java que demuestra la relación entre matrices de adyacencia y gráficos.
• Estructuras de datos abiertas - Sección 12.1 - AdjacencyMatrix: Representación de un gráfico mediante una matriz, Pat Morin
• Café math: Matrices de Adyacencia de Grafos: Aplicación de las matrices de adyacencia al cálculo de series generadoras de caminatas.