Grafos Vias

´
Proyecto de Algebra Lineal

II Término 2017 - 2018
Facultad de Ciencias Naturales y Matemáticas
Guayaquil, Agosto de 2017
1. Introducción
En matemáticas, un grafo es un conjunto de elementos llamados vértices
o nodos, conectados por medios de enlaces denominados aristas o arcos. Un
grafo, desde un punto de vista simple, permite representar una operación binaria
interna de un conjunto. Uno de los problemas más representativos de la teorı́a
de grafos es el ejemplo histórico denominado el problema de los puentes de
Königsberg, problema que fue resuelto por Leonhard Euler.
Con un poco más de rigurosidad, podemos decir que un grafo G es un par
ordenado G = (V, E), donde:
V es un conjunto de vértices o nodos, y
E es un conjunto de aristas o arcos, que relacionan estos nodos.
Consideraremos a V como un conjunto finito. Si los arcos poseen una dirección,
el grafo de denomina grafo dirigido o digrafo. En la figura I se muestra un grafo
dirigido cuyos vértices son las letras A, B, C, conectadas entre sı́.
Figura 1: Grafo con nodos A, B, C
Para un grafo se define su matriz de adyacencia como una representación

de la conexión de sus vértices. Para construir una matriz de adyacencia se debe
seguir lo siguiente:
Se crea una matriz cero, cuyas columnas y filas representan los nodos del
grafo.
1 INTRODUCCIÓN
Por cada arista que une a dos nodos, se coloca 1 al valor que hay actual-
mente en la ubicación correspondiente de la matriz.
Por ejemplo para el grafo de nuestro ejemplo, su matriz de adyacencia serı́a
X Y Z
 
X 0 1 1
Y 0 0 1
Z 1 1 0
* La primera fila indica que el nodo X se conecta con el nodo Y y con el

nodo Z.
* La segunda fila indica que el nodo Y se conecta sólo con el nodo Z.
* La tercera fila indica que el nodo Z se conecta con el nodo X y con el nodo
Y, tal como inidica la figura 1.
En un grafo se define una k-trayectoria como el camino para ir de un vérti-

ce X a un vértice Y, atravesando por k enlaces. Podemos observar en la imagen
de nuestro grafo que en él existe una 1-trayectoria de X a Y, una 1-trayectoria
de X a Z, una 1-trayectoria de Z a Y, entre otras.
Además de las 1-trayectorias, existen también las 2-trayectoria’s, es decir,

caminos de un vértice a otro vértice atravesando exactamente 2 enlaces. Por
ejemplo para ir de X a Y existe una 2-trayectoria, porque se puede ir por el
camino de X hacia Z y de Z hacia Y, atravesando exactamente 2 enlaces.
Teorema 1. Si A es la matriz de adyacencia de una gráfica simple, el elemento

ij de Ak es igual al número de k-trayectorias del vértice i al vértice j, para todo
k∈N
Lo que nos quiere decir el teorema anterior es que el elemento ij de la matriz
A nos proporciona el número de 1-trayetorias que hay del vérticie i al vértice j.
X Y Z
 
X 0 1 1
Y 0 0 1
Z 1 1 0
Se observa que hay una 1-trayectoria de Y a Z.
También nos asegura que en la matriz A2 el elemento ij nos proporciona el

número de 2-trayetorias que hay del vérticie i al vértice j.
A2 = A × A
  
0 1 1 0 1 1
A2 = 0 0 1 0 0 1
1 1 0 1 1 0
2 Ing. Angel Guale L.

1.1 Cómo elevar una matriz a la k-ésima potencia 1 INTRODUCCIÓN
 
1 1 1
A2 = 1 1 0
0 1 2
En este caso podemos observar que el elemento c12 es igual a 1 (texto en
azul), lo que indica que existe exactamente UNA 2-trayectoria que va de X
hacia X. En el gráfico podemos notar que se trata de la ruta X - Z - X. Además
como ejemplo también podemos decir que el elemento c33 , que tiene un valor
de 2 (texto en rojo), nos indica que existen exactamente dos 2-trayectorias que
van de Z a Z. Estos caminos son Z-X-Z y Z-Y-Z. Finalmente notamos que no
hay 2-trayectorias de Y a Z ya que el elemento c23 es igual a 0.
X Y Z
 
X 1 1 1
Y 1 1 0
Z 0 1 2
Por lo tanto, el problema de hallar las k-trayectorias dentro de un grafo
se resume a hallar la k-ésima potencia de la matriz A. Para hallar la k-ésima
potencia de la matriz A podemos usar diagonalización de matrices, ya que si A
es diagonalizable se tiene lo siguiente
D = C −1 AC
Donde D es una matriz diagonal semejante a A, y C una matriz invertible, que
diagonaliza a A. Si A es semejante a una matriz diagonal, entonces su k-ésima
potencia es
Ak = CDk C −1
Gracias al álgebra lineal sabemos que la matriz diagonal D se compone de
los valores propios de A y que la matriz C de vectores propios linealmente
independientes de la matriz A.
1.1. Cómo elevar una matriz a la k-ésima potencia

