Autor Tema: Probar que en todo árbol, [texx]|V|=|A|+1[/texx]

0 Usuarios y 2 Visitantes están viendo este tema.

20 Febrero, 2020, 07:20 am
Respuesta #20

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Tengo una pregunta que es por qué en tu prueba, Luis, del mensaje #3, decís construir un árbol con un vértice menos sin ninguna justificación, y en la prueba del profesor hay que justificar.

¡Hey! Mi mensaje #3 viene después del #1 donde he esbozado el cómo se construye ese árbol con un vértice menos:

Por ser un árbol tiene un vértice de grado uno. Si retiras ese vértices y su arista adyacente, tienes un nuevo árbol con una arista menos y un vértice menos: aplica inducción..

Lo que digo en el #3 es complementario a esto, como contestación a tu respuesta #2.

Para que no queden dudas mi prueba completa sería:

Teorema: Todo árbol \( T_n \) con \( |V(T_n)|=n \) (de \( n \) vértices) cumple \( |V(T_n)|=|A(T_n)|+1 \).

Demostración por inducción en el número de vértices:

Caso base \( n=2 \). Es inmediato que un árbol \( T_2 \) de dos vértices tiene \( 1 \) arista que los conecta. Por tanto \( |V(T_2)|=2=1+1=|A(T_2)|+1 \).

Paso inductivo:

Hipótesis: Todo árbol \( T_n \) con \( |V(T_n)|=n \) (de \( n \) vértices) cumple \( |V(T_n)|=|A(T_n)|+1 \).

Tesis: Todo árbol \( T_{n+1} \) con \( V(T_{n+1})=n+1 \) (de \( n+1 \) vértices) cumple \( |V(T_{n+1})|=|A(T_{n+1})|+1 \).

Sea \( T_{n+1} \) un árbol de \( n+1 \) vértices.

1) Por ser \( T_{n+1} \) un árbol tiene un vértice de grado uno.

Prueba:
Sea \( v_1\to v_2\to \ldots\to v_k) \) un camino maximal (no se puede añadir más vértices). Si \( v_1 \) no tiene grado \( 1 \), tiene otra arista distinta de la que lo une con \( v_2 \). Pero por ser un camino maximal \( v_1 \) no puede ser unido a otro vértice distinto de los \( k \) vértices que forman el camino  por tanto estaría unido a alguno de los vértices \( v_3,\ldots,v_k \) y tendríamos un ciclo. Pero un árbol no tiene ciclos.
[cerrar]

2) Si al \( T_{n+1} \) le quitamos su vértice de grado uno y su única arista adyacente queda un árbol \( T_n \) con un vértice menos y una arista menos, es decir,

\( |V(T_n)|=|V(T_{n+1})|-1,\qquad |A(T_n)|=|A(T_{n+1)}|-1 \)

Prueba:
Que el nuevo grafo tiene un vértice menos y una arista menos es obvio por construcción. Nos queda ver que es árbol.

Está claro que si el grafo original \( T_{n+1} \) no tenía ciclos al quitar un vértice de grado \( 1 \) y su arista, sigue sin haber ciclos. Lo único que hay que probar es que \( T_{n+1}-\{v\} \) sigue siendo conexo. Pero dados dos vértices de \( u,w\in T_{n+1}-\{v\} \) sabemos que se pueden conectar por un camino en \( T_{n+1} \). Como \( grado(v)=1 \) ese camino no puede contener a \( v \) (ya que en un camino salvo los vértices inical y final todos los demás tienen al menos grado dos). Por tanto ese camino está en \( T_{n+1}-\{v\} \).
[cerrar]

3) Por hipótesis de inducción el árbol \( T_n \) con \( |V(T_n)|=|V(T_{n+1})|-1=n+1-1=n \) cumple:

\( |V(T_n)|=|A(T_n)|+1 \)

Pero entonces:

\( |V(T_{n+1})|=|V(T_n)|+1=|A(T_n)|+1+1=|A(T_{n+1})|+1 \)

que es justo lo que queríamos probar.

Saludos.

20 Febrero, 2020, 12:37 pm
Respuesta #21

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Tengo una pregunta que es por qué en tu prueba, Luis, del mensaje #3, decís construir un árbol con un vértice menos sin ninguna justificación, y en la prueba del profesor hay que justificar.

¡Hey! Mi mensaje #3 viene después del #1 donde he esbozado el cómo se construye ese árbol con un vértice menos:

Por ser un árbol tiene un vértice de grado uno. Si retiras ese vértices y su arista adyacente, tienes un nuevo árbol con una arista menos y un vértice menos: aplica inducción..

Lo que digo en el #3 es complementario a esto, como contestación a tu respuesta #2.

Para que no queden dudas mi prueba completa sería:

