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

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

14 Febrero, 2020, 08:17 pm
Leído 3455 veces

manooooh

  • $$\pi \pi \pi \pi \pi \pi \pi$$
  • Mensajes: 3,038
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola!

Probar por inducción que en todo árbol \( (V,A,\varphi) \), se tiene \( |V|=|A|+1 \).



Me interesaría probarlo sin usar el teorema de Euler y con teoría de árboles elemental.

Para \( |V|=n=1 \) es cierto pues el grafo con \( A=1-1=0 \) es un árbol (un vértice aislado).

Sea cierto para \( |V|=n \). Demostraremos que es cierto para \( |V|=n+1 \).

¿Hasta ahí está bien escrito? ¿Cómo se demuestra?

Gracias!!
Saludos

14 Febrero, 2020, 08:48 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,081
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Para \( |V|=n=1 \) es cierto pues el grafo con \( A=1-1=0 \) es un árbol (un vértice aislado).

Sea cierto para \( |V|=n \). Demostraremos que es cierto para \( |V|=n+1 \).

¿Hasta ahí está bien escrito? ¿Cómo se demuestra?

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.

Saludos.

15 Febrero, 2020, 03:01 am
Respuesta #2

manooooh

  • $$\pi \pi \pi \pi \pi \pi \pi$$
  • Mensajes: 3,038
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

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.

No entiendo cómo podemos usar eso para probar el resultado. No entiendo cómo se te ocurre usar eso, ¡qué visionario! :laugh:.

De todos los vértices, si elimino uno que sea un vértice con su única arista de un árbol de \( n \) vértices, obtengo un árbol de \( n-1 \) vértices. Aplicando de vuelta, remuevo un vértice que una única arista y obtengo un árbol de \( (n-1)-1=n-2 \) vértices... ???

Gracias y saludos

15 Febrero, 2020, 08:51 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,081
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

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.

No entiendo cómo podemos usar eso para probar el resultado. No entiendo cómo se te ocurre usar eso, ¡qué visionario! :laugh:.

Para ser sincero no entiendo muy bien la broma o la ironía (no me parece mal, conste  ;)). No se si efectivamente lo ves muy obvio o si realmente quieres matizar algo al respecto.

Citar
De todos los vértices, si elimino uno que sea un vértice con su única arista de un árbol de \( n \) vértices, obtengo un árbol de \( n-1 \) vértices. Aplicando de vuelta, remuevo un vértice que una única arista y obtengo un árbol de \( (n-1)-1=n-2 \) vértices... ???

Ese "aplicando de vuelta" se hace "de golpe" precisamente con el argumento inductivo: suponiendo el resultado cierto para árboles de \( n-1 \) vértices y probándolo para árboles de \( n \) vértices.

Partimos de un árbol \( T \) con \( n \) vértices.

Construimos un árbol \( T' \) con \( n-1 \) vértices y tal que \( aristas(T')=aristas(T)-1 \).

Por hipótesis de inducción:

\( n-1=aristas(T')+1 \)
\( n=aristas(T')+1+1 \)
\( n=aristas(T)+1 \)

y listo.

Saludos.

15 Febrero, 2020, 06:43 pm
Respuesta #4

manooooh

  • $$\pi \pi \pi \pi \pi \pi \pi$$
  • Mensajes: 3,038
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

No, no lo veo obvio, por eso mi incredulidad de decir "¡qué visionario!", una inteligencia superior, como nos tenés acostumbrados (que conste muchas veces logro entenderte, otras veces no :laugh:).

Decís que la hipótesis de inducción es (o se deduce que) \( n-1=aristas(T')+1 \) pero, ¿eso no es precisamente la propiedad que en todo grafo, \( vértices(G)=aristas(G)+1 \)? Ese caso no aplicamos ninguna hipótesis sino simplemente una propiedad conocida.

Gracias y saludos

15 Febrero, 2020, 11:22 pm
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,081
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

 mmmmm…… vaya por delante en que estoy en esos casos en los que creo que un estudiante tiene algún bloqueo o duda sobre un problema, pero no tengo ni ideal de cuál es. De tu historial en el foro, puedo afirmar con toda seguridad que sabes lo que es una demostración por inducción.

 No tengo claro, eso si, lo que sabes de Teoría de Grafos; pero la idea de este problema es absolutamente elemental (más allá de que si uno quisiera ponerse puntilloso con algún detalle formal quizá este pudiera dar un poco la lata; pero poco).

No, no lo veo obvio, por eso mi incredulidad de decir "¡qué visionario!", una inteligencia superior, como nos tenés acostumbrados (que conste muchas veces logro entenderte, otras veces no :laugh:).

¿Entiendes lo que es un árbol en teoría de grafos?¿Lo "visualizas"? En caso afirmativo debería de serte evidente que al final todas esas ramitas en que se va ramificando el árbol, terminan por acabar en algún momento dejando al final vértices sin más descendencia, vértices de grado uno.

Si no visualizas, sino tienes ninguna intuición de lo que es un árbol en teoría de grafos, deberíamos de empezar por ahí. Diría que en teoría de grafos, un porcentaje alto de resultados o razonamientos deben de ser entendidos y vistos claramente de manera intuitiva, porque si uno pretende sólo manipularlos a través del formalismos se harán muy oscuros.

Por otra parte cuando uno trata de probar una propiedad por inducción lo natural es reducir el caso \( n \) al caso \( n-1 \); así que es natural intentar a partir de nuestro árbol original de \( n \) vértices construir otro árbol de \( n-1 \) vértices para poder usar el mecanismo de inducción.

Por todo esto mi propuesta si era realmente bastante obvia y nada original: es la que aparece en muchos libros de Teoría de Grafos para demostrar la propiedad de los árboles que nos ocupa.

Citar
Decís que la hipótesis de inducción es (o se deduce que) \( n-1=aristas(T')+1 \) pero, ¿eso no es precisamente la propiedad que en todo grafo, \( vértices(G)=aristas(G)+1 \)?

¡No!. Eso sólo se da en los árboles, no en cualquier grafo. ¡Además es precisamente lo qué quieres demostrar!.

Probar por inducción que en todo árbol \( (V,A,\varphi) \), se tiene \( |V|=|A|+1 \).

¡Qué \( |V|=|A|+1 \) significa exactamente que \( vértices(G)=aristas(G)+1 \)!. ¿Acaso habías entendido otra cosa?.

Entonces la idea de probar eso por inducción es suponer que es cierto para árboles de \( n-1 \) vértices y a partir de ahí probarlo para árboles de \( n \) vértices (¡exactamente igual qué en cualquier demostración por inducción!).

Si has entendido todo esto vuelve a leer mi primera respuesta y pregunta las dudas.

Saludos.

16 Febrero, 2020, 12:06 am
Respuesta #6

manooooh

  • $$\pi \pi \pi \pi \pi \pi \pi$$
  • Mensajes: 3,038
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Gracias por tus palabras. Sé que no todos los sábados respondés, así que te agradezco por tan detallada respuesta, Luis.

mmmmm…… vaya por delante en que estoy en esos casos en los que creo que un estudiante tiene algún bloqueo o duda sobre un problema, pero no tengo ni ideal de cuál es. De tu historial en el foro, puedo afirmar con toda seguridad que sabes lo que es una demostración por inducción.

 No tengo claro, eso si, lo que sabes de Teoría de Grafos; pero la idea de este problema es absolutamente elemental (más allá de que si uno quisiera ponerse puntilloso con algún detalle formal quizá este pudiera dar un poco la lata; pero poco).

Sé lo que es inducción. No me gusta tener que usar palabras para hacer una demostración, y eso se empeora cuando toco los temas de grafos, autómatas, no me gusta, pero bueno forma parte de las matemáticas discretas.

¿No te pasa a veces que hay alguna rama de las matemáticas y un hilo nuevo que un usuario pregunta (o en clase, o en tu estudio de las matemáticas) que te parezca pesado, latoso, lioso y te deje sin muchas ganas de responder o estudiar pero que aun así sabés que tenés que entender? A mí me pasa con teoría de grafos, y lo peor de todo es que estudio Ingeniería en Sistemas y es bastante importante por el tema de los algoritmos y eso :-\ :'(.

¿Entiendes lo que es un árbol en teoría de grafos?¿Lo "visualizas"? En caso afirmativo debería de serte evidente que al final todas esas ramitas en que se va ramificando el árbol, terminan por acabar en algún momento dejando al final vértices sin más descendencia, vértices de grado uno.

Más o menos. O sea yo me imagino al árbol como un diagrama perfectamente armado en donde claramente se ve el padre y los hijos, un vértice en la cima y sus descendientes. Pero no me gusta verlo cuando está desarmado, o sea cuando no se distingue claramente la línea sucesora. Y ahí me frustro.

¡No!. Eso sólo se da en los árboles, no en cualquier grafo. ¡Además es precisamente lo qué quieres demostrar!.

Ah, sí, es cierto, debería haber prestado más atención...

¡Qué \( |V|=|A|+1 \) significa exactamente que \( vértices(G)=aristas(G)+1 \)!. ¿Acaso habías entendido otra cosa?.

No, sólo no me esforcé en verlo.

Entonces la idea de probar eso por inducción es suponer que es cierto para árboles de \( n-1 \) vértices y a partir de ahí probarlo para árboles de \( n \) vértices (¡exactamente igual qué en cualquier demostración por inducción!).

En inducción (sobretodo aplicado a ecuaciones de recurrencia) se supone cierta la fórmula para \( n \) y se demuestra para \( n+1 \). ¿Da igual hacerlo así, y si la supongo cierta para \( n+54 \) y la demuestro para \( n+53 \) da igual?



Qusiera transcribir hipótesis y tesis inductivas para verlo un poco más claro:

Hipótesis: Con \( n=|V| \) tenemos \( |V|=|A|+1 \).

Tesis: Con \( n=|V|-1 \) tenemos \( |V|-1=|A|+1 \).

¿Lo que hiciste fue partir de \( |V|-1 \) y tratar de llegar a \( |A|+1 \) (como se hace habitualmente)? Sé que lo importante es lo que dijiste acá:

así que es natural intentar a partir de nuestro árbol original de \( n \) vértices construir otro árbol de \( n-1 \) vértices para poder usar el mecanismo de inducción.

¿Correcto?

Saludos

16 Febrero, 2020, 02:58 am
Respuesta #7

Richard R Richard

  • Ingeniero Industrial
  • $$\pi \pi \pi \pi$$
  • Mensajes: 445
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
Hola manooooh... te doy mi vista ingenieril del problema...

Definamos que se entiende por árbol. Un árbol es un grafo que no tiene ciclos y a la vez no hay dos aristas que comparten los mismos dos vértices.

Si te fijas cual es el Árbol mas pequeño es aquel que tiene una sola arista  pero tiene 2 vértices así que cumple con \( |V|=|A|+1 \)

Ahora si agregas aristas verás que para cumplir el primer párrafo una nueva arista tiene que tener un vértice perteneciente al árbol y otro que no puede pertenecer, porque de hacerlo crea un ciclo o bien repite vértices.

Luego cada ves que si agregas una arista tambien agregas un vértice  por lo que la relación \( |V|=|A|+1 \) se sigue cumpliendo...


Ahora que quizá mejore conceptualmente lo que es un árbol , quizá te sea mas fácil aplicar inducción
Saludos  \(\mathbb {R}^3\)

17 Febrero, 2020, 12:11 am
Respuesta #8

manooooh

  • $$\pi \pi \pi \pi \pi \pi \pi$$
  • Mensajes: 3,038
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Algo más que no entiendo sobre lo dicho por Luis:

(...) así que es natural intentar a partir de nuestro árbol original de \( n \) vértices construir otro árbol de \( n-1 \) vértices para poder usar el mecanismo de inducción.

(...)

Entonces la idea de probar eso por inducción es suponer que es cierto para árboles de \( n-1 \) vértices y a partir de ahí probarlo para árboles de \( n \) vértices (¡exactamente igual qué en cualquier demostración por inducción!).

¿No hay una contradicción ahí? "Empiezo por un árbol de \( n \) vértices" y la segunda cita dice, para mí, "Empiezo por un árbol de \( n-1 \) vértices". ¿Por dónde se empieza entonces?

También me gustaría revisar lo que dije en:

Qusiera transcribir hipótesis y tesis inductivas para verlo un poco más claro:

Hipótesis: Con \( n=|V| \) tenemos \( |V|=|A|+1 \).

Tesis: Con \( n=|V|-1 \) tenemos \( |V|-1=|A|+1 \).

¿Lo que hiciste fue partir de \( |V|-1 \) y tratar de llegar a \( |A|+1 \) (como se hace habitualmente)? Sé que lo importante es lo que dijiste acá:

así que es natural intentar a partir de nuestro árbol original de \( n \) vértices construir otro árbol de \( n-1 \) vértices para poder usar el mecanismo de inducción.

¿Correcto?



Si te fijas cual es el Árbol mas pequeño es aquel que tiene una sola arista  pero tiene 2 vértices así que cumple con \( |V|=|A|+1 \)

De acuerdo, aunque con \( 1 \) vértice también funciona, ya que éste queda aislado y cumple con la definición de árbol, ¿no? ???.

Ahora si agregas aristas verás que para cumplir el primer párrafo una nueva arista tiene que tener un vértice perteneciente al árbol y otro que no puede pertenecer, porque de hacerlo crea un ciclo o bien repite vértices.

La última parte no la entiendo. ¿Cómo que "y otro que no puede pertenecer"? ¿A qué te referís?

Luego cada ves que si agregas una arista tambien agregas un vértice  por lo que la relación \( |V|=|A|+1 \) se sigue cumpliendo...

Es cierto, ¡gracias!

He notado que en los libros aparece la propiedad \( |V|=|A|-1 \), mientras que aquí se usa \( |V|=|A|+1 \). ¿Es lo mismo? ¿Se restringe la cantidad de vértices?

Gracias y saludos

17 Febrero, 2020, 02:21 am
Respuesta #9

Richard R Richard

  • Ingeniero Industrial
  • $$\pi \pi \pi \pi$$
  • Mensajes: 445
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
De acuerdo, aunque con \( 1 \) vértice también funciona, ya que éste queda aislado y cumple con la definición de árbol, ¿no? ???.
Si un grafo puede contar con un  único vértice y sin aristas, entonces cumple con la condición \( |V|=|A|+1 \)  y sería el árbol más pequeño, pero ignoro realmente si es un grafo .


La última parte no la entiendo. ¿Cómo que "y otro que no puede pertenecer"? ¿A qué te referís?

Fijate que si quiero agregar un segmento o arista a este grafo para que continúe siendo un árbol, debe partir de los vértices A,B,C,o D pero no puede terminar en uno de ellos (los que ya pertenecen al Árbol)

,  pues si no se crea un ciclo o una doble arista entre los mismos dos vértices, y deja de ser un árbol. luego necesitas un nuevo vértice el E que hasta ese momento no estaba incluido en el árbol, luego hay 4 maneras de continuar el árbol con un de los  segmentos \( \overline{AE},\overline{BE},\overline{CE},\overline{DE} \), luego siempre adicionas un nuevo vértice y una nueva arista. Por lo que la relación continúa siendo cierta mientras crece el árbol.

He notado que en los libros aparece la propiedad \( |V|=|A|-1 \), mientras que aquí se usa \( |V|=|A|+1 \). ¿Es lo mismo? ¿Se restringe la cantidad de vértices?


Creería que no es lo mismo , si tienes una referencia al libro sin que afecte el copyrigth le hecho un vistazo, o dime el nombre de la fuente que lo busco por mi cuenta y veo más el contexto de la afirmación.
Saludos  \(\mathbb {R}^3\)