Matrices y grafos

MATRICES Y GRAFOS

Javier Sánchez Sánchez

Ingeniería Mecatrónica
Academia de Matemáticas
Algebra Lineal
Ana María López Salgado
Centro de Enseñanza Técnica Industrial
Plantel: Colomos
Turno: Vespertino

Fecha: 16 de marzo de 2010

MATRICES Y GRAFOS

Introducción
1. Definición de matriz
Una matriz es un arreglo rectangular de objetos distribuidos en m renglones y n columnas, yse representa como:

En el caso de una matriz que tiene el mismo número de renglones que de columnas, se dice que la matriz es cuadrada.

2. Multiplicación de matrices
Sean A y B dos matrices de mxn y nxp respectivamente, tales que el número de columnas de A coincida con el número de renglones de B; entonces se define el producto entre matrices como la matriz C de mxr que resulta de efectuarel siguiente procedimiento:

C=cijmxrdonde cada cij=k=1naikbkj

Cuando dos matrices se pueden multiplicar, se dice que son matrices conformables.
En el producto de matrices no existe la conmutatividad.

3. Potencia de una matriz
Sea A una matriz de mxm con elementos en C, y sea n є N. Se llama potencia enésima de A, y se representa con:

a) A0=Im
b) An=AAn-1, n≥1

Descripción delos Grafos
En la imagen de abajo se muestra un elemento matemático llamado grafo, a los puntos se le llaman vértices y aristas a las líneas que los unen.
El grafo a su vez puede ser representado mediante una matriz conocida como matriz de adyacencia, la denotaremos A. Cada elemento de la matriz indica el número de aristas que enlazan al vértice i con el vértice j. Cuando dos vértices estánunidos por lo menos por una arista se dice que ellos son adyacentes.

Desarrollo
La antigua ciudad de Königsberg (hoy Kaliningrado) ubicada en lo que era Prusia Oriental, se encuentra atravesada por el río Pregel (cuyo nombre actual es Pregolya). La ciudad es famosa por sus puentes, ya que cuenta con 7 que unen ambas márgenes del río Pregel con dos de sus islas, tal como se puede ver en el planode arriba. Se dice que los habitantes de la ciudad se entretenían tratando de encontrar una ruta para pasear con la condición de cruzar cada uno de los siete puentes y hacerlo sólo una vez. Como habían intentado hacerlo infructuosamente la mayoría pensaba que tal paseo era imposible.
Euler resolvió el problema representando la situación mediante un modelo gráfico. La solución dada en 1736,mostraba la imposibilidad de cruzar los siete puentes sin pasar dos veces por el mismo puente.

Los puntos azules en el grafo (vértices) representan las dos islas y las dos orillas del río; mientras que las líneas que enlazan a los puntos (aristas) representan los puentes: siete en total.
Hemos etiquetado los vértices con los números del 1 al 4, como se muestra en la figura. La matriz de adyacenciadel grafo de la figura es:

Cada fila de la matriz está asociada con un vértice del grafo. Lo mismo ocurre con las columnas. Así, por ejemplo, la fila 2 está asociada con el vértice que lleva la etiqueta 2; y la columna cuatro con el vértice 4. En el cruce de la fila 2 con la columna 4 se encuentra justamente el elemento a24=2. El valor de a24 indica que existen dos conexiones (puentes) que unena dichos vértices. En consecuencia, el elemento simétrico a42 también debe ser 2, ya que si hay dos puentes que enlazan a 2 con 4, esos mismos puentes comunican a 4 con 2. Si miramos la matriz A, efectivamente ocurre esto (A es una matriz simétrica).
La matriz A puede multiplicarse por sí misma, obteniéndose la matriz AA la cual se denota A^2.

¿Cómo interpretamos ahora las entradas de lamatriz?
Por ejemplo, ¿qué significa que a11 valga 3 ó que a34 tome el valor 5?
a11=3, significa que hay tres caminos de longitud 2 del vértice 1 a él mismo. Estos caminos son: 1-4-1; 1-2-1 y 1-3-1. Así, el camino 1-4-1 indica que salimos de 1, cruzamos el puente que lleva a 4 y nos devolvemos a 1 por ese mismo puente; es decir, hemos hecho un recorrido de longitud 2. Similar interpretación le...