5.1 Matrices
La teoría espectral de matrices se utiliza ampliamente en diversos temas de la teoría de grafos. En particular, se ha utilizado recientemente para el estudio y caracterización de grafos distancia-regulares, esquemas de asociación, y sus aplicaciones en teoría de códigos completamente regulares. Pero en este estudio nos vamos a centrar en la utilización de matrices para averiguar la adyacencia de un grafo y poder crear matrices a partir de grafos y viceversa.
Partimos de que una matriz es un conjunto de números formado bidimensionalmente. Como puede definirse tanto el producto como la suma de matrices, normalmente se dice que son elementos de un anillo. Las matrices se representan a partir de una letra mayúscula (A, B, ...) y sus elementos han de estar representados con la misma letra pero en minúscula (a, b, ...), con su doble subíndice donde el primero indica la fila y el segundo la columna a la que pertenece.
La adyacencia de un grafo
La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la correspondiente fila o columna está compuesta únicamente por ceros. Si el grafo es simple entonces la matriz de adyacencia contiene solamente ceros y , tratándose de una matriz binaria, unos, y la diagonal está compuesta sólo por ceros.
Construcción de la matriz a través de un grafo
Se crea una matriz vacía, cuyas columnas y filas representan los vértices del grafo.
Para cada borde que conecta dos vértices, se agrega 1 al valor actual en la posición correspondiente en la matriz.
Si este borde es un bucle y el grafo no está dirigido, agregue 1 o 2 (dependiendo de la convención utilizada).
Si el grafo tiene un peso, entonces en lugar de 1, se suma el peso del borde opuesto.
Finalmente se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de vértices (elementos). Hay una matriz de afinidad única para cada grafo (independientemente de las permutaciones de fila o columna) y viceversa.
Matriz de adyacencia: Definición
Una matriz de adyacencia es una matriz que contiene los elementos 0 y 1, donde 1 indica un camino desde el vértice que ocupa la fila hasta el vértice que ocupa la columna, y 0 indica que no existe tal camino.
Matriz de incidencia: Definición
El grafo representa una matriz A (arista) con V (vértice), donde [arista,
vertex] contiene información de borde (1 - conectado, 0 - no conectado)
