Teoria De Grafos

INTRODUCCION

El nacimiento del concepto GRAFOS se puede situar, por el año 1730, cuando Euler (matemático) se convirtió en el padre de la Teoría de Grafos al modelar un famoso problema no resuelto, llamado el "problema de los puentes de Königsberg".

Un río con dos islas atraviesa la ciudad. Las islas están unidas, entre si y con las orillas, a través de siete puentes. El problema consistía en establecer un recorrido que pasara una y solo una vez por cada uno de los siete puentes, partiendo de cualquier punto y regresando al mismo lugar.

Para probar que no era posible, Euler sustituyó cada zona de partida por un punto y cada puente por un arco, creando así un grafo, el primer grafo, diseñado para resolver un problema.

Mostrar que el problema no tiene solución equivale a mostrar que el grafo no puede ser recorrido según criterios determinados.

Problema genérico: dado un grafo (con múltiples líneas entre pares de puntos) encontrar un camino que recorra el grafo pasando por cada arista exactamente una vez.

Solución: El grafo debe se conexo, y en cada punto deben incidir un número par de líneas. Esta condición es suficiente para definir lo que se llama un ciclo euleriano.

A partir de Euler el modelado mediante grafos fue desarrollando esta metodología hasta convertirse en la actualidad, en una herramienta de trabajo para ciencias tan diferentes como la Física, la Química, la Sicosociología, la Economía, la Lingüística, etc. La teoría de grafos está íntimamente relacionada con varias ramas de la Matemáticas como por ejemplo la Teoría de Conjuntos, el Análisis Numérico, Probabilidad, Topología, etc. y es la base conceptual en el tratamiento de problemas combinatorios.

La eficacia de los grafos se basa en su gran poderío de abstracción y la muy clara representación de cualquier relación (de orden, precedencia, etc.) lo que facilita enormemente tanto la fase de modelado como de resolución del problema. Gracias a la Teoría de Grafos se han desarrollado una gran variedad de algoritmos y métodos de resolución eficaces que nos permiten tomar una mejor decisión.

Teoría de grafos

“Los grafos son objetos de matemáticas discretas, se componen de nodos o vértices, y pueden ser redes de cualquier cosa (personas, computadoras, vialidades, antenas de telefonía, aeropuertos, etc.); son abstracciones matemáticas de alguna entidad que tiene alguna propiedad o función específica, éstos a su vez, se conectan entre aristas.

“El tener una intersección significa que son, por lo menos, dos las calles que se unen en la misma; si son personas, podrían ser quizá, las que coinciden físicamente durante un día en el mismo lugar, esto serviría, por ejemplo, para un estudio epidemiológico que oriente a cerca de quién podría contagiar a quién en dada situación; es decir son redes de todo tipo”, explicó la investigadora, “así sean computadoras, éstos podrían ser enlaces de telecomunicación entre las computadoras o podrían ser los ruteadores que manejan todo el tráfico de Internet”.

En la menciona teoría, los nodos y las aristas de cada grafo tienen diferentes propiedades; todo lo anterior representa el área de estudio de la doctora Elisa Schaeffer, quien al 2010, cumplió 10 años estudiando diferentes tipos de grafos. Con los primeros con los que trabajó la investigadora del CIIDIT, fue con los llamados grafos árboles, los cuales tienen un nodo raíz del cual se desprenden nodos hijos, y así sucesivamente.

“La cuestión es que si coloco todos los datos en una lista y los voy buscando, tardaré una cantidad de tiempo que es proporcional a la cantidad de elementos que tenga. En cambio, si los coloco en el grafo de árbol y los ordeno en base a una regla, cuando realice la búsqueda, está va a ser más rápida”, explicó Elisa Schaeffer.

En las ciencias matemáticas, computación y disciplinas relacionadas, un algoritmo es un conjunto preescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generan dudas a quien lo ejecuta. Siguiendo los pasos, se llega a un estado final y se obtiene una solución.

Muchos problemas de planificación de rutas de distribución han encontrado alternativas de solución en la teoría de grafos, dado que se facilita su modelamiento por la similaridad conceptual de las estructuras. Al igual que las rutas de distribución, los grafos son estructuras discretas que constan de vértices conectados mediante arcos. Un grafo dirigido (figura 1) se denota por G = (V, A), donde V es un conjunto no vacío de elementos

...