Matriz de adyacencia - Adjacency matrix

En teoría de grafos y ciencias de la computación , una matriz de adyacencia es una matriz cuadrada que se usa 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 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-borde son incidentes o no, y su matriz de grados , que contiene información sobre el grado de cada vértice.

Definición

Para un simple gráfico con conjunto de vértices U = { u ₁ , ..., u _n }, la matriz de adyacencia es un cuadrado n × n matriz A de tal manera que su elemento A _ij es uno cuando hay un borde de vértice u _i al vértice u _j , y cero cuando no hay borde. 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 grafos algebraicos reemplazar los elementos distintos de cero con variables algebraicas. El mismo concepto puede extenderse a gráficos múltiples 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 (como dos incidencias de borde de vértice), siempre que se siga una convención coherente. Los gráficos no dirigidos a menudo utilizan la última convención de contar bucles dos veces, mientras que los gráficos dirigidos suelen utilizar la primera convención.

De un gráfico bipartito

La matriz de adyacencia A de un gráfico bipartito cuyos dos partes tienen r y s vértices se pueden 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 B más pequeña representa de forma única el gráfico y las partes restantes de A pueden descartarse como redundantes. B a veces se denomina matriz de biadyacencia .

Formalmente, dejar que G = ( U , V , E ) sea un gráfico bipartito con partes U = { u ₁ , ..., u _r }, V = { v ₁ , ..., v _s } y los bordes E . La matriz biadjacency es el r × s 0-1 matriz B en el que b _{i , j} = 1 si y sólo si ( u _i , v _j ) ∈ E .

Si G es un multigrafo bipartito o 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 una gráfica 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áficas fuertemente regulares y gráficas de dos .

La matriz de distancias 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 los bordes, la longitud de un camino es el número de bordes en él. La matriz de distancia se asemeja a una alta potencia 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 de

Gráficos no dirigidos

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

Gráfico etiquetado	Matriz de adyacencia
	${\ displaystyle {\ begin {pmatrix} 2 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 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 de colores son unos.

Gráficos dirigidos

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

1. un no-cero elemento A _ij indica un borde 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). Este último 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 la dinámica lineal 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 está dado por la suma de la columna correspondiente.

Gráfico etiquetado	Matriz de adyacencia
Directed gráfico Cayley de S 4	Las coordenadas son 0-23. Como se indica en 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${\ Displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}.}$

El mayor valor propio está delimitado por encima del grado máximo. Esto puede verse como resultado del teorema de Perron-Frobenius , pero puede demostrarse fácilmente. Deje que v sea un vector propio asociado a y x el componente en el que v tiene un valor máximo absoluto. 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 . Luego ${\ 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 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 . En particular, d es un valor propio de gráficos bipartitos. ${\ Displaystyle \ lambda _ {1}> \ lambda _ {2}}$${\ Displaystyle \ lambda _ {i}}$${\ Displaystyle - \ lambda _ {i} = \ lambda _ {n + 1-i}}$

La diferencia se llama el espacio espectral y se relaciona 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. ${\ 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

Suponga 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

${\ 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 , autovalores , 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. Se dice que estos operadores lineales son isospectrales .

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) no dirigido) caminatas de longitud n desde el vértice i al vértice j . Si n es el número entero no negativo más pequeño, tal que para algunos 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 . Esto implica, por ejemplo, que el número de triángulos en una gráfica no dirigida G es exactamente la traza de A ³ dividida por 6. La matriz de adyacencia se puede usar para determinar si la gráfica está conectada 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 de computadora para manipular gráficos. La estructura de datos alternativa principal, 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 (mediante el uso de un formato triangular embalado y sólo el almacenamiento de la parte triangular inferior de la matriz) de aproximadamente | V | ² /16 bytes para representar un grafo no dirigido. Aunque son posibles representaciones un poco más concisas, 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 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 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 para representar los 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 los bordes están presentes) o punteros nulos (cuando no hay borde). También es posible almacenar los pesos de los bordes directamente en los elementos de una matriz de adyacencia.

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 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 al número de vértices en todo el gráfico. Por otro lado, probar si hay una arista entre dos vértices dados se puede determinar a la vez 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.

Ver también

• Matriz laplaciana
• Matriz de auto-semejanza

Referencias

enlaces externos

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