Hispanopedia Wiki
Articulo de referencia

matriz de adyacencia

En teoría de grafos e informática , una matriz de adyacencia es una matriz cuadrada que se utiliza para representar un grafo finito . Los elementos de la matriz indican si pares...

Hispanopedia WikiContenido en espanolLectura gratuita

En teoría de grafos e informática , una matriz de adyacencia es una matriz cuadrada que se utiliza para representar un grafo finito . Los elementos de la matriz indican si pares de vértices son adyacentes o no dentro del grafo.

En el caso particular 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, todas sus aristas son bidireccionales), la matriz de adyacencia es simétrica . La relación entre un grafo y los autovalores y autovectores de su matriz de adyacencia se estudia en la teoría espectral de grafos .

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 de 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 1 , ..., u n } , la matriz de adyacencia es una matriz cuadrada n × n A tal que su elemento A ij es 1 cuando hay una arista del vértice u i al vértice u j , y 0 cuando no hay arista. [ 1 ] Los elementos diagonales de la matriz son todos 0, ya que las aristas de un vértice a sí mismo ( bucles ) no están permitidas en grafos simples. También es útil a veces en la teoría algebraica de grafos reemplazar los elementos no nulos con variables algebraicas. [ 2 ] El mismo concepto puede extenderse a multigrafos y grafos con bucles almacenando el número de aristas entre cada par de vértices en el elemento de matriz correspondiente, y permitiendo elementos diagonales no nulos. Los bucles pueden contarse una vez (como una sola arista) o dos veces (como dos incidencias vértice-arista), siempre que se siga una convención consistente. Los grafos no dirigidos suelen utilizar la segunda convención, que consiste en contar los bucles dos veces, mientras que los grafos dirigidos suelen utilizar la primera.

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

A=(0r,rBBT0s,s),{\displaystyle A={\begin{pmatrix}0_{r,r}&B\\B^{\mathsf {T}}&0_{s,s}\end{pmatrix}},}

donde B es una matriz de r × s , y 0 r , r y 0 s , s representan las matrices nulas de r × r y s × s . En este caso, la matriz más pequeña B representa de forma única el grafo, y las partes restantes de A pueden descartarse por ser redundantes. A veces, B se denomina matriz de biadyacencia .

Formalmente, sea G = ( U , V , E ) un grafo bipartito con partes U = { u 1 , ..., u r } , V = { v 1 , ..., v s } y aristas E . La matriz de biadyacencia es la matriz 0-1 r × s 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 ) de un grafo simple, A , 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 grafos de dos nodos . [ 3 ]

La matriz de distancias contiene en la posición ( i , j ) la distancia entre los vértices v i y v j . Esta distancia es la longitud del camino más corto que conecta dichos vértices. A menos que se especifiquen explícitamente las longitudes de las aristas, la longitud de un camino corresponde al número de aristas que lo componen. La matriz de distancias se asemeja a una matriz de adyacencia elevada, pero en lugar de indicar únicamente si dos vértices están conectados o no (como la matriz de conexiones, que contiene valores booleanos ), proporciona la distancia exacta entre ellos.

Ejemplos

Grafos no dirigidos

La convención que se sigue aquí (para grafos no dirigidos) es que cada arista suma 1 a la celda correspondiente de la matriz, y cada bucle (una arista de un vértice a sí mismo) suma 2 a la celda correspondiente de la diagonal de la matriz. [ 4 ] Esto permite calcular fácilmente el grado de un vértice sumando los valores de su fila o columna correspondiente 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 una arista de j a i .

La primera definición se usa 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 segunda es más común en otras ciencias aplicadas (por ejemplo, sistemas dinámicos, física, ciencia de redes) donde A se usa a veces para describir dinámicas lineales en grafos. [ 6 ]

Según la primera definición, el grado de entrada de un vértice se calcula sumando los elementos de la columna correspondiente, y el grado de salida, sumando los elementos de la fila correspondiente. En 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, por la suma de la columna correspondiente.

Gráficos triviales

La matriz de adyacencia de un grafo completo contiene todos unos excepto en la diagonal, donde solo hay ceros. La matriz de adyacencia de un grafo vacío es una matriz de ceros .

