Aplicaciones de la teoria de grafos

APLICACIONES DE LA TEORÍA DE GRAFOS

Desde sus orígenes, la Teoría de Grafos se utilizó para la resolución de juegos matemáticos, para el estudio de circuitos eléctricos y en diversas aplicaciones en una multitud de campos tan diferentes como la economía, física teórica, psicología, física nuclear, lingüística, sociología, zoología, tecnología, antropología, química, biología, etc. En la actualidad, la teoría de grafos sigue aplicándose dentro y fuera de las matemáticas. La Teoría de Grafos tiene un poderoso apoyo en los problemas de transporte. Desde un punto de vista elemental, para que sea posible el transporte o la comunicación, son necesarios puntos concretos de emisión o recepción y rutas de comunicación.

Estos dos elementos, puntos y rutas, se representan respectivamente por vértices y lados. La figura así obtenida es una red de transporte. Además los lados pueden estar orientados según si las rutas de desplazamiento necesitan definirse en un sentido obligatorio o puedan recorrerse en ambos sentidos. A menudo interesa fijar la atención en los posibles trayectos posibles entre dos vértices distintos, de tal manera que se cumplan algunas condiciones útiles como, por ejemplo:

1.- Pasar por las aristas una sola vez. El siguiente problema responde a esta idea: Un repartidor de propaganda tiene que desplazarse por una zona de ciudad depositando octavillas en los buzones. El plano de esta parte de ciudad es un grafo considerando los cruces como vértices y las calles como aristas. Al repartidor le interesa un trayecto de forma que vuelva al punto de salida después de haber pasado por todas las calles una sola vez. Por tanto el problema se reduce a encontrar un camino euleriano cerrado en el grafo que consideramos. La forma de conseguirlo es aplicar el teorema de Euler al caso particular de cada plano de ciudad. Así el problema tendrá solución cuando el grafo sea conexo y todos los vértices tengan grado par.

2.- Pasar por todos los vértices del grafo. El problema siguiente responde a este tipo: Un camión repartidor de bebidas tiene que suministrar mercancía a un almacén distribuidor situados en cada ciudad. Su problema principal es encontrar el trayecto que una todas las ciudades pasando una sola vez por cada una de ellas. Ahora el objetivo no es pasar por todas las carreteras, sino pasar una sola vez por los puntos de reparto de manera que al final se llegue el punto de partida. Este problema consiste en saber si este grafo contiene un ciclo hamiltoniano.

Cuando se presentan problemas en los que cada arista viene caracterizada por su distancia o por su capacidad para trasladar objetos por ella, la riqueza de situaciones se multiplica. Entramos de lleno en los problemas de optimización, de los que algunos ejemplos menciono a continuación: -Obtener una ruta entre dos vértices por el camino más corto. - Obtener una ruta entre dos vértices de coste mínimo. - Transportar un conjunto de objetos entre dos vértices de forma que se aproveche al máximo la capacidad de cada ruta. Ejemplos de este tipo de situaciones son: * El caso de un comerciante que necesita recorrer un grupo de ciudades alcanzando finalmente la ciudad de partida después de recorrer la menor distancia. * El caso de un autobús escolar que tiene que recoger a niños en un nº determinado de paradas situadas en distintas calles de una red urbana. El objetivo es encontrar una ruta con la menor longitud posible. Ambos problemas consisten en ver si los grafos que representan los planos admiten un circuito hamiltoniano de longitud mínima. Otro problema característico es el del conector mínimo y consiste en: Se desea construir una red de ferrocarriles que conecte n ciudades dadas, de forma que un pasajero pueda viajar desde cualquiera de ellas a cualquier otra. Si suponemos que por razones económicas la cantidad de vía a utilizar debe ser mínima, el grafo formado por las n ciudades como vértices y las vías como lados, debe ser un árbol. El problema consiste en encontrar un algoritmo eficiente que permita decidir cual de los nn-2 (fue Cayley el que lo demostró) posibles árboles que conectan estas ciudades usa la menor cantidad de vías, suponiendo que la distancia entre las ciudades es conocida.

...