Matriz de adxacencia

En teoría de grafos e informática, unha matriz de adxacencia é unha matriz cadrada usada para representar un grafo finito. Os elementos da matriz indican se os pares de vértices son adxacentes ou non no grafo.

No caso especial dun grafo simple finito, a matriz de adxacencia é unha matriz (0,1) con ceros na súa diagonal. Se o grafo é non orientado (é dicir, todas as súas arestas son bidireccionais), a matriz de adxacencia é simétrica. 

A relación entre un grafo e os autovalores e vectores propios da súa matriz de adxacencia estúdase na teoría espectral  de grafos.

A matriz de adxacencia dun grafo debe distinguirse da súa matriz de incidencia, unha representación matricial diferente cuxos elementos indican se os pares vértice-aresta son incidentes ou non, e a súa matriz de graos, que contén información sobre o grao de cada vértice.

 Definición 
Para un grafo simple co conxunto de vértices , a matriz de adxacencia é unha matriz  cadrada  tal que o seu elemento  é 1 cando hai unha aresta desde o vértice  ata o vértice , e 0 cando non hai aresta.  

Os elementos diagonais da matriz son todos 0, xa que os bordos dun vértice ata si mesmo ( bucles ) non están permitidos nos grafos simples. 

O mesmo concepto pódese estender a multigrafos e grafos con bucles almacenando o número de arestas entre cada dous vértices no elemento correspondente da matriz e permitindo elementos diagonais distintos de cero. 

Os bucles pódense contar unha vez (como unha única aresta) ou dúas veces (como dúas incidencias de arestas de vértice), sempre que se siga unha convención consistente. 

Os grafos non orientados adoitan usar a última convención de contar bucles dúas veces, mentres que os grafos orientados normalmente usan a primeira convención.

A matriz de distancias ten na posición  a distancia entre os vértices  e . A distancia é a lonxitude do camiño máis curto que une os vértices. A información que proporciona en lugar de dicir só se dous vértices están ligados ou non (é dicir, a matriz de conexión, que contén valores booleanos), dá a distancia exacta entre eles.

 Exemplos 

 Grafos non orientados 
A convención seguida aquí (para grafos non orientados) é que cada aresta engade 1 á cela apropiada da matriz e cada bucle (unha aresa desde un vértice ata si mesmo) engade 2 á cela apropiada na diagonal da matriz. Isto permite atopar facilmente o grao dun vértice tomando a suma dos valores na súa fila ou columna respectiva na matriz de adxacencia.
Grafo etiquetado Matriz de adxacencia219x219px  

As coordenadas son 1-6.250x250px 

Grafo de Nauru250x250px 

As coordenadas son 0-23. Os campos brancos son ceros, os de cores son uns.

 Grafos orientados 
A matriz de adxacencia dun grafo orientado pode ser asimétrica. Pódese definir a matriz de adxacencia dun grafo orientado de xeito que

 un elemento distinto de cero  indica unha aresta de  a  ou
 indica unha aresta de  a .

A primeira definición úsase habitualmente na teoría de grafos e na análise de redes sociais (por exemplo, socioloxía, ciencias políticas, economía, psicoloxía). 

A segunda definición é máis común noutras ciencias aplicadas (por exemplo, sistemas dinámicos, física, ciencia de redes) onde  ás veces úsase para describir dinámica linear en grafos. 

Usando a primeira definición, o  grao de entrada dun vértice pódese calcular sumando as entradas da columna correspondente e o grao de saída do vértice sumando as entradas da fila correspondente. 
Grafo etiquetado Matriz de adxacencia250x250px 

Grafo de Cayley orientado de S4 250x250px 

As coordenadas son 0-23. Como o grafo está orientado, a matriz non é necesariamente simétrica.

 Propiedades 

 Espectro 
A matriz de adxacencia dun grafo simple non orientado é simétrica e, polo tanto, ten un conxunto completo de valores propios reais e unha base de vectores propios ortogonal. 

O conxunto de valores propios dun grafo é o espectro do grafo., Chapter 2 ("The spectrum of a graph"), pp. 7–13. É común denotar os autovalores por 

O maior valor propio  está limitada por riba polo grao máximo. Isto pódese ver como o resultado do teorema de Perron-Frobenius, mais pódese probar facilmente. 

Sexa  un vector propio asociado a  e  a entrada na que  ten o valor absoluto máximo. Sen perda de xeneralidade supoña que  é positivo xa que se non, simplemente tomamos o vector propio , tamén asociado a . Daquela



Para grafos -regulares,  é o primeiro autovalor de  para o vector  (é doado comprobar que é un autovalor e é o máximo debido ao límite anterior). 

A multiplicidade deste autovalor é o número de compoñentes conectados de , en particular  para grafos conexos. 

Pódese demostrar que para todo valor propio , o seu oposto  tamén é un valor propio de  se  é un grafo bipartito.  En particular − é un valor propio de calquera grafo bipartito -regular.

A diferenza  chámase fenda espectral e está relacionada coa expansión de . Tamén é útil introducir o raio espectral de  denotado como . 

Este número está limitado por . Este límite é axustado nos grafos de Ramanujan.

 Isomorfismo e invariantes 
Supoña que se dan dous grafos orientados ou non orientados  e  con matrices de adxacencia  e .  e  son isomorfos se e só se existe unha matriz de permutación  tal que



En particular,  e  son semellantes e polo tanto teñen o mesmo polinomio mínimo, polinomio característico, valores propios, determinante e traza. 

Polo tanto, eses valores e ecuacións poden servir como invariantes de isomorfismo dos grafos. No entanto, dous grafos poden posuír o mesmo conxunto de valores propios mais non ser isomorfos. Eses operadores lineares dise que son isoespectrais.

 Potencias da matriz 
Se  é a matriz de adxacencia do grafo orientado ou non  , entón a matriz  (é dicir, o produto matricial de  copias de ) ten unha interpretación interesante: o elemento  dá o número de camiños (orientados ou non) de lonxitude  dende o vértice  ata o vértice . 

Se  é o número enteiro non negativo máis pequeno, de xeito que para algúns , , o elemento  de  é positivo, entón  é a distancia entre o vértice  e o vértice . 

Un grande exemplo de como isto é útil é contar o número de triángulos nun grafo non orientado , que é exactamente a traza de  dividido por 3 ou 6 dependendo de se o grafo está orientado ou non. Dividimos por eses valores para compensar a sobrecontaxe de cada triángulo. 

Nun grafo non orientado, cada triángulo contarase dúas veces para os tres nós, porque o camiño pódese seguir no sentido horario ou antihorario: ijk ou ikj. 

A matriz de adxacencia pódese usar para determinar se o grafo é conexo ou non.

Se un grafo orientado ten unha matriz de adxacencia nilpotente (é dicir, se existe  tal que  é a matriz cero), entón é un grafo acíclico orientado.

 Notas 


 Véxase tamén 


 Outros artigos 
 Matriz laplaciana
 Matriz de incidencia

 Ligazóns externas 

 Fluffschack — an educational Java web start game demonstrating the relationship between adjacency matrices and graphs.
 Open Data Structures - Section 12.1 - AdjacencyMatrix: Representing a Graph by a Matrix, Pat Morin
 Café math : Adjacency Matrices of Graphs : Application of the adjacency matrices to the computation generating series of walks.

Categoría:Matrices
Categoría:Informática
Categoría:Teoría de grafos
Categoría:Wikipedia:Páxinas con traducións non revisadas