Teoría de Grafos y Análisis de Redes

En un post anterior, comenté sobre el posibilidades de utilizar el Análisis Envolvente de Datos - DEA para realizar comparaciones de rendimientos combinados. Hoy voy a hablar un poco sobre otra rama de las matemáticas que puede tener aplicabilidad en la optimización de un negocio: la teoría de grafos.

La teoría de grafos estudia la relación entre los individuos dentro de una red, a través de estructuras llamadas grafos. Un gráfico no es más que un conjunto de puntos (que pueden ser individuos, instalaciones, países...) que contienen relaciones entre ellos. Por ejemplo, en una red de personas, yo, Fernando, puedo ser amigo de Jean y Paulo, que también son amigos entre sí, y Jean puede ser el único amigo de Bruna. Este es un ejemplo de un gráfico, que se puede representar gráficamente como se muestra en la Figura 1.

Figura 1 – Representación de un gráfico de ejemplo de una red de individuos

Fuente: OIT

La gráfica también se puede representar mediante una matriz cuadrada, llamada matriz de correspondencias, donde el número 0 representa la ausencia de relación, y el número 1 en este caso (pueden ser otros, en caso de que existan pesos para las relaciones) representa la presencia de un vínculo.

Figura 2 – Representación del mismo gráfico a través de la Matriz de Correspondencia

Fuente: OIT

Uno de los primeros casos en los que se registra el uso de la teoría de grafos es en el problema de los puentes en Königsberg, una ciudad que tenía cuatro islas conectadas por siete puentes (como se muestra en la Figura 3). El matemático Leonhard Euller demostró mediante la teoría de grafos que era imposible atravesar los siete puentes una vez y volver a la misma isla de origen sin repetir al menos uno de los caminos.

Figura 3 – Los puentes de Königsberg

Fuente: OIT

Comprobar una simple red de amigos o islas conectadas por puentes puede no parecer tan interesante, pero piensa que el mismo tipo de representación se puede aplicar a redes de centros de distribución, aeropuertos o puertos, redes de suministro, clientes o incluso personas dentro de una empresa.

La parte más interesante de la teoría de grafos es poder comprender qué individuos son más influyentes dentro de una red, a través de varias medidas de centralidad. Estos pueden evaluar qué vértices (el nombre técnico dado a cada individuo) del gráfico son más influyentes, de varias maneras. Por ejemplo, es posible determinar el individuo más influyente en función del número total de relaciones (que se denominan aristas) que tiene con otros vértices de la red, lo que sería el denominado grado de centralidad. También es posible analizar cuál es el vértice más presente en los caminos más cortos entre dos vértices cualesquiera, a través de la medida de centralidad de intermediación. Estos son solo algunos ejemplos de mediciones que se pueden realizar para comprender la influencia de las personas dentro de una red. En las referencias a continuación, puede ver cada uno de ellos con más detalle.

Existen algunos programas de software gratuitos que pueden generar informes que calculan estas medidas y/o representan gráficamente una red, con múltiples opciones de filtrado y visualización. Uno de ellos es el UCINET, que viene con Net Draw (que muestra la representación gráfica del gráfico) y es muy simple de usar. Basta con crear una matriz de correspondencia en el propio programa o importar una desde Excel, y generar los análisis deseados.

Con los análisis correctos, la teoría de grafos puede ser muy útil para problemas de enrutamiento y optimización de redes en general, siendo un conocimiento muy agregado para el profesional de la logística.

Referencias

<http://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf>

<http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html>

<http://objdig.ufrj.br/60/teses/coppe_m/LeandroQuintanilhaDeFreitas.pdf>