El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, el cual consistía en encontrar un camino que recorriera los siete puentes del río Pregel de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos.
En 1847 se utilizó la teoría de grafos para el análisis de redes eléctricas publicando sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos, conocidas como leyes de Kirchhoff, considerado la primera aplicación de la teoría de grafos a un problema de ingeniería.
Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.
Para la administración de proyectos, utilizamos técnicas como técnica de revisión y evaluación de programas (PERT) en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.
Conceptos Claves
¿Qué es un Grafo?
Un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas.
VERTICE
Un vértice o nodo es la unidad fundamental de la que están formados los grafos, es representado como un punto dentro del grafo.
ARISTAS
Una arista o arco corresponde a una relación entre dos vértices o nodos de un grafo, se representa como líneas que unen los vértices.
ADYACENCIA
En un grafo, los vértices son adyacentes si están unidos mediante una arista.
CAMINOS
Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor.
No hay comentarios.:
Publicar un comentario