Teoria De Grafos Y Sus Aplicaciones

REPÚBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL DE LA FUERZA ARMADA
INGENIERIA EN SISTEMAS.

PUNTO FIJO 2013
HISTORIA DE LA TEORIA DE GRAFOS
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 puentesdel río pregel (54°42′12″N 20°30′56″E) en la ciudad de Königsberg, actualmenteKaliningrado, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos. El trabajo de Leonhard Euler sobre el problema titulado Solutio problematis ad geometriam situs pertinentis1 (La solución de un problema relativo a la geometría de la posición) en 1736, es considerado el primer resultado de lateoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y latopología.
Luego, en 1847, Gustav Kirchhoff 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 loscircuitos eléctricos, conocidas como leyes de Kirchhoff, considerado la primera aplicación de la teoría de grafos a un problema de ingeniería.
En 1852 Francis Guthrie planteó el problema de los cuatro colores el cual afirma que es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que nofue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken en 1976, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.
En 1857, Arthur Cayley estudió y resolvió el problema de enumeración de los isómeros, compuestos químicos con idéntica composición (formula) perodiferente estructura molecular. Para ello represento cada compuesto, en este caso hidrocarburos saturadosCnH2n+2, mediante un grafo árbol donde los vértices representan átomos y las aristas la existencia de enlaces químicos.
El termino «grafo», proviene de la expresión «graphic notation» usada por primera vez por Edward Frankland2 y posteriormente adoptada por Alexander Crum Brown en 1884, yhacia referencia a la representación gráfica de los enlaces entre los átomos de unamolécula.
El primer libro sobre teoría de grafos fue escrito por Dénes Kőnig y publicado en 1936.3

APLICACIONES
Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas porejemplo, Dibujo computacional, en toda las áreas 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 PERT en las que se modelanlos mismos utilizando grafos y optimizando los tiempos para concretar los mismos.
La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar yabstraer relaciones complejas, de manera que la estructura social puede representarse gráficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se transmite y a quiénes.
Los grafos son importantes en el estudio de la biología y hábitat. El...