La Teoría de Grafos y la TGS

1. TEORIA DE GRAFOS

1.1 ¿QUÉ ES LA TEORÍA DE GRAFOS?
La teoría de grafos es llamada también teoría de las gráficas, es un campo de estudio de las matemáticas y las ciencias de la computación, esta es la que estudia las propiedades de los grafos o gráficas, estructuras que constan de dos partes (el conjunto de vértices, nodos o puntos, y el conjunto de aristas, líneas o lados), que pueden serorientados o no.
Esta teoría es una rama de las matemáticas discretas y aplicadas, y es una disciplina que unifica diversas áreas como combinatoria, álgebra, probabilidad, geometría de polígonos ,aritmética y topología.
Actualmente ha tenido mayor preponderancia en el campo de la informática, las ciencias de la computación y telecomunicaciones.

1.2. EJEMPLOS

Grafica 1Grafica 2

Grafica 3

2. UN POCO DE LA HISTORIA

Su inicio fue en el s. XVlll con los puentes de Königsberg actualmente Kaliningrado, el cual consistía en encontrar un camino que pudiera recorrer los siete puentes del río Pregel sin cruzar más de una vez uno de ellos.
Se considera que el trabajo de Leonhard Euler en 1736 sobre el problema titulado Solutio problematis ad geometriam situspertinentis (La solución de un problema relativo a la geometría de la posición); fue el primer resultado de la Teoria de Grafos, también se considera uno de los primeros resultados Topologicos en geometría (que no depende de ninguna medida).
En 1847 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos.
En 1852 FrancisGuthrie planteó el problema de los cuatro colores que plantea si 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 no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticosdefinieron 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) pero diferente estructura molecular. Para ello represento cada compuesto, en este caso hidrocarburos saturados CnH2n+2, mediante un grafo árbol donde los vértices representan átomos y lasaristas la existencia de enlaces químicos. El término «grafo», proviene de la expresión «graphic notation» usada por primera vez por Edward Frankland2 y posteriormente adoptada por Alexander Crum Brown en 1884, y hacía referencia a la representación gráfica de los enlaces entre los átomos de una molécula.
El primer libro sobre esta teoría fue escrito por Dénes Konig y publicado en 1936.



3.TEOREMA DE LOS CUATRO COLORES

Mapa coloreado con 4-colores

Grafo dual asociado al mapa con una 4-vértice coloración.

Lo importante no es la forma de cada país, sino saber qué país toca al otro. En este caso los vértices son los países y las aristas conectan los que justamente son adyacentes. Y lo ideal es atribuirle a cada vértice un color distinto del que sus vecinos tienen.

4. ¿ENQUE SE PUEDE USAR ESTA TEORÍA?

Gracias a dicha teoría se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura.
Esta tiene varias aplicaciones o usos, por ejemplo:
Dibujo computacional, en todas las áreas de Ingeniería.
Para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el quepodemos 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 modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.
Pero la teoría de grafos no solo ha sido útil en las ingenierías y algoritmos, también ha servido de...