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.
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\).