La teoría de grafos es una mezcla extraordinaria 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 data.
En la actualidad los grafos integran parte central de un número increíble de soluciones a problemas complejos. Son uno de los componentes fundamentales de la analítica social, relaciones entre personas y más recientemente se han utilizado sus propiedades para incrementar la eficiencia en la lucha contra el blanqueo de capitales y el fraude bancario.
Para empezar a navegar en el mar de los grafos, conozcamos un poco sobre la historia de la teoría de grafos.
Historia de la teoría de grafos
Los orígenes que fundamentan la teoría de grafos nacen con un estudio realizado por el matemático suizo Leonhard Euler en 1736. La investigación de Euler trataba de resolver el mítico problema de los puentes de Konisberg.
Este problema consistía en obtener una ruta eficiente para cruzar todos los puentes de la ciudad, cruzándolos una sola vez. Las conclusiones de Euler demostraron su improbabilidad, pero fue el punto de partida a un número increíble de estudios.
Entre los estudios más relevantes que le han dado forma a la teoría de grafos como la conocemos hoy se encuentran las investigaciones de Gustav Kirchhoff (1845) con los circuitos de cálculo de voltaje y Francis Guthrie (1852) con la presentación de la hipótesis de los cuatros colores.
Este problema plantea la posibilidad de llenar un mapa geográfico solo con cuatro colores, de forma que países vecinos no compartan nunca un mismo color. El problema fue resuelto casi un siglo después por Kenneth Appel y Wolfang Haken, donde plantearon conceptos fundamentales de los grafos.
Continuemos profundizando sobre los Conceptos de esta teoría.
Principales conceptos de la teoría de grafos
Debemos tener presentes que existen diferentes tipos de grafos. Dependiendo del tipo de grafo podemos lograr obtener diferentes características que podemos implementar en nuestros proyectos. Los grafos simples o multigrafos son composiciones de complejidad ligera en las que los conjuntos de nodos pueden estar unidos por varias aristas.
Los grafos también tienen propiedades especiales que indican orientaciones, estas características se encuentran en los grafos o multígrafos dirigidos. En este tipo de grafos cuentan con la particularidad de que sus aristas vinculan a los nodos en una sola dirección. Además de estos conceptos también podemos conseguir grafos, completos, conexos y etiquetados.
Estructura de datos en la representación de grafos
Uno de los puntos más importantes que integra la teoría de grafos son sus estructuras de representación. Gracias a estas estructuras podemos aprovechar al máximo la visualización de los conjuntos de datos para analizar se forma simple los elementos para tomar decisiones.
Entre las estructuras más sencillas e implementadas se encuentran las listas y las matrices. Aunque frecuentemente existen modelos combinados entre ambas.
Una estructura de lista es donde las aristas son representadas con un vector de pares ordenados, en el caso de que el grafo sea dirigido, donde cada par representa a una de las aristas.
Por su parte las listas de adyacencia, ocurre que cada vértice tiene una lista de vértices los cuales son adyacentes al mismo nodo. Esto causa redundancia en un grafo no dirigido, pero este tipo de listas ofrece una gran rapidez en las búsquedas.
En las estructuras de datos de datos descritas la idea es asociar cada uno de los vértices del grafo con una lista que contenga al resto de los vértices adyacentes. De esta forma solo se reservará memoria para los arcos adyacentes.
Ciclos y caminos hamiltonianos
En la teoría de grafos se contempla un proceso conocido como ciclo. Este es una sucesión de aristas adyacentes donde no se recorre dos veces la misma arista y posteriormente regresa a un punto inicial. Por su parte un ciclo hamiltoniano es el que recorre todos los vértices exactamente una sola vez, exceptuando al vértice del que parte y al cual llega.
Estos últimos ciclos descritos son difíciles de conseguir debido a que no se conocen métodos generales para hallarlos en tiempo polinómico, teniendo que realizarse búsquedas a fuerza bruta donde se combinan todas las opciones y caminos probables. Este método en cantidades grandes de datos suele ser bastante lento y costoso.
Aplicaciones de la teoría de grafos
Al abordar aspectos básicos de la teoría de grafos podemos descubrir que estos nos presentan características y prestaciones para resolver diversos tipos de problemas. Con ellos podemos brindar soluciones de dibujo computacional, perfeccionar técnicas de PERT en el área gerencial o potenciar el estudio de las relaciones en ambientes biológicos complejos.
Además con esta teoría se ha podido aprovechar el 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. Esto ha sido de una utilidad gigantesca para las empresas del sector. Aunque el sector más prominente en el cual se ha avanzado es 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.
Esperamos que esta información te sea útil conociendo el mundo de los grafos.
