Matrices Y Aplicaciones2 F20 1

Matrices y aplicaciones

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 plano de arriba.
Se dice que los habitantes de la ciudad seentretení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
pasardos veces por el mismo puente.

20

Grafo que modela la situación

3

Matrices y grafos
Este tipo de objeto matemático se conoce con el nombre de
grafo: a los puntos se les llama vértices y aristas a las líneas que
los unen.
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 lospuentes: siete
en total.
El grafo a su vez puede ser representado mediante una matriz
conocida como matriz de adyacencia, la cual denotaremos
por A. Cada elemento a ij 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án unidos por lo menos con una arista
se dice que ellos son adyacentes.
Hemos etiquetado los vértices con los números del 1 al4,
como se muestra en la figura.
La matriz de adyacencia del grafo de la figura es:

0 1 1 1
A=

1 0 2 2
1 2 0 0
1 2 0 0

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 encuentrajustamente el elemento a24=2. El valor
de a24 indica que existen dos conexiones (puentes) que unen
a 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 A2.
3 4 2 2
A 2=

4 9 1 1
2 1 5 5
2 1 5

5

¿Cómo interpretamos ahora las entradas de la matriz?

Fascículo 20 • Matrices y aplicaciones

154

1
2

Grafo que modela la situación
4

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 y1-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 otorgamos a los otros dos caminos.
Si queremos ir del punto 3 al 4, tenemos a disposición 5
caminos de longitud 2. Una escogencia es pasar por el vértice
2, pero tenemos dos puentes, cada unocorresponde a una
opción. Una vez llegados al vértice 2, nuevamente tenemos Uno de los puentes de Köningsberg (hoy Kaliningrado)
dos puentes, es decir, dos alternativas. En consecuencia, si
que todavía se encuentra en la actualidad.
Fuente: www.matheory.info/ konigsberg
decidimos ir desde 3 a 4 pasando por 2, tenemos 2 x 2 = 4
caminos posibles. El quinto camino corresponde a salir de 3,
pasar por 1 yarribar a 4.
3
En general, cada entrada a ij de la matriz A 2 representa el
número de rutas o caminos de longitud 2 que existen entre
los vértices i y j.

2
¿Podrías encontrar las 9 rutas posibles (de
longitud 2) para, saliendo de 2, regresar al
lugar de partida cruzando dos puentes
diferentes o dos veces el mismo puente?

En forma análoga podemos estudiar el significado de las
entradas de las...