Duda pregunta 2.2 ayudantia 10

[Amegonzale]

Holaa buenas :3

Tengo una duda de esta pregunta:

Para la induccion no me esta quedando realmente claro cual es la HI a la que se refieren y cual seria el procedimiento para probar la propiedad, tengo que demostrar que eliminando un nodo del grafo se sigue cumpliendo?? ayua ;-;

muchas gracias :D

[Maratripa]

Hola! Para resolver esta pregunta se realiza inducción sobre la cantidad de nodos en el grafo n, por lo tanto, para la inducción (fuerte) se asume que todos los grafos que tienen menos que n nodos cumplen la propiedad. Luego en el paso inductivo, siempre se reduce el grafo a uno que tiene menos nodos, para que cumpla con la hipótesis.

[Amegonzale]

ahh, entonces es como sacar el nodo para llegar a algo que sabemos para dsps poder descomponer los n en lo que llegamos + algo si es necesario? :0 para demostraciones de grafos normalmente usamos induccion fuerte? muchas gracias <3

[Amegonzale]

cerre la issue sin querer xd perdon

[Maratripa]

Como siempre, el tipo de inducción que utilizamos siempre depende del ejercicio. En este caso usamos inducción fuerte porque tenemos dos casos, en uno removemos un nodo y en el otro removemos dos.

El argumento de la demostración es que si sacamos nodos controladamente: o no cambia, o sabemos de qué manera cambia. Si no cambia cuando reducimos la cantidad de nodos, se cumple directamente por la hipótesis inductiva. Si cambia, pero sabemos cómo cambia, podemos reducirlo, aplicar la hipótesis inductiva y agregar lo que sacamos.

Eso es lo que se hace en la pauta.

[Amegonzale]

oki, ty :D