Teorema: Todo árbol \( T_n \) con \( |V(T_n)|=n \) (de \( n \) vértices) cumple \( |V(T_n)|=|A(T_n)|+1 \).

Demostración por inducción en el número de vértices:

Caso base \( n=2 \). Es inmediato que un árbol \( T_2 \) de dos vértices tiene \( 1 \) arista que los conecta. Por tanto \( |V(T_2)|=2=1+1=|A(T_2)|+1 \).

Paso inductivo:

Hipótesis: Todo árbol \( T_n \) con \( |V(T_n)|=n \) (de \( n \) vértices) cumple \( |V(T_n)|=|A(T_n)|+1 \).

Tesis: Todo árbol \( T_{n+1} \) con \( V(T_{n+1})=n+1 \) (de \( n+1 \) vértices) cumple \( |V(T_{n+1})|=|A(T_{n+1})|+1 \).

Sea \( T_{n+1} \) un árbol de \( n+1 \) vértices.

1) Por ser \( T_{n+1} \) un árbol tiene un vértice de grado uno.

Prueba:
Sea \( v_1\to v_2\to \ldots\to v_k) \) un camino maximal (no se puede añadir más vértices). Si \( v_1 \) no tiene grado \( 1 \), tiene otra arista distinta de la que lo une con \( v_2 \). Pero por ser un camino maximal \( v_1 \) no puede ser unido a otro vértice distinto de los \( k \) vértices que forman el camino  por tanto estaría unido a alguno de los vértices \( v_3,\ldots,v_k \) y tendríamos un ciclo. Pero un árbol no tiene ciclos.
[cerrar]

2) Si al \( T_{n+1} \) le quitamos su vértice de grado uno y su única arista adyacente queda un árbol \( T_n \) con un vértice menos y una arista menos, es decir,

\( |V(T_n)|=|V(T_{n+1})|-1,\qquad |A(T_n)|=|A(T_{n+1)}|-1 \)

Prueba:
Que el nuevo grafo tiene un vértice menos y una arista menos es obvio por construcción. Nos queda ver que es árbol.

Está claro que si el grafo original \( T_{n+1} \) no tenía ciclos al quitar un vértice de grado \( 1 \) y su arista, sigue sin haber ciclos. Lo único que hay que probar es que \( T_{n+1}-\{v\} \) sigue siendo conexo. Pero dados dos vértices de \( u,w\in T_{n+1}-\{v\} \) sabemos que se pueden conectar por un camino en \( T_{n+1} \). Como \( grado(v)=1 \) ese camino no puede contener a \( v \) (ya que en un camino salvo los vértices inical y final todos los demás tienen al menos grado dos). Por tanto ese camino está en \( T_{n+1}-\{v\} \).
[cerrar]

3) Por hipótesis de inducción el árbol \( T_n \) con \( |V(T_n)|=|V(T_{n+1})|-1=n+1-1=n \) cumple:

\( |V(T_n)|=|A(T_n)|+1 \)

Pero entonces:

\( |V(T_{n+1})|=|V(T_n)|+1=|A(T_n)|+1+1=|A(T_{n+1})|+1 \)

que es justo lo que queríamos probar.

Vale, esto va tomando forma para mí. Me sirve que hayas atado los cabos.

Sin embargo, Y PERDÓN LA INSISTENCIA, de verdad quiero entender tu prueba, pero repito, tu prueba es mucho más "extensa" que las que vi por otros lados, incluso la de mi profesor.

Mirá la proposición 4.2.4 de este libro, página 266 del PDF:

http://discrete.openmathbooks.org/pdfs/dmoi-tablet.pdf

¿Cuánta formalidad ves? ¡No mucha!

¿Cuánta formalidad ves en la imagen de mi mensaje #11 (la de otro libro)? ¡No mucha!

¿Cuánta formalidad ves en la "prueba" de mi profesor? ¡No mucha!

Así que en base a 3 casos distintos y viendo tu extensa demostración, no me queda más remedio que descartar estas 3 por ser incompletas, pero entonces hay 3 profesionales que se equivocan. No creo que sea muy lógico.

No digo que tu argumento esté mal, de hecho me gusta tu metodología, pero en este caso, vuelvo a decir, creo que estás hilando demasiado fino para una prueba "conocida" y "elemental".

Este ejercicio fue precisamente sacado de un examen, formulado tal como lo ves, ¿crees que un estudiante puede haber demostrado de la forma en que lo hiciste? Pensá si hubieses puesto este ejercicio en un examen tuyo para tus alumnos, ¿les hubieses pedido demostrarlo como lo hiciste, o pueden haber seguido alguno de los 3 casos anteriores?

Gracias por la paciencia.

Saludos

