El problema de la aerolínea

Una aerolínea desea saber cuántos aviones necesita tener a su disposición para cubrir todas las rutas entre quince aeropuertos distribuidos de tal forma que forman un polígono irregular de quince lados. Las condiciones bajo las que han decidido que se hará el análisis son las siguientes:

• Cada avión realizará el vuelo de ida y el de regreso entre dos aeropuertos por lo que solo es necesario uno para cada ruta, y
• No habrá ruta de vuelo entre dos aeropuertos que se encuentren contiguos no importando la distancia que los separe.

• Los puntos (A, B, C, D, E) representan cada uno de los aeropuertos y las lineas punteadas las conexiones entre ellos.
• Las líneas verdes representan las rutas sobre las cuales trabajará la aerolinea y por ello necesita un avión para cada una.
• Las líneas rojas corresponden a conexiones sobre las cuales no habrá vuelos entre aeropuertos.

Para hallar la solución al problema basta solo con contar la cantidad de líneas verdes que hay, las cuales corresponden a cada una de las rutas a cubrir. Para este ejemplo es sencillo pero... como habrás notado, a la aerolínea no le interesa la cantidad de aviones necesaria para cinco sino para quince aeropuertos bajo las mismas condiciones planteadas. Aún así, a partir de este ejemplo es posible comenzar a generalizar el planteamiento que nos interesa.