Para este ejemplo nos basaremos en una matriz 2×2. Mostraremos cómo usar
la diagonalización para elevar una matriz a la k-ésima potencia. Consideremos
la matriz
2 1
A=
3 4
Para nuestro ejemplo, los valores propios y bases de los espacios propios asocia-
dos a cada valor propio son:

1
λ1 = 1 BEλ1 =
−1

1
λ2 = 5 BEλ2 =
3
Las matrices D y C son

1 0 1 1
D= C=
0 5 −1 3

2 EL PROBLEMA
Es posible hallar la inversa de C, obteniendo:

3
− 14

C −1 = 4
1 1
4 4
Finalmente tenemos:
Ak = CDk C −1
3
− 14
k
k 1 1 1 0 4
A = 1 1
−1 3 0 5k 4 4
3
+ 14 5k − 14 + 14 5k

k 4
A = 3
−4 + 34 5k 1 3 k
4 + 45
2. El problema
En el año 2023, Guayaquil ha sufrido una regeneración urbana, y ciertas
avenidas han sido modificadas con el tiempo. En un mapa vial de las principales
zonas de Guayaquil se puede observar estas zonas están conectadas por carre-
teras modernas (con adoquines en los extremos) que ofrecen un acceso directo
entre las mismas. Las zonas que muestra el mapa son
Figura 2: Vı́as directas entre las principales zonas de Guayaquil, año 2023
Las Peñas (P)

Terminal Terrestre (T)
Parque Centenario (C)
Estadio Capwell(E)
Estadio Monumental (B)
C.C. San Marino (M)

3 ENTREGABLES
Parque Samanes (S)
El alcalde J. Nebot en su enésimo perı́odo de alcaldı́a desea reunir informa-

ción que considera importante acerca de estas modernas carreteras, entre uno
de sus principales requisitos, se desea la siguiente información:
¿Cuántas rutas existen entre dos zonas principales cualesquiera de las
mencionadas, atravesando exactamente por 23 carreteras directas.
¿Cuántas rutas existen entre dos zonas principales cualesquiera de las
mencionadas, atravesando exactamente por 50 carreteras directas.
El alcalde, imperioso de conocer esta información, contrata a la empresa que
usted coordina denominada Autopistas Guayaquil (AG). La empresa AG ofrece
servicios de análisis de información acerca de cualquier suceso relacionado con
carreteras en Guayaquil.
3. Entregables
Se necesita que su grupo de trabajo elabore un reporte con su solución a este
problema. El reporte es un documento con introducción, fundamento teórico,
solución, conclusiones, recomendaciones.
Para la sección solución usted deberá presentar:
El planteamiento matricial del problema (matriz de adyacencia).
El polinomio caracterı́stico de la matriz

Los valores propios de la matriz
Las bases de vectores propios asociados a cada valor propio de la matriz
La matriz D diagonal y la matriz C que diagonaliza a A
La matriz A elevado a la k-ésima potencia

La tabla de la cantidad de 23-trayectoria’s entre una zona y otra.
La tabla de la cantidad de 50-trayectoria’s entre una zona y otra.
Todo lo anterior debe estar escrito de una manera secuencial y con sentido com-
pleto. Usted puede (y probablemente debe) ayudarse utilizando herramientas
de software para resolver este problema, los mismos que deben ser descritos, y
detallar su uso, en el reporte.

Grafos Vias

Cargado por

Copyright:

Formatos disponibles

Grafos Vias

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Grafos Vias

Cargado por

Copyright:

Formatos disponibles

´

Proyecto de Algebra Lineal

Figura 1: Grafo con nodos A, B, C

Para un grafo se define su matriz de adyacencia como una representación

* La primera fila indica que el nodo X se conecta con el nodo Y y con el

En un grafo se define una k-trayectoria como el camino para ir de un vérti-

Además de las 1-trayectorias, existen también las 2-trayectoria’s, es decir,

Teorema 1. Si A es la matriz de adyacencia de una gráfica simple, el elemento

También nos asegura que en la matriz A2 el elemento ij nos proporciona el

2 Ing. Angel Guale L.

1.1. Cómo elevar una matriz a la k-ésima potencia

Las matrices D y C son

3 Ing. Angel Guale L.

Es posible hallar la inversa de C, obteniendo:

Las Peñas (P)

4 Ing. Angel Guale L.

Parque Samanes (S)

El alcalde J. Nebot en su enésimo perı́odo de alcaldı́a desea reunir informa-

El polinomio caracterı́stico de la matriz

La matriz A elevado a la k-ésima potencia

5 Ing. Angel Guale L.

También podría gustarte