20 Febrero, 2020, 02:22 pm
Respuesta #22

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Sin embargo, Y PERDÓN LA INSISTENCIA, de verdad quiero entender tu prueba, pero repito, tu prueba es mucho más "extensa" que las que vi por otros lados, incluso la de mi profesor.

Mirá la proposición 4.2.4 de este libro, página 266 del PDF:

http://discrete.openmathbooks.org/pdfs/dmoi-tablet.pdf

¿Cuánta formalidad ves? ¡No mucha!

¿Cuánta formalidad ves en la imagen de mi mensaje #11 (la de otro libro)? ¡No mucha!

La prueba de la proposición 4.2.4 del libro, la del mensaje #11 (que me ha costado mucho leer porque la letra es pequeña y de poca resolución  :D) y la mía son...¡EXACTAMENTE LA MISMA!.

Si no eres capaz de ver eso es que no las estás entendiendo. Las tres siguen esta idea:

- Probar el resultado para un árbol de 1 o 2 vértices.
- Suponer el resultado cierto para un árbol de \( n \) vértices.
- Dado un árbol de \( n+1 \) vértices, usar que todo árbol tiene un vértice de grado uno para justificar que quitándole ese vértice y esa arista nos queda un árbol de \( n \) vértices.
- Aplicar la hipótesis de inducción para ese árbol de \( n \) vértices y concluir que el árbol original cumple lo que afirma el teorema.

Pueden estar redactadas de una u otra manera; más o menos detalladas; pero esencialmente son la misma.

A veces me parece que confundes formalidad, con usar símbolos y ecuaciones en lugar de palabras.

Citar
¿Cuánta formalidad ves en la "prueba" de mi profesor? ¡No mucha!

La demostración de tu profesor sin embargo, es distinta de las otras tres. Y no es cuestión de formalidad. Es que la idea no es correcta o está incompleta; le falta mencionar y justificar mínimamente que todo árbol de \( n+1 \) vértices puede construirse añadiendo un vértice a un árbol de \( n \) vértices.

Citar
Así que en base a 3 casos distintos y viendo tu extensa demostración, no me queda más remedio que descartar estas 3 por ser incompletas, pero entonces hay 3 profesionales que se equivocan. No creo que sea muy lógico.

Como te he dicho, y desde mi punto de vista, las dos que son iguales que la mía son perfectamente correctas. No se equivocan.

Y la de tu profesor ya he detallado mucho (queda que estudies y valores el ejemplo de los NO-árboles) porque no la considero correcta.

Citar
Este ejercicio fue precisamente sacado de un examen, formulado tal como lo ves, ¿crees que un estudiante puede haber demostrado de la forma en que lo hiciste? Pensá si hubieses puesto este ejercicio en un examen tuyo para tus alumnos, ¿les hubieses pedido demostrarlo como lo hiciste, o pueden haber seguido alguno de los 3 casos anteriores?

Más de lo mismo. Como te he dicho la única prueba distinta a las demás y que considero incorrecta (incompleta, mejor) es la de tu profesor.

Saludos.

07 Marzo, 2020, 01:17 am
Respuesta #23

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Creo que me voy dando cuenta de lo que querés transmitir.

Yo cuando leía "Se obtiene agregando un nuevo vértice" interpretaba que podía agregarse EN CUALQUIER vértice, pero ahora veo que no es cierto que se pueda agregar este nuevo vértice a cualquier otro, sólo en algunos vértices se cumplirá el teorema. ¿Es esto?

1) ¿Entiendes que si a un árbol de \( n+1 \) vértices le quitas un vértice de grado \( 1 \) y la única arista adyacente lo que te queda es un árbol de \( n  \) vértices?.

2) Entonces si cuando tenemos un árbol \( T_{n+1} \) de \( n+1 \) vértices somos capaces de quitarle uno y obtener un árbol \( T_n \) de \( n \) vértices...¡¿no es obvio que hemos probado que el árbol original  \( T_{n+1} \) puede construirse añadiendo al árbol \( T_n \) de \( n \) vértices, el vértice que le habíamos quitado?!. ¿No es obvio que hemos probado que todo árbol de \( n+1 \) vértices se obtiene añadiendo un vértice a un árbol de \( n \) vértices?.

Bajo la órbita que propuse anteriormente veo que 1) es verdadero y 2) falso, porque "se obtiene añadiendo un vértice a un árbol de \( n \) vértices" puede ser que se agregue a un vértice "no deseado". Entonces faltaría precisar cuál vértice elegimos para agregar el nuevo vértice.

Definición: Un NO-árbol es un grafo conexo que tiene algún ciclo.

Spoiler
Vaya por delante que es una definición inventada. Pero eso es lo de menos. Es un nombre para un grafo con una determinada propiedad, sin más.
[cerrar]

