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