Matriz de adyacencia

Teoria de grafos

Diego HuertasDavid LopezAndrés Torres

Índice

1. Matriz de adyacencia.

2. Espectro de un grafo

3. Espectro de algunos grafos

4. Determinantes

5. Cotas

Matriz de adyacencia

• Es una matriz booleana que representa las conceiones entre pares de vertices.
• La matriz de adyacencia de un grafo es simétrica.
• Si un vértice es aislado entonces la correspondiente fila (columna) esta compuesta sólo por ceros.
• Si el grafo es simple entonces la matriz de adyacencia contiene solo ceros y unos (matriz binaria) y la diagonal esta compuesta sólo por ceros.

Matriz de adyacencia

• La matriz de adyacencia de un dígrafo no es simétrica.
• Es una matriz binaria.
• El número de unos que aparecen en una fila es igual al grado de salida del correspondiente vértice y el número de unos que aparecen en una determinada columna es igual al grado de entrada del correspondiente vértice.

• Paso 1: Se le asignan un orden arbitrario a los vértices.
• Paso 2: Se construye una matriz de dimensión n*n, cardinalidad (número de vértices) por cardinalidad (número de vértices)
• Paso 3: En la posición I j-ésima se coloca 1 si el vértice i es adyacente al vértice j; 0 en el otro caso

Algoritmo para construir la matriz de adyacencia de un grafo

Se obtiene

Existe una matriz de adyacencia única para cada grafo (sin considerar las permutaciones de filas o columnas), y viceversa

Finalmente, se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de nodos (elementos).

Ejemplo

La siguiente tabla muestra dos grafos y su respectiva matriz de adyacencia. Note que en el primer caso, como se trata de un grafo no dirigido, la matriz obtenida es simétrica

• Para un grafo no dirigido la matriz de adyacencia es simétrica.
• El número de caminos Ci,j(k), atravesando k aristas desde el nodo i al nodo j, viene dado por un elemento de la potencia k-ésima de la matriz de adyacencia:

Propiedades de la matriz de adyacencia

Espectro de un grafos

El espectro Sp(▲) el multiconjunto de los autovalores de A.

Para hayar el espectro de un grafo se debe encontrar las raices del pólinomio caracteristico de la matriz adyacente al grafo (valores propios).

La energia de un grafo G se define como la suma de los valores absolutos de sus autovalores. Esto es,

energia de un grafo

Para hayar la energia de un grafo se debe encontrar las raices del pólinomio caracteristico de la matriz adyacente al grafo (valores propios) y sumarlos en su valor absoluto.

Ejemplo

El espectro y la energia de la siguiente matriz se encuentran mediante los valores propios de la matriz

El polinomio caracteristico es:

Los valores propios son:

El espectro es:

La energia es: 16

• El determinante de una matriz siempre es un número real y únicamente lo podremos calcular para matrices cuadradas.
• El determinante de una matriz cuadrada, se obtiene de restar la multiplicación de los elementos de la diagonal principal de la matriz y la multiplicación de los elementos de la diagonal secundaria de la misma matriz.
• Para poder realizar este cálculo necesitamos una matriz cuadrada de orden m x n, donde m son las filas y n las columnas, siendo siempre m=n. Esto es lo que llamamos dimensión de la matriz. Para matrices de orden superior a 2 x 2, el cálculo se realiza mediante las reglas de Laplace o Sarrus.

Determinantes

Orden inferior

Una matriz cuadrada de orden uno El valor del determinante es igual al unico termino de la matriz

El caso de matrices de orden inferior (orden 1, 2 o 3) es muy simple y su determinante se calcula con sencillas reglas conocidas. Dichas reglas son también deducibles del teorema de Laplace.

El determinante de una matriz de orden 2 Se calculan con la siguiente formula

Orden inferior

Dada una matriz de orden 3 El determinante de una matriz de orden 3 se calcula mediante la regla de Sarrus:

El caso de matrices de orden inferior (orden 1, 2 o 3) es muy simple y su determinante se calcula con sencillas reglas conocidas. Dichas reglas son también deducibles del teorema de Laplace.

El determinante de orden n, puede calcularse mediante el teorema de Laplace a partir de una fila o columna, reduciendo el problema al cálculo de n determinantes de orden n-1.

Orden superior

El cofactor de un elemento 𝑎_𝑖𝑗 de la matriz es el determinante de la matriz que se obtiene al eliminar la fila y columna correspondiente a dicho elemento, y multiplicándolo por 〖(−1)〗^(𝑖+𝑗) donde i es el número de fila y j el número de columna.

La suma de todos los productos de los elementos de una fila (o columna) cualquiera multiplicados por sus cofactores es igual al determinante.

Para ello se toma una fila o columna cualquiera, multiplicando cada elemento por su cofactor.

Mediante esta regla podremos calcular fácilmente el determinante de matrices de dimensiones iguales y mayores a 3 x 3. De esta forma, simplificamos el cálculo de las matrices de dimensiones elevadas al utilizar la suma de los determinantes de las matrices menores en las que se descompone la matriz inicial.

regla de laplace

Esta regla nos permite también calcular determinantes de matrices cuadradas de orden 3 y solamente de este orden. Para calcular los determinantes de esta manera debemos dibujar dos conjuntos de dos triángulos opuestos a través de los elementos que componen la matriz. El primer conjunto tendrá dos triángulos que deben cruzar la diagonal principal, mientras que el segundo conjunto tendrá otros dos triángulos que crucen la diagonal secundaria.

regla de Sarrus

Matriz de dimencion 3x3 Calculamos el determinante aplicando Sarrus

ejemplo

=3×(−1)×5+2×0×2+7×(−4)×(−3)−(−3)×(−1)×2−2×7×5−0×(−4)×3=−15+84−6−70=−7

• El determinante del producto de dos matrices será siempre el mismo que el resultado del producto de sus determinantes.
• El determinante cambia de signo si se intercambian dos filas o columnas cualesquiera de una matriz.

propiedades de un determinante

• El determinante de una matriz siempre es igual al de su matriz traspuesta.
• El determinante de una matriz será siempre cero (nulo) si la matriz contiene dos filas o columnas iguales, si los elementos de una fila o columna son todo ceros o si los elementos de una fila o columna son una combinación lineal de las demás.

• El determinante de una matriz quedará multiplicado por un número real si se multiplican todos los elementos de una fila o columna por ese mismo número.
• El determinante de una matriz no se altera si sumamos a una fila o columna un múltiplo de otra fila o columna.

Algunas utilidades de los determinantes

• Nos permiten estudiar la posición relativa de rectas y planos (sabemos que la posición relativa que ocupan rectas y planos se puede calcular a través de sistemas de ecuaciones lineales, que son resueltas por determinantes de matrices).
• Podemos obtener la ecuación implícita de un plano (a través de un determinante nulo).

• Son un instrumento para calcular áreas de figuras en el plano.

• Son útiles para calcular el volumen de los paralelepípedos.

Sean los valores propios y , entonces,

Cotas

Dado que la suma de los valores propios siempre es 0, se puede deducir que 0 es una cota superior para el menor valor propio y su vez es una cota inferir para el mayor valor propio.

¡Gracias!