Teorema: Todo NO-árbol de \( 3 \) o más vértices tiene un ciclo de orden \( 3 \).

Prueba por inducción en el número \( n \) de vértices:

Paso base: \( n=3 \). Si un NO-árbol tiene tres vértices como tiene que tener un ciclo y el ciclo más pequeño posible es de orden \( 3 \), entonces necesariamente el NO-árbol tiene un ciclo de orden \( 3 \).

Paso inductivo:

Hipótesis: En todo NO-árbol, si \( |V|=h\geq 3 \) entonces tiene un ciclo de orden \( 3 \).

Tesis: En todo NO-árbol, si \( |V|=h+1\geq 4 \) entonces  tiene un ciclo de orden \( 3 \).

Para probarlo, consideremos cualquier NO-árbol \( G_h \) de \( h\geq 3 \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene  tiene un ciclo de orden \( 3 \).

A cualquiera de esos NO-árboles, le agregamos un nuevo vértice \( v_{h+1} \) para formar un nuevo NO-árbol \( G_{h+1} \) es decir: \( V_{h+1}=V_u\cup\{v_{h+1}\} \).

Si no agregáramos arista alguna, dicho vértice queda aislado y el grafo no es conexo, no es NO-árbol. Por lo cual hay que agregar necesariamente una arista \( \{v_{h+1},v_i\} \) donde \( v_i \) es alguno de los vértices existentes en \( G_h \).

Una vez agregado el vértice y al menos una arista ya tenemos un grafo \( G_{h+1} \) conexo y con un ciclo de orden \( 3 \) (el mismo que tenía \( G_h \)). Por tanto \( G_{h+1}  \)es un NO-árbol de \( h+1 \) vértices y hemos probado como queríamos que tiene un ciclo de orden \( 3 \), con lo cuál queda demostrada la tesis.

Obviamente la demostración NO puede estar bien, porque el Teorema que pretendía probar es FALSO. No es cierto que todo NO-árbol tenga un ciclo de orden tres. ¿Dónde está el error?.

El problema que veo es aquí:

A cualquiera de esos NO-árboles, le agregamos un nuevo vértice \( v_{h+1} \) para formar un nuevo NO-árbol \( G_{h+1} \) es decir: \( V_{h+1}=V_u\cup\{v_{h+1}\} \).

No es cierto que se pueda agregar un nuevo vértice A ALGÚN VÉRTICE DE TODOS LOS QUE un NO-árbol tiene.

Espero poder seguir aprendiendo.

Saludos

07 Marzo, 2020, 10:43 pm
Respuesta #24

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Yo cuando leía "Se obtiene agregando un nuevo vértice" interpretaba que podía agregarse EN CUALQUIER vértice, pero ahora veo que no es cierto que se pueda agregar este nuevo vértice a cualquier otro, sólo en algunos vértices se cumplirá el teorema. ¿Es esto?

Fracamente, no.  :( Me parece que estás poniendo el foco en un detalle bastante secundario... un matiz que has entendido mal.

En primer lugar si a un árbol se le agrega un vértice y se une por una arista a cualquier vértice lo que se obtiene es un árbol.

Citar
2) Entonces si cuando tenemos un árbol \( T_{n+1} \) de \( n+1 \) vértices somos capaces de quitarle uno y obtener un árbol \( T_n \) de \( n \) vértices...¡¿no es obvio que hemos probado que el árbol original  \( T_{n+1} \) puede construirse añadiendo al árbol \( T_n \) de \( n \) vértices, el vértice que le habíamos quitado?!. ¿No es obvio que hemos probado que todo árbol de \( n+1 \) vértices se obtiene añadiendo un vértice a un árbol de \( n \) vértices?.

Bajo la órbita que propuse anteriormente veo que 1) es verdadero y 2) falso, porque "se obtiene añadiendo un vértice a un árbol de \( n \) vértices" puede ser que se agregue a un vértice "no deseado". Entonces faltaría precisar cuál vértice elegimos para agregar el nuevo vértice.

¿Exactamente qué afirmación del las que hago en 2 dices qué es falsa? No hay porque especificar en qué vértice tengo que añadir el nuevo vértice; como tampoco especifico quien es el árbol \( T_n \).

Por ejemplo si digo, todo número natural se puede obtener sumando un número entero al \( 1 \). ¿Es falsa esa afirmación?. No. Es verdadera; eso no quiere decir que, por ejemplo para obtener el \( 3 \) pueda sumar cualquier número al \( 1 \); no. El número a sumar depende de que número natural queremos coneguir. Pero eso no quita veracidad alguna a la afirmación.

Citar
El problema que veo es aquí:

