Teoría de grafos
| ||||||
Teoría de Grafos. Es la rama de las matemáticas y las ciencias de la computación que estudia las propiedades de los grafos. Son un conjunto de elementos no vacíos, que se conocen como vértices y una recopilación de aristas (pares de vértices) que pueden ser o no orientados. La representación del grafo, por lo general, es una gráfica de puntos conectados por líneas.
Sumario
Definición
Un grafo es un par de conjuntos G = (V, A), donde “V” es el conjunto de vértices y “A “ es el conjunto de aristas. Los grafos pueden ser simples, conexos, completos o bipartitos.
La teoría de grafos tiene sus fundamentos en las matemáticas discretas y de las matemáticas aplicadas. Esta teoría requiere de diferentes conceptos de diversas áreas como combinatoria, álgebra, probabilidad, geometría de polígonos, aritmética y topología. Actualmente ha tenido mayor influencia en el campo de la informática, las ciencias de la computación y telecomunicaciones. Debido a la gran cantidad de aplicaciones en la optimización de recorridos, procesos, flujos, algoritmos de búsquedas, etc, se generó toda una nueva teoría que se conoce como análisis de redes.
La teoría de grafos es una mezcla de historia, cultura y soluciones a problemas complejos desde el mundo de las matemáticas. Con esta teoría se busca representar de forma visual conjuntos de datos abstractos en formas de nodos o vértices y la unión o relaciones que estas pueden tener con otros nodos a través de aristas. Gracias a esta teoría se han podido lograr grandes avances en el análisis de amplios volúmenes de datos. Hay distintas maneras de almacenar los grafos en un computador. La estructura de datos que se utilice va a depender tanto de los rasgos del grafo, como del algoritmo que se utilice. Las estructuras más empleadas son las listas y las matrices e, incluso, combinadas. Las listas se prefieren en grafos dispersos porque hacen uso eficiente de la memoria.
Historia
El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, su nombre se debe a Königsberg, la ciudad de Prusia Oriental y luego de Alemania que desde 1945 se convirtió en la ciudad rusa de Kaliningrado, 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. El trabajo de Leonhard Euler sobre el problema relativo a la geometría de la posición en 1736, se considera como el primer resultado de la teoría de grafos y topológicos en geometría (sin depender de medida alguna). Este ejemplo muestra la profunda conexión entre la teoría de grafos y la topología.
Gustav Kirchhoff en 1847, empleó la teoría de grafos para el análisis de redes eléctricas publicando sus resultados para calcular el voltaje y la corriente en los circuitos eléctricos, conocidas como leyes de Kirchhoff, es la primera aplicación de la teoría de grafos a un problema de ingeniería.
En el año 1852, Francis Guthrie planteó el problema de los cuatro colores, afirmando que utilizando solamente cuatro colores, se puede colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, no fue resuelto hasta 1976 por Kenneth Appel y Wolfgang Hake, 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.
Arthur Cayley en 1857, estudió y resolvió el problema de enumeración de los isómeros que son compuestos químicos con idéntica composición fórmula pero diferente estructura molecular. Representando cada compuesto, en éste caso hidrocarburos saturados CnH2n+2, mediante un grafo árbol donde los vértices representan átomos y las aristas la existencia de enlaces químicos.
El término grafo, proviene de la expresión inglesa graphic notation notación gráfica, Edward Frankland fue el primero en usarlo y posteriormente adoptada por Alexander Crum Brown en 1884 y que hacía referencia a la representación gráfica de los enlaces entre los átomos de una molécula.
Tipos de Grafos
Aplicaciones de la Teoría de Grafos
Al abordar aspectos básicos de la teoría de grafos se descubre que estos presentan características y prestaciones para resolver diversos tipos de problemas. Ellos brindan soluciones de dibujo computacional, perfeccionar técnicas de PERT (Program Evaluation and Review Technique –Técnica de evaluación y revisión de programas) en el área gerencial o potenciar el estudio de las relaciones en ambientes biológicos complejos.
Esta teoría permite aprovechar al máximo el potencial de las redes sociales. Con el análisis de grafos es posible comprender las relaciones, preferencias y similitudes entre los usuarios. Ha sido de utilidad para las empresas del sector, aunque se ha avanzado más en la detección de fraude bancario. Las herramientas de grafos permiten analizar miles de millones de datos de forma rápida, también pueden usarse softwares complementarios para determinar de forma eficiente comportamientos que puedan orientar a la presencia de un fraude.
