Matriz de adyacencia

Una matriz de adyacencia es una forma de representar un gráfico como una matriz.

Definición

La matriz de adyacencia de un grafo con un número finito de vértices (numerados del 1 al ) es una matriz cuadrada entera de tamaño , en la que el valor del elemento es igual al número de aristas desde el vértice del gráfico hasta el vértice. $GRAMO$ $norte$ $norte$ ${\matemáticas A}$ $n\veces n$ $a_{i,j}$ $i$ $j$

A veces, especialmente en el caso de un gráfico no dirigido, un bucle (una arista desde el -ésimo vértice hacia sí mismo) cuenta como dos aristas, es decir, el valor del elemento diagonal en este caso es igual al doble del número de bucles alrededor el -ésimo vértice. $i$ ${\ Displaystyle a_ {yo, yo}}$ $i$

La matriz de adyacencia de un gráfico simple (que no contiene bucles ni aristas múltiples) es una matriz binaria y contiene ceros en la diagonal principal .

La matriz de adyacencia de un grafo bipartito

La matriz de adyacencia de un grafo bipartito , cuyas partes también tienen vértices , se puede escribir de la siguiente forma ${\matemáticas A}$ $r$ $s$

\mathbf {A} ={\begin{pmatrix}\mathbf {0} _{r,r}&\mathbf {B} \\\mathbf {B} ^{T}&\mathbf {0} _ {s,s}\end{pmatriz}},

donde es una matriz y y son matrices cero . En este caso, la matriz más pequeña representa de forma única el gráfico y las partes restantes de la matriz se pueden descartar. a veces llamada matriz de bis-adyacencia. $\matemáticas {B}$ ${\ estilo de visualización r \ veces s}$ ${\ estilo de visualización \ mathbf {0} _ {r, r}}$ ${\ estilo de visualización \ mathbf {0} _ {s, s}}$ ${\ estilo de visualización r \ veces r}$ $s \ veces s$ $\matemáticas {B}$ ${\matemáticas A}$ $\matemáticas {B}$

Formalmente, sea un grafo bipartito con partes y . Una matriz biconjugada es una matriz 0-1 en la que si y solo si . ${\ Displaystyle G = (U, V, E)}$ $U=\{u_{1},\dots,u_{r}\}$ $V=\{v_{1},\puntos,v_{s}\}$ ${\ estilo de visualización r \ veces s}$ $\matemáticas {B}$ ${\ estilo de visualización b_ {i, j} = 1}$ ${\ estilo de visualización (u_ {i}, v_ {j}) \ en E}$

Si es un multigrafo bipartito o un grafo ponderado, entonces los elementos serán el número de aristas entre vértices o los pesos de las aristas, respectivamente. $GRAMO$ ${\ Displaystyle b_ {i, j}}$ ${\ estilo de visualización (u_ {i}, v_ {j})}$

Ejemplos

A continuación se muestra un ejemplo de un gráfico no dirigido y su correspondiente matriz de adyacencia . Este gráfico contiene un bucle alrededor del vértice 1 y, según las aplicaciones específicas, un elemento puede considerarse igual a uno (como se muestra a continuación) o dos. ${\matemáticas A}$ ${\ estilo de visualización a_ {1,1}}$

Grafico	Matriz de adyacencia
	${\begin{pmatrix}1&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))$

$a_{i,j}$ es el número de aristas que conectan los vértices y , y en algunas aplicaciones cada bucle (arista para algunas ) se cuenta dos veces. $v_{i}$ $v_{j}$ $\{v_{i},v_{i}\}$ $i$

La matriz de adyacencia de un gráfico vacío que no contiene bordes consta de todos ceros.

Propiedades

La matriz de adyacencia de un grafo no dirigido es simétrica , lo que significa que tiene valores propios reales y una base ortogonal de vectores propios. El conjunto de sus valores propios se denomina espectro del gráfico, y es el principal tema de estudio en la teoría de grafos espectrales .

Dos grafos y con matrices de adyacencia son isomorfos si y solo si existe una matriz de permutación tal que $G_{1}$ $G_{2}$ ${\ estilo de visualización \ mathbf {A} _ {1}}$ ${\ estilo de visualización \ mathbf {A} _ {2}}$ $\mathbf {P}$

{\displaystyle \mathbf {P} \mathbf {A} _{1}\mathbf {P} ^{-1}=\mathbf {A} _{2))

De esto se deduce que las matrices y son similares y, por lo tanto, tienen conjuntos iguales de valores propios, determinantes y polinomios característicos. Sin embargo, lo contrario no siempre es cierto: dos gráficos con matrices de adyacencia similares pueden no ser isomorfos (esto sucede si la matriz no es permutable, por ejemplo, las matrices y son similares, pero los gráficos correspondientes no son isomorfos). ${\ estilo de visualización \ mathbf {A} _ {1}}$ ${\ estilo de visualización \ mathbf {A} _ {2}}$ $\mathbf {P}$ ${\begin{pmatrix}0&1\\0&0\end{pmatrix}}$ ${\begin{pmatrix}0&2\\0&0\end{pmatrix}}$

Potencias de la matriz

Si es la matriz de adyacencia del gráfico , entonces la matriz tiene la siguiente propiedad: el elemento en la -ésima fila, -ésima columna es igual al número de caminos desde el -ésimo vértice hasta el -ésimo, que consta exactamente de aristas. ${\matemáticas A}$ $GRAMO$ ${\ estilo de visualización \ mathbf {A} ^ {m}}$ $i$ $j$ $i$ $j$ $metro$

Estructura de datos

La matriz de adyacencia y las listas de adyacencia son las principales estructuras de datos que se utilizan para representar gráficos en programas informáticos.

El uso de una matriz de adyacencia es preferible solo en el caso de gráficos no dispersos con una gran cantidad de bordes, ya que requiere almacenar un bit de datos para cada elemento. Si el gráfico es disperso, la mayor parte de la memoria se desperdiciará almacenando ceros, pero en el caso de gráficos no dispersos, la matriz de adyacencia representa el gráfico en la memoria de manera bastante compacta, utilizando aproximadamente un bit de memoria, que puede ser una orden. de magnitud mejor que las listas de adyacencia. $n^{2}$

En los algoritmos que trabajan con gráficos ponderados (por ejemplo, en el algoritmo de Floyd-Warshall ), los elementos de la matriz de adyacencia, en lugar de los números 0 y 1, que indican la presencia o ausencia de una arista, suelen contener los pesos de las aristas. ellos mismos. Al mismo tiempo, se coloca algún valor límite especial ( centinela en inglés ) en lugar de los bordes que faltan , según el problema que se resuelva, generalmente 0 o . $\infty$

Véase también

Literatura

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmos: construcción y análisis = Introducción a los Algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .

Enlaces

Matriz de adyacencia de grafos. Código de programa en Pascal y C++