Proyecto Estructuras

1

Grafos - Rutas de Menor Costo
Sebastián Rojas – Diego Díaz – Miller Carreño


I. INTRODUCCIÓN

E

L presente documento busca responder al interrogante que
plantea el proyecto de aula de Estructuras de Datos sobre
los grafos y las rutas de menor costo desde un punto
“origen” hacía un punto de “destino”, en éste caso, teniendo
como ejercicio práctico hallar la menor ruta entre dos puntosescogidos arbitrariamente dentro de tres conjuntos de datos
que almacenan las carreteras de los estados de Texas,
Pennsylvania y California, en Estados Unidos.
“En los problemas originados en ciencias de la computación,
matemáticas, ingeniería y muchas otras disciplinas, a menudo
es necesario representar relaciones arbitrarias entre objetos
de datos. Los grafos dirigidos y los no dirigidos son modelosnaturales de tales relaciones.”- Pag, 200 Cap 6 Estructuras
de datos y algoritmos, Alfred Aho, John, Hopcroft, Jeffrey
Ullman.
Hacemos un acercamiento a los conceptos básicos sobre los
grafos, su representación en la computadora, los usos más
habituales en las diferentes ramas del conocimiento y
nombramos algunos de los algoritmos que localizan la ruta
más corta entre dos puntos. El algoritmo queproponemos ha
sido creado por nosotros a partir de la información recogida y
no incluimos algoritmos de terceros para solucionar el
ejercicio.

como por ejemplo, en arquitectura de redes móviles, circuitos
eléctricos, dibujo computacional, redes sociales, en el
modelamiento de las rutas de autobuses de una ciudad ó el que
es nuestro caso de estudio, el cálculo de la ruta de menor costo
de un punto“x” a un punto “y” dentro de tres conjuntos de
datos tomados de la colección de datos de la Universidad de
Stanford.
Tipos de grafos
Grafo Simple se compone de una arista que une dos vértices.
También se les llama grafos no dirigidos. Multigrafo se
compone de una o más aristas entre dos vértices. Grafo
dirigido es donde las aristas tienen una dirección específica.
Grafo etiquetado es aquel donde sele agrega un “peso” a las
aristas o una “etiqueta” a los vértices. Grafo aleatorio se
compone de aristas que van asociadas a una probabilidad
determinada. Hipergrafo es aquel donde cada arista va a tres
vértices o más. Grafo infinito es aquel que se compone de un
conjunto de vértices y aristas de cardinal infinito.

Representación de grafos en la computadora
Un grafo se puede representar de muchasformas en la
computadora, la estructura escogida depende de las
características del grafo y los algoritmos con los que sea
manipulado, pero por lo general se usan listas y matrices.
Cuando el grafo es disperso, son preferidas las listas por su
eficiencia en memoria, a diferencia de las matrices, que
brindan un acceso rápido pero a un costo alto de memoria.

II. MARCO TEÓRICO
Teoría de Grafos
Esun campo de estudio de las ciencias de la computación y
las matemáticas donde se busca conocer las propiedades de los
grafos, estructura que está compuesta básicamente por dos
partes, vértices y aristas, y a su vez, los grafos pueden ser
dirigidos o no dirigidos. Los grafos tienen varias aplicaciones

Cuando se usa lista de adyacencia
para su representación, cada
vértice tiene una lista con losvértices que son adyacentes a él
mismo. Ver grafo a la izquierda.
La lista de adyacencia del grafo
indicado es la siguiente:

Sebastián Rojas estudia Ingeniería de Sistemas en la Institución
Universitaria Politécnico Grancolombiano, adscrita a la Facultad de Ingeniería
y Ciencias Básicas, Sede Bogotá, COLOMBIA
(e-mail: XXXXXX@poli.edu.co).
Diego Díaz estudia Ingeniería de Sistemas en la InstituciónUniversitaria
Politécnico Grancolombiano, adscrita a la Facultad de Ingeniería y Ciencias
Básicas, Sede Bogotá, COLOMBIA
(e-mail: XXXXXXX@poli.edu.co).
Miller Carreño estudia Ingeniería de Sistemas en la Institución
Universitaria Politécnico Grancolombiano, adscrita a la Facultad de Ingeniería
y Ciencias Básicas, Sede Bogotá, COLOMBIA
(e-mail: macarrenob@poligran.edu.co).

2

Cuando se usa una...