Reflexiones y aplicaciones

Inducción matemática

Como ya hemos visto, este principio es una herramienta muy útil y poderosa en las matemáticas en general. El tema que hemos trabajado pertenece a la teoría de gráficas, la cual hace uso constante de este principio. Recordemos nuevamente qué es la inducción matemática y en qué consiste.

Principio de inducción matemática

Consiste en establecer, sin lugar a dudas, que una propiedad se cumple para cualquier número natural que sea mayor que o igual a un número natural inicial. Esto se consigue garantizando que:

1. La propiedad se cumple para el número inicial.

2. Suponiendo, o dando por hecho, que la propiedad se cumple para un número natural arbitrario \(n\), podemos garantizar que se cumplirá para \(n+1\).

Aplicando este principio podemos comprobar, y así estar seguros, de que el procedimiento que hemos desarrollado en verdad nos da como resultado una configuración óptima en términos del problema, ya sea de minimización o maximización.

Estrategia equivocada

Para realizar lo anterior, la primera idea que viene a nuestra mente es verificar directamente que el procedimiento funciona correctamente para \(n=2\), y luego ver si para una configuración cualquiera de \(n\) puntos, donde el procedimiento nos da la solución requerida, podemos llegar partiendo de ella a la solución correcta para \(m=n+1\) puntos.

Sin embargo, esta primera idea que vino a nuestra mente no va a funcionar. ¿Por qué?

¿Cómo es el procedimiento para enlazar dos puntos A y B? Sin lugar a dudas funciona porque comenzamos por A y lo enlazamos con B o al revés. No hay más. Obtenemos la solución única y óptima a la vez. Lo que quiere decir que el primer paso de la inducción matemática es exitoso. No tenemos problemas ahí.

El problema viene porque, en general, es decir, en todos los casos habidos y por haber, no podemos partir de una configuración óptima para \(n\) puntos para obtener la correspondiente pero para \(n+1\) puntos.

Problema

Piensa y diseña un escenario en el que tengas una solución óptima para \(n\) puntos. Luego añade un punto junto con los costos de los enlaces de este punto al resto de los puntos, de tal forma que enlazando este último punto con el enlace de costo óptimo no resulte todo ello en una solución óptima.

Pista: Puedes tomar \(n=2\) con un enlace costoso, pensado en el problema de minimización.

A continuación incluimos una escena del mismo tipo que las anteriores. Puedes variar el número de puntos \(N\) entre 2 y 5. Si encuentras una solución de costo total mínimo e incrementas el valor de \(N\), verás que tienes que eliminar todos los enlaces que escogiste para obtener la nueva solución de costo total mínimo.

Al resolver el problema podemos ver claramente que no podemos aplicar la inducción matemática a partir de cualquier número de puntos ya enlazados.

Lo que sí podemos hacer es verificar que para cualquier número natural \(N\) de puntos, el procedimiento funciona usando la inducción para ir de \(n=2\) hasta \(n=N\).