Propiedades

Espectro

La matriz de adyacencia de un grafo simple no dirigido es simétrica y, por lo tanto, tiene un conjunto completo de autovalores reales y una base de autovectores ortogonales . El conjunto de autovalores de un grafo es el espectro del grafo. [ 7 ] Es común denotar los autovalores porλ1≥λ2≥⋯≥λnorte.{\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}.}

El mayor valor propioλ1{\displaystyle \lambda _{1}}está acotado superiormente 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λ1{\displaystyle \lambda _{1}}y x una entrada en la que v tiene el máximo valor absoluto. Sin pérdida de generalidad, supongamos que v x es positivo, ya que de lo contrario simplemente se toma el vector propio − v , también asociado aλ1{\displaystyle \lambda _{1}}. Entonces

λ1vincógnita=(Av)incógnita=∑y=1norteAincógnita,yvy≤∑y=1norteAincógnita,yvincógnita=vincógnitagrados⁡(incógnita).{\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 autovalor de A para el vector v = (1, ..., 1) (es fácil comprobar que es un autovalor y que es el máximo debido a la cota anterior). La multiplicidad de este autovalor es el número de componentes conexas de G , en particularλ1>λ2{\displaystyle \lambda _ {1}> \ lambda _ {2}}para grafos conectados. Se puede demostrar que para cada valor propioλi{\displaystyle \lambda _{i}}, su opuesto−λi=λnorte+1−i{\displaystyle -\lambda _{i}=\lambda _{n+1-i}}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.

La diferenciaλ1−λ2{\displaystyle \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 deA{\displaystyle A}denotado porλ(GRAMO)=máximo|λi|<d|λi|{\displaystyle \lambda (G)=\max _{\left|\lambda _{i}\right|<d}|\lambda _{i}|}Este número está acotado porλ(GRAMO)≥2d−1−o(1){\displaystyle \lambda (G)\geq 2{\sqrt {d-1}}-o(1)}. Este límite es estricto en los gráficos de Ramanujan .

Isomorfismo e invariantes

Supongamos que se dan dos grafos 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 solo si existe una matriz de permutación P tal que

PAGA1PAG−1=A2.{\displaystyle PA_{1}P^{-1}=A_{2}.}

En particular, A 1 y A 2 son similares y, por lo tanto, tienen el mismo polinomio mínimo , polinomio característico , autovalores , determinante y traza . Estos pueden, por consiguiente, servir como invariantes de isomorfismo de grafos. Sin embargo, dos grafos pueden poseer el mismo conjunto de autovalores pero no ser isomorfos. [ 9 ] Se dice que tales operadores lineales son isoespectrales .

Poderes de Matrix

Si A es la matriz de adyacencia del grafo dirigido o no dirigido G , entonces la matriz A n (es decir, el producto matricial de n copias de A ) tiene una interpretación interesante: el elemento ( i , j ) da el número de caminos (dirigidos o no dirigidos) de longitud n desde el vértice i al vértice j . [ 10 ] Si n es el entero no negativo más pequeño, tal que para algún i , j , el elemento ( i , j ) de A n 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 en contar el número de triángulos en un grafo no dirigido G , que es exactamente la traza de A 3 dividida por 3 o 6 dependiendo de si el grafo es dirigido o no. Dividimos por esos valores para compensar el sobreconteo de cada triángulo. En un grafo no dirigido, cada triángulo se contará dos veces para los tres nodos, ya que el camino se puede seguir en sentido horario o antihorario  : ijk o ikj. La matriz de adyacencia se puede utilizar para determinar si el grafo está conectado o no .

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

Estructuras de datos

La matriz de adyacencia puede utilizarse como estructura de datos para la representación de grafos en programas informáticos para la manipulación de grafos. Se utilizan tipos de datos booleanos , como Truey Falseen Python . La principal estructura de datos alternativa, también utilizada para esta aplicación, es la lista de adyacencia . [ 12 ] [ 13 ]

El espacio necesario para representar una matriz de adyacencia y el tiempo requerido para realizar operaciones sobre ella dependen de la representación matricial elegida para la matriz subyacente. Las representaciones de matrices dispersas solo almacenan los elementos distintos de cero y representan implícitamente los elementos cero. Por ejemplo, pueden utilizarse para representar grafos dispersos sin incurrir en el espacio adicional que supone almacenar los numerosos elementos 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 tanto los elementos cero como los distintos 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 grafo 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 grafo 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 grafos de n vértices. [ 14 ] Para almacenar grafos en archivos de texto , se pueden usar menos bits por byte para asegurar que todos los bytes sean caracteres de texto, por ejemplo, usando una representación Base64 . [ 15 ] Además de evitar el desperdicio de espacio, esta compacidad fomenta la localidad de referencia . Sin embargo, para un grafo disperso grande , las listas de adyacencia requieren menos espacio de almacenamiento, porque no desperdician ningún espacio representando aristas que no están presentes. [ 13 ] [ 16 ]

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

Además de la compensación de espacio, las diferentes estructuras de datos también facilitan distintas 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 requiere un tiempo proporcional al número de vecinos. Con una matriz de adyacencia, se debe escanear una fila completa, lo que requiere un tiempo mayor, proporcional al número de vértices en todo el grafo. Por otro lado, comprobar si existe 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. [ 13 ] [ 16 ]

Véase también

Referencias

  1. ↑ Biggs, Norman (1993), Teoría algebraica de grafos , 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). "Grafos fuertemente regulares con matriz de adyacencia (−1, 1, 0) que tiene 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). «Grafos y códigos de expansión» . Volumen 68 de la serie DIMACS en matemáticas discretas y ciencias de la computación teóricas . Teoría de la codificación algebraica y teoría de la información: Taller DIMACS, Teoría de la codificación algebraica y teoría de la información. Sociedad Matemática Americana. pág. 63. ISBN  9780821871102.
  5. ↑ Borgatti, Steve; Everett, Martin; Johnson, Jeffrey (2018), Analyzing Social Networks (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" , Espectros de gráficos , Universitext, Nueva York: Springer, págs. 6–7 , doi : 10.1007/978-1-4614-1939-6 , ISBN  978-1-4614-1938-9, MR 2882891 
  9. ↑ Godsil, Chris ; Royle, Gordon, Teoría algebraica de grafos , Springer (2001), ISBN 0-387-95241-1pág. 164
  10. ↑ "Una breve introducción a la teoría de grafos" (PDF) . www.people.computing.clemson.edu . Consultado el 8 de diciembre de 2025 .
  11. ↑ Nicholson, Victor A. (1975-01-01). "Matrices con permanente igual a uno" . Álgebra lineal y sus aplicaciones . 12 (2): 187. doi : 10.1016/0024-3795(75)90067-1 . ISSN 0024-3795 . 
  12. ↑ Goodrich y Tamassia (2015) , pág. 361: "Hay dos estructuras de datos que la gente suele usar para representar grafos: la lista de adyacencia y la matriz de adyacencia."
  13. 1 2 3 4 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.
  14. ↑ Turán, György (1984), "Sobre la representación sucinta de grafos", Matemáticas Aplicadas Discretas , 8 (3): 289– 294, doi : 10.1016/0166-218X(84)90126-4 , MR 0749658 .
  15. ↑ McKay, Brendan , Descripción de las codificaciones graph6 y sparse6 , archivado del original el 30/04/2001 , recuperado el 10/02/2012..
  16. 1 2 3 Goodrich, Michael T. ; Tamassia, Roberto (2015), Diseño y aplicaciones de algoritmos , Wiley, pág. 363 .
  • Weisstein, Eric W. "Matriz de adyacencia" . MathWorld .
  • Fluffschack : un juego web educativo en Java que demuestra la relación entre matrices de adyacencia y grafos.
  • Estructuras de datos abiertas - Sección 12.1 - Matriz de adyacencia: Representación de un grafo mediante una matriz , Pat Morin
  • Matemáticas de café  : Matrices de adyacencia de grafos  : Aplicación de las matrices de adyacencia al cálculo de series generadoras de recorridos.