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

0 Usuarios y 1 Visitante están viendo este tema.

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

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-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.

Saludos.

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

manooooh

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,054
  • 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: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
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{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,054
  • 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: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
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.