A cualquiera de esos NO-árboles, le agregamos un nuevo vértice \( v_{h+1} \) para formar un nuevo NO-árbol \( G_{h+1} \) es decir: \( V_{h+1}=V_u\cup\{v_{h+1}\} \).

No es cierto que se pueda agregar un nuevo vértice A ALGÚN VÉRTICE DE TODOS LOS QUE un NO-árbol tiene.

Pero no entiendo. ¿Por qué no se va a poder agregar un nuevo vértice a cualquier otro del NO-árbol?¿Qué problema hay ahí?.

En realidad el problema de esa "demotrasción", su fallo, es que NO es cierto que todo NO-árbol de \( h+1 \) vértices pueda conseguirse añadiendo un vértice a algún NO-árbol de \( h \) vértices.

Es una copia, esencialmente, de la misma demostración de tu profesor para árboles. Lo que quiero hacerte notar es que la clave de aquella, lo que le falta a tu profesor, es demostrar que en el caso de árboles ese posible fallo no se da; si es cierto que  todo árbol de \( h+1 \) vértices puede conseguirse añadiendo un vértice a algún árbol de \( h \) vértices.

Saludos.

28 Enero, 2021, 01:11 am
Respuesta #25

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Quisiera preguntar una cuestión sobre la crítica que se hace al profesor de su "demostración":

Tenemos los siguientes 2 hechos previamente demostrados sobre árboles:

1) Al agregar una arista entre dos vértices de un árbol, deja de ser árbol.

2) Todas las aristas de un árbol son puentes.

¿Es suficiente con mencionar estas 2 propiedades en la "demostración" del profesor para que sea correcta? O dicho de otra forma, ¿estos 2 hechos son equivalentes a lo que Luis expone cuando dice que falta lo siguiente en la prueba incompleta?:

- Hay que justificar que todo árbol tiene un vértice \( v \) de grado \( 1 \).

Spoiler
Sea \( v_1\to v_2\to \ldots\to v_k) \) un camino maximal (no se puede añadir más vértices). Si \( v_1 \) no tiene grado \( 1 \), tiene otra arista distinta de la que lo une con \( v_2 \). Pero por ser un camino maximal \( v_1 \) no puede ser unido a otro vértice distinto de los \( k \) vértices que forman el camino  por tanto estaría unido a alguno de los vértices \( v_3,\ldots,v_k \) y tendríamos un ciclo. Pero un árbol no tiene ciclos.
[cerrar]

- Si quitas ese vértice \( v \) y su arista adyacente te vuelve a quedar un árbol.
 
Spoiler
Está claro que si el grafo original \( G \) no tenía ciclos al quitar un vértice de grado \( 1 \) y su arista, sigue sin haber ciclos. Lo único que hay que probar es que \( G-\{v\} \) sigue siendo conexo. Pero dados dos vértices de \( u,w\in G-\{v\} \) sabemos que se pueden conectar por un camino en \( G \). Como \( grado(v)=1 \) ese camino no puede contener a \( v \) (ya que en un camino salvo los vértices inical y final todos los demás tienen al menos grado dos). Por tanto ese camino está en \( G-\{v\} \).
[cerrar]

 Con eso ya hemos probado que  todo árbol de \( n+1 \) vértices se puede construir añadiendo un vértice a un árbol de \( n \) vértices, lo que pasa es que ahora es mucho más inmediato terminar la prueba como yo te indiqué que como hace tu profesor.

Es decir reconozco que la prueba está incompleta; pero si se agregara algo como "y como se sabe que 1) y 2) se cumplen en todo árbol" quedando:

Citar
Paso Base (...)

Paso inductivo:

Hipótesis: En todo árbol, si \( |V|=h \) entonces \( |A|=h-1 \).

Tesis: En todo árbol, si \( |V|=h+1 \) entonces \( |A|=h \).

Para probarlo, consideremos cualquier árbol \( T_h \) de \( h \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene \( |A_h|=h-1 \).

A cualquiera de esos árboles, le agregamos un nuevo vértice \( v_{h+1} \) para formar un nuevo árbol \( T_{h+1} \) es decir: \( V_{h+1}=V_u\cup\{v_{h+1}\} \). Esto es así pues al agregar una arista entre dos vértices de un árbol, deja de árbol y todas las aristas de un árbol son puentes.

Si no agregáramos arista alguna, dicho vértice queda aislado y el grafo no es conexo, no es árbol. Por lo cual hay que agregar necesariamente una arista \( \{v_{h+1},v_i\} \) donde \( v_i \) es alguno de los vértices existentes en \( T_h \).

Si agregáramos además al menos otra arista \( \{v_j,v_k\} \), como entre dichos vértices ya existía un camino en el árbol \( T_h \), esta arista nueva en unión al camino existente formaría un ciclo, y el grafo resultante tampoco sería árbol.

Por lo tanto, la única opción es que se agregue una única aristas para tener un árbol de \( n+1 \) vértices. Entonces:

\( |A_{h+1}|=|A_h|+1=(h-1)+1=h \) con lo cual queda demostrada la tesis.

¿Con lo agregado en rojo ahora queda completa la prueba?



Otra consulta, Luis me dijo por privado:

Cita de: Luis
Y por último; incluso didácticamente no me agrada. Si en la tesis uno va a probar una propiedad sobre un árbol de h vértices lo natural es comenzar con un árbol de h vértices (después reducirlo a uno de h−1 para poder usar la hipótesis inductiva).

Pero en la prueba del profesor comienza diciendo explícitamente: "Para probarlo, consideremos cualquier árbol \( T_h \) de \( h \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene \( |A_h|=h-1 \)". ¿Por qué sugieres que el profesor no empieza con un árbol de \( h \) vértices cuando sí que lo hace?

Gracias y saludos

28 Enero, 2021, 09:17 am
Respuesta #26

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Es decir reconozco que la prueba está incompleta; pero si se agregara algo como "y como se sabe que 1) y 2) se cumplen en todo árbol" quedando:

Citar
Paso Base (...)

Paso inductivo:

Hipótesis: En todo árbol, si \( |V|=h \) entonces \( |A|=h-1 \).

Tesis: En todo árbol, si \( |V|=h+1 \) entonces \( |A|=h \).

Para probarlo, consideremos cualquier árbol \( T_h \) de \( h \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene \( |A_h|=h-1 \).

A cualquiera de esos árboles, le agregamos un nuevo vértice \( v_{h+1} \) para formar un nuevo árbol \( T_{h+1} \) es decir: \( V_{h+1}=V_u\cup\{v_{h+1}\} \). Esto es así pues al agregar una arista entre dos vértices de un árbol, deja de árbol y todas las aristas de un árbol son puentes.

¿Con lo agregado en rojo ahora queda completa la prueba?

No. Es que no es ese el problema. Lo que hay que agregar al menos es una frase que diga algo así: "Tenemos en cuenta que todo árbol de \( h+1 \) vértices se construye añadiendo un vértice a un árbol de \( h \) vértices." Luego uno podría discutir si adicionalmente hay que incluir una demostración de que eso es cierto o no (en mi opinión si; uno puede considerar que es bastante evidente, pero es que está al mismo nivel de evidencia del teorema que se quiere probar). Pero desde luego la observación que he escrito en negrita es troncal.

Tu parece que añadiendo esas frases quieres justificar más claramente esto:

"A cualquiera de esos árboles, le agregamos un nuevo vértice \( v_{h+1} \) para formar un nuevo árbol \( T_{h+1} \) es decir: \( V_{h+1}=V_u\cup\{v_{h+1}\} \)."

Pero el problema desde el principio es aclarar porqué, si lo que se quiere es probar que un árbol de \( h+1 \) vértices tiene \( h \) aristas, en lugar de partir de un árbol de \( h+1 \) vértices y razonar sobre él, como sería natural, parte sin embargo de un árbol de \( h \) vértices.

Citar
Otra consulta, Luis me dijo por privado:

Cita de: Luis
Y por último; incluso didácticamente no me agrada. Si en la tesis uno va a probar una propiedad sobre un árbol de \( h \) vértices lo natural es comenzar con un árbol de h vértices (después reducirlo a uno de h−1 para poder usar la hipótesis inductiva).

Pero en la prueba del profesor comienza diciendo explícitamente: "Para probarlo, consideremos cualquier árbol \( T_h \) de \( h \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene \( |A_h|=h-1 \)". ¿Por qué sugieres que el profesor no empieza con un árbol de \( h \) vértices cuando sí que lo hace?

Yo te dije eso entendiendo que la tesis que se quiere probar es:

Tesis: Si \( |V|=h \) entonces \( |A|=h-1 \).

Si él enuncia la tesis así (que es correcto igualmente):

Tesis: Si \( |V|=h+1 \) entonces \( |A|=h \).

Entonces lo natural para comenzar a probarla es partir de un árbol de \( h+1 \) vértices y razonar sobre él para llegar a probar que tiene \( h \) aristas.

Saludos.

28 Enero, 2021, 09:19 pm
Respuesta #27

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

No. Es que no es ese el problema. Lo que hay que agregar al menos es una frase que diga algo así: "Tenemos en cuenta que todo árbol de \( h+1 \) vértices se construye añadiendo un vértice a un árbol de \( h \) vértices." Luego uno podría discutir si adicionalmente hay que incluir una demostración de que eso es cierto o no (en mi opinión si; uno puede considerar que es bastante evidente, pero es que está al mismo nivel de evidencia del teorema que se quiere probar). Pero desde luego la observación que he escrito en negrita es troncal.

Tu parece que añadiendo esas frases quieres justificar más claramente esto:

"A cualquiera de esos árboles, le agregamos un nuevo vértice \( v_{h+1} \) para formar un nuevo árbol \( T_{h+1} \) es decir: \( V_{h+1}=V_u\cup\{v_{h+1}\} \)."

Pero el problema desde el principio es aclarar porqué, si lo que se quiere es probar que un árbol de \( h+1 \) vértices tiene \( h \) aristas, en lugar de partir de un árbol de \( h+1 \) vértices y razonar sobre él, como sería natural, parte sin embargo de un árbol de \( h \) vértices.

No he querido decir eso, perdón la confusión. Mi idea era saber si las 2 propiedades que se cumplen en los árboles justifican que todo árbol de \( h+1 \) vértices se pueda construir añadiendo un vértice a un árbol de \( h \) vértices. Equivalentemente:

Si [al agregar una arista entre dos vértices de un árbol, deja de ser árbol, y todas las aristas de un árbol son puentes]     entonces    [todo árbol de \( h+1 \) vértices se pueda construir añadiendo un vértice a un árbol de \( h \) vértices.]

¿Se puede demostrar que ese condicional es verdadero?

Yo te dije eso entendiendo que la tesis que se quiere probar es:

Tesis: Si \( |V|=h \) entonces \( |A|=h-1 \).

Si él enuncia la tesis así (que es correcto igualmente):

Tesis: Si \( |V|=h+1 \) entonces \( |A|=h \).

Entonces lo natural para comenzar a probarla es partir de un árbol de \( h+1 \) vértices y razonar sobre él para llegar a probar que tiene \( h \) aristas.

No. Según entiendo en la prueba del profesor menciona hipótesis y la tesis es con \( h+1 \) vértices, y lo que hace es empezar de la hipótesis para llegar a la tesis:

Spoiler
Debemos probar que en todo árbol, si \( |V|=n \), entonces \( |A|=n-1 \).

Paso base: \( n=1 \). Si existe un sólo vértice las únicas aristas que podría tener son bucles, pero siendo árbol debe ser acíclico, por lo tanto debe tener \( 0 \) aristas, y se cumple \( |A|=1-1=0 \).

Paso inductivo:

Hipótesis: En todo árbol, si \( |V|=h \) entonces \( |A|=h-1 \).

Tesis: En todo árbol, si \( |V|=h+1 \) entonces \( |A|=h \).

Para probarlo, consideremos cualquier árbol \( T_h \) de \( h \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene \( |A_h|=h-1 \).

A cualquiera de esos árboles, le agregamos un nuevo vértice \( v_{h+1} \) para formar un nuevo árbol \( T_{h+1} \) es decir: \( V_{h+1}=V_u\cup\{v_{h+1}\} \).

Si no agregáramos arista alguna, dicho vértice queda aislado y el grafo no es conexo, no es árbol. Por lo cual hay que agregar necesariamente una arista \( \{v_{h+1},v_i\} \) donde \( v_i \) es alguno de los vértices existentes en \( T_h \).

Si agregáramos además al menos otra arista \( \{v_j,v_k\} \), como entre dichos vértices ya existía un camino en el árbol \( T_h \), esta arista nueva en unión al camino existente formaría un ciclo, y el grafo resultante tampoco sería árbol.

Por lo tanto, la única opción es que se agregue una única aristas para tener un árbol de \( n+1 \) vértices. Entonces:

\( |A_{h+1}|=|A_h|+1=(h-1)+1=h \) con lo cual queda demostrada la tesis.
[cerrar]

Y aunque en la tesis haya un árbol con \( h \) vértices, no cambia en nada. Si uno demuestra \( p\to q \) partiendo de \( p \), hace cálculos y llega a \( q \), es igualmente válido tomar una parte de \( q \) (si es una igualdad, la izquierda; si es un condicional, la hipótesis), y usar \( p \) para llegar a la otra parte de \( q \). Son dos caminos distintos y prueban lo mismo pero ninguno es más "natural" que otro, creo yo.

Saludos

28 Enero, 2021, 10:21 pm
Respuesta #28

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Si [al agregar una arista entre dos vértices de un árbol, deja de ser árbol, y todas las aristas de un árbol son puentes]     entonces    [todo árbol de \( h+1 \) vértices se pueda construir añadiendo un vértice a un árbol de \( h \) vértices.]

¿Se puede demostrar que ese condicional es verdadero?

Pues no te voy a decir categóricamente que no se puede, pero yo no veo ahora mismo como hacerlo. La demostración de que todo árbol de \( h+1 \) vértices se pueda construir añadiendo un vértice a un árbol de \( h \) vértices, ya te indiqué como la haría:

La demostración de que todo árbol de \( n+1 \) vértices se puede construir añadiendo un vértice a un árbol de \( n \) vértices...¡es precisamente la demostración de  la propiedad que quieres probar que te esbocé al principio!.

- Hay que justificar que todo árbol tiene un vértice \( v \) de grado \( 1 \).

Spoiler
Sea \( v_1\to v_2\to \ldots\to v_k) \) un camino maximal (no se puede añadir más vértices). Si \( v_1 \) no tiene grado \( 1 \), tiene otra arista distinta de la que lo une con \( v_2 \). Pero por ser un camino maximal \( v_1 \) no puede ser unido a otro vértice distinto de los \( k \) vértices que forman el camino  por tanto estaría unido a alguno de los vértices \( v_3,\ldots,v_k \) y tendríamos un ciclo. Pero un árbol no tiene ciclos.
[cerrar]

- Si quitas ese vértice \( v \) y su arista adyacente te vuelve a quedar un árbol.
 
Spoiler
Está claro que si el grafo original \( G \) no tenía ciclos al quitar un vértice de grado \( 1 \) y su arista, sigue sin haber ciclos. Lo único que hay que probar es que \( G-\{v\} \) sigue siendo conexo. Pero dados dos vértices de \( u,w\in G-\{v\} \) sabemos que se pueden conectar por un camino en \( G \). Como \( grado(v)=1 \) ese camino no puede contener a \( v \) (ya que en un camino salvo los vértices inical y final todos los demás tienen al menos grado dos). Por tanto ese camino está en \( G-\{v\} \).
[cerrar]

 Con eso ya hemos probado que  todo árbol de \( n+1 \) vértices se puede construir añadiendo un vértice a un árbol de \( n \) vértices, lo que pasa es que ahora es mucho más inmediato terminar la prueba como yo te indiqué que como hace tu profesor.

En cuanto a esto:


Debemos probar que en todo árbol, si \( |V|=n \), entonces \( |A|=n-1 \).

Paso base: \( n=1 \). Si existe un sólo vértice las únicas aristas que podría tener son bucles, pero siendo árbol debe ser acíclico, por lo tanto debe tener \( 0 \) aristas, y se cumple \( |A|=1-1=0 \).

Paso inductivo:

Hipótesis: En todo árbol, si \( |V|=h \) entonces \( |A|=h-1 \).

Tesis: En todo árbol, si \( |V|=h+1 \) entonces \( |A|=h \).

Para probarlo, consideremos cualquier árbol \( T_h \) de \( h \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene \( |A_h|=h-1 \).

Lo único que digo que él para probar que:

Tesis: En todo árbol, si \( |V|=h+1 \) entonces \( |A|=h \).

Comienza considerando un árbol de \( h \) vértices (en azul). Lo lógico sería partir de la hipótesis: sea un árbol con \( h+1 \) vértices.

Cuando si yo quiero probar que si MENGANO entonces ZUTANO, lo "natural" es comenzar suponiendo que se cumple MENGANO y a partir de ahí razonar hasta verificar ZUTANO.

Vaya por delante que estoy usando "natural" de forma subjetiva; así que tampoco sé si tiene sentido llevar esta parte del debate mucho más allá.

Saludos.

28 Enero, 2021, 10:46 pm
Respuesta #29

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pues no te voy a decir categóricamente que no se puede, pero yo no veo ahora mismo como hacerlo.

Pues es muy fácil. Basta tener en cuenta que \( p\rightarrow (q\rightarrow p) \). Si sabes demostrar \( p \) (que sí que sabes), sólo tienes que añadir: por lo tanto, \( q\rightarrow p \).

Vaya por delante que estoy usando "natural" de forma subjetiva; así que tampoco sé si tiene sentido llevar esta parte del debate mucho más allá.

A mí me parece objetivo que la prueba en cuestión supone tácitamente que todo árbol con \( h+1 \) vértices puede obtenerse añadiendo un vértice y una arista a uno de \( h \) vértices, y que eso chirría al leerlo. Es como si quieres probar que todo número racional \( r \) cumple una propiedad \( P(r) \) y en lugar de eso tomas una función \( f: \mathbb N\longrightarrow \mathbb Q \) y demuestras que, para todo \( n\in \mathbb N \) se cumple \( P(f(n)) \). Eso sólo vale si \( f \) es suprayectiva, pero resulta muy raro que quieras probar algo sobre números racionales y que en su lugar partas de un número natural sin más explicaciones al que luego le aplicas \( f \), siempre sin mencionar siquiera que \( f \) es suprayectiva, por obvio que esto pudiera ser.