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 2577 veces

manooooh

  • Matemático
  • Mensajes: 2,823
  • 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: 46,431
  • 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

  • Matemático
  • Mensajes: 2,823
  • 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: 46,431
  • 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

  • Matemático
  • Mensajes: 2,823
  • 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: 46,431
  • 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

  • Matemático
  • Mensajes: 2,823
  • 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
  • Aprendiz
  • Mensajes: 347
  • 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

  • Matemático
  • Mensajes: 2,823
  • 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
  • Aprendiz
  • Mensajes: 347
  • 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\)

17 Febrero, 2020, 08:22 am
Respuesta #10

Luis Fuentes

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

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?

Sería suponer cierta para \( n+54 \) y probarlo para \( n+55 \). Es decir, suponer cierto para un caso y ser capaz de probarlo para el "siguiente".

Entonces si, da igual, suponer cierto para \( n-1 \) y probarlo para \( n \) que suponer cierto para \( n \) y probarlo para \( n+1 \).

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

No es nada claro. Lo que has escrito ahí. Nada. De hecho lo que pones como tesis está mal, porque si \( |V|=n+1 \) debería de tenerse igualmente \( |V|=|A|+1 \). Además el \( |V|,|A|  \)de lo que escribes como hipótesis y tesis son diferentes; se refieren a árboles posiblemente distintos y en mi opinión no queda claro de esa escritura.

Para mi es mucho más claro con PALABRAS.

El razonamiento inductivo para probar la propiedad pedida se basa en, suponer como cierto que si un árbol tiene \( n-1 \) vértices entonces tiene una arista menos \( (n-2) \) y probar entonces que si un árbol tiene \( n \) vértices entonces tiene una arista menos \( (n-1) \).

Volveré de todas formas a esto después...

Citar
¿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á:

No. Lo que se hace habitualmente es reducir el caso \( n \) al caso \( n-1 \) para poder aplicar la hipótesis de inducción.

(...) 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?

Veamos. La inducción funciona así.

Queremos probar que una propiedad \( P(n) \) es cierta para cualquier \( n\in \Bbb N \).

La demostración por inducción consiste en:

1) Probar \( P(1) \).
2) Probar que \( P(n-1)\Rightarrow{}P(n) \) para cualquier \( n>1 \) (\( P(n-1) \) es lo que suele llamarse la hipótesis de inducción).

En nuestro caso \( P(n) \) es: "un árbol de \( n \) vértices tiene \( n-1 \) aristas".

Cuando digo: "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!)."

Me estoy refiriendo exactamente a (2): es decir describo que el segundo y esencial paso de la prueba por inducción es probar que \( P(n-1) \) ( que es cierto para árboles de \( n-1 \)) implica \( P(n \)) (a partir de ahí probarlo para árboles de \( n \) vértices).

Cuando dije antes: "(...) 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."

Me referiero a que para probar (2), es decir, para probar que \( P(n-1)\Rightarrow{}P(n) \) lo natural es intentar a partir de las hipótesis de \( P(n) \) (en nuestro caso que tenemos un árbol de \( n \) vértices) conseguir reducir el problema a \( P(n-1) \) (que afirma una propiedad sobre árboles de \( n-1 \) vértices) para poder utilizar en algún momento que \( P(n-1) \) es cierto.

En otras palabras, esas dos afirmaciones que te parecieron contradictorias, una es el enunciado del paso (2) de cualquier demostración por inducción y la otra es la descripción de como probar ese paso (2).

Citar
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?

La propiedad correcta es que \( |V|=|A|+1 \), es decir, que en un árbol el número de vértices es superior en una unidad al de aristas. Que \( |V|=|A|-1 \) está mal.

Saludos.

18 Febrero, 2020, 07:43 am
Respuesta #11

manooooh

  • Matemático
  • Mensajes: 2,823
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Antes que nada dejo la demostración del profesor:

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]

Miren, ahí el profesor escribió hipótesis y tesis inductivas y yo lo veo muy claro, partiendo del hecho en que "no había visto" que si \( |V|=|A|+1 \) luego \( |A|=|V|-1 \).

¿Está bien la demostración? ¿Va en sintonía con lo que ustedes proponen?



Gracias Richard R Richard por tus aclaraciones, al final aclararé sobre \( |V|=|A|-1 \).

Luis:

No. Lo que se hace habitualmente es reducir el caso \( n \) al caso \( n-1 \) para poder aplicar la hipótesis de inducción.

¿Qué pensás luego de haber visto una prueba "no habitual" (porque supuso \( n=h \) y demostró para \( n=h+1 \))?

En otras palabras, esas dos afirmaciones que te parecieron contradictorias, una es el enunciado del paso (2) de cualquier demostración por inducción y la otra es la descripción de como probar ese paso (2).

De acuerdo. Gracias!!

La propiedad correcta es que \( |V|=|A|+1 \), es decir, que en un árbol el número de vértices es superior en una unidad al de aristas. Que \( |V|=|A|-1 \) está mal.

La única referencia que tengo sobre eso es en el libro de "Matematica discreta y lógica" (Ed. Prentice Hall) de Grassmann y Tremblay (página 393):


Árbol libre
Más arriba dice que un árbol libre (árbol) es un grafo sencillo no dirigido que es a la vez conexo y acíclico. Recuérdese que un grafo acíclico es un grafo que carece de ciclos.
[cerrar]

Ahí dice que en todo árbol de \( n \) nodos (supongo son vértices), debe de tener \( n-1 \) aristas. ¡O sea que \( |V|=|A|-1 \) y encima lo demuestra! :o.

¿Me estoy equivocando?

Saludos

18 Febrero, 2020, 08:21 am
Respuesta #12

Luis Fuentes

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

Antes que nada dejo la demostración del profesor:

Vaya por delante: no me gusta NADA la demostración de tu profesor.  :D

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

De acuerdo.

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

De acuerdo y no es nada diferente a lo que te estaba diciendo. El paso inductivo consiste en suponer cierta la propiedad para un caso y probarla para el siguiente, es decir, con su notación suponer cierta para árboles de \( h \) vértices y probarlo para árboles de \( h+1 \) vértices. Obviamente llamarle \( n,h,m \), o \( Pericodelospalotes \) a la variable es lo de menos.


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

Y esto es lo que NO me gusta. Todo es correcto si damos por supuesto que todo árbol de \( h+1 \) vértices puede construirse añadiendo un vértice a un árbol de \( h \) vértices. Pero esto requiriría un mínimo comentario o justificación. Y de hecho si se justifica bien, después la prueba es mucho más rápida, porque veo difícil justificarlo sin hacer intervenir las aristas.

En todo caso incluso si lo da por hecho debería de empezar: sea un árbol \( T_{h+1} \) de \( h+1 \) vértices; sabemos que se construye añadiendo un vértice a otro árbol \( T_h \) de \( h \) vértices... y a partir de ahí razonar como ha hecho.

Porque tal como está estrictamente no prueba la Tesis:

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

Sino esta otra:

Tesis: En todo árbol, si \( |V|=h+1 \) y puede ser construido añadiendo un vértice a un árbol de \( h \) vértices, entonces \( |A|=h \).

Citar
Miren, ahí el profesor escribió hipótesis y tesis inductivas y yo lo veo muy claro, partiendo del hecho en que "no había visto" que si \( |V|=|A|+1 \) luego \( |A|=|V|-1 \).

Estoy de acuerdo como las escribió. Y es exactamente como te había comentado en mis anteriores mensajes.

Citar
No. Lo que se hace habitualmente es reducir el caso \( n \) al caso \( n-1 \) para poder aplicar la hipótesis de inducción.

¿Qué pensás luego de haber visto una prueba "no habitual" (porque supuso \( n=h \) y demostró para \( n=h+1 \))?

Ya te he dicho que la prueba no me gusta y he explicado el porqué.

Citar
La única referencia que tengo sobre eso es en el libro de "Matematica discreta y lógica" (Ed. Prentice Hall) de Grassmann y Tremblay (página 393):


Árbol libre
Más arriba dice que un árbol libre (árbol) es un grafo sencillo no dirigido que es a la vez conexo y acíclico. Recuérdese que un grafo acíclico es un grafo que carece de ciclos.
[cerrar]

Ahí dice que en todo árbol de \( n \) nodos (supongo son vértices), debe de tener \( n-1 \) aristas. ¡O sea que \( |V|=|A|-1 \) y encima lo demuestra! :o.

¿Me estoy equivocando?

¡Si! ¡Te estás equivocando! Que  en todo árbol de \( n \) nodos (supongo son vértices), debe de tener \( n-1 \) aristas, NO SIGNIFICA que \( |V|=|A|-1 \).

Que tenga \( n \) nodos quiere decir que \( |V|=n \). Que tenga \( n-1 \) aristas quiere decir que \( |A|=n-1 \), por tanto:

\( |A|=|V|-1 \) o equivalentemente \( |V|=|A|+1 \).

Saludos.

18 Febrero, 2020, 09:09 am
Respuesta #13

manooooh

  • Matemático
  • Mensajes: 2,823
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Vaya por delante: no me gusta NADA la demostración de tu profesor.  :D

Guerra de catedráticos, ¡traigo mis palomitas! ;D jajaja.

De acuerdo y no es nada diferente a lo que te estaba diciendo. El paso inductivo consiste en suponer cierta la propiedad para un caso y probarla para el siguiente, es decir, con su notación suponer cierta para árboles de \( h \) vértices y probarlo para árboles de \( h+1 \) vértices. Obviamente llamarle \( n,h,m \), o \( Pericodelospalotes \) a la variable es lo de menos.

De acuerdo.

Y esto es lo que NO me gusta. Todo es correcto si damos por supuesto que todo árbol de \( h+1 \) vértices puede construirse añadiendo un vértice a un árbol de \( h \) vértices. Pero esto requiriría un mínimo comentario o justificación. Y de hecho si se justifica bien, después la prueba es mucho más rápida, porque veo difícil justificarlo sin hacer intervenir las aristas.

En todo caso incluso si lo da por hecho debería de empezar: sea un árbol \( T_{h+1} \) de \( h+1 \) vértices; sabemos que se construye añadiendo un vértice a otro árbol \( T_h \) de \( h \) vértices... y a partir de ahí razonar como ha hecho.

Porque tal como está estrictamente no prueba la Tesis:

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

Sino esta otra:

Tesis: En todo árbol, si \( |V|=h+1 \) y puede ser construido añadiendo un vértice a un árbol de \( h \) vértices, entonces \( |A|=h \).

Disculpen que diga esto, pero Luis, creo que un poco se te ha ido la olla (sin ofender) :laugh:.

¿La diferencia que marcás es que no está justificado que la unión de dos conjuntos de vértices, es otro conjunto de vértices? ¿Es ese el problema?

Yo no veo que haya que justificar eso, es como (una vez trabajado lo suficiente con conjuntos) tener \( A=\{1\}\cup C \) y haya que justificar que, suponiendo \( \{1\},C \) conjuntos, \( A \) es otro conjunto, resultante de haber unido los anteriores.

Es obvio.

Se sabe que la unión de conjuntos es otro conjunto, de la misma forma tomando los conjuntos como vértices. ¿Esto es lo que criticás? ???

En caso de no acertar me gustaría que expliques exactamente la crítica diciendo algo como:

Está bien la prueba de tu profesor, si previamente se demuestra que ... [ejemplo: En todo árbol \( T_{h+1} \) con cantidad de vértices \( |V_{h+1}| \) (\( h+1 \) vértices), se cumple que \( V_{h+1}=V_{h}\cup\{v_{h+1}\} \) donde \( V_h \) es el conjunto de vértices de un árbol \( T_h \), en cuyo caso la demostración es....],

me gustaría entenderla.

¡Si! ¡Te estás equivocando! Que  en todo árbol de \( n \) nodos (supongo son vértices), debe de tener \( n-1 \) aristas, NO SIGNIFICA que \( |V|=|A|-1 \).

Que tenga \( n \) nodos quiere decir que \( |V|=n \). Que tenga \( n-1 \) aristas quiere decir que \( |A|=n-1 \), por tanto:

\( |A|=|V|-1 \) o equivalentemente \( |V|=|A|+1 \).

Ahhh, ¡gracias! Ahora eso lo entendí. Muy claro.

Gracias y saludos

18 Febrero, 2020, 10:05 am
Respuesta #14

Luis Fuentes

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

Guerra de catedráticos, ¡traigo mis palomitas! ;D jajaja.

¡Ya perdí!. No soy catedrático.

Citar
Disculpen que diga esto, pero Luis, creo que un poco se te ha ido la olla (sin ofender) :laugh:.

¿La diferencia que marcás es que no está justificado que la unión de dos conjuntos de vértices, es otro conjunto de vértices? ¿Es ese el problema?

No. Un árbol no es sólo un conjunto de vértices cualquiera. Un árbol es un conjunto de vértices y aristas que los unen que conforma un grafo conexo y acíclico, y ese es el matiz.

Y si a un árbol le quitamos al azar un vértice (y por tanto la o las aristas adyacentes a él) en principio NO tiene porque quedar un árbol. Podría quedar un grafo NO conexo si el vértice que hemos quitado no es terminal.

Te voy a poner un ejemplo. ¿Podemos probar una propiedad sobre ciclos usando que un ciclo de orden \( n \) se obtiene siempre añadiendo un vértice a un ciclo de orden \( n-1 \)?. Pues no, no podemos porque es FALSO que un ciclo de orden \( n \) pueda construirse añadiendo un vértice a un ciclo de orden \( n-1 \). Sin embargo con tu argumento uno podría decir. "¿Y por qué no?. El conjunto de vértices de un ciclo de orden \( n \) tiene un elemento más que el conjunto de vértices de un ciclo de orden \( n-1 \). ¿No es claro que en un conjunto de \( n \) elementos se obtiene añadiendo otro elemento a uno de \( n-1 \) elementos?."

Citar
Se sabe que la unión de conjuntos es otro conjunto, de la misma forma tomando los conjuntos como vértices. ¿Esto es lo que criticás? ???

Reiterando la idea que te he comentado antes: un grafo (y por tanto un árbol) es mucho más que simplemente su conjunto de vértices.

Citar
En caso de no acertar me gustaría que expliques exactamente la crítica diciendo algo como:

Está bien la prueba de tu profesor, si previamente se demuestra que ... [ejemplo: En todo árbol \( T_{h+1} \) con cantidad de vértices \( V_{h+1} \) (\( h+1 \) vértices), se cumple que \( V_{h+1}=V_{h}\cup\{v_{h+1}\} \) donde \( V_h \) es el conjunto de vértices de un árbol \( T_h \), en cuyo caso la demostración es....],

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.

Saludos.

18 Febrero, 2020, 10:17 am
Respuesta #15

manooooh

  • Matemático
  • Mensajes: 2,823
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

No. Un árbol no es sólo un conjunto de vértices cualquiera. Un árbol es un conjunto de vértices y aristas que los unen que conforma un grafo conexo y acíclico, y ese es el matiz.

Y si a un árbol le quitamos al azar un vértice (y por tanto la o las aristas adyacentes a él) en principio NO tiene porque quedar un árbol. Podría quedar un grafo NO conexo si el vértice que hemos quitado no es terminal.

Te voy a poner un ejemplo. ¿Podemos probar una propiedad sobre ciclos usando que un ciclo de orden \( n \) se obtiene siempre añadiendo un vértice a un ciclo de orden \( n-1 \)?. Pues no, no podemos porque es FALSO que un ciclo de orden \( n \) pueda construirse añadiendo un vértice a un ciclo de orden \( n-1 \). Sin embargo con tu argumento uno podría decir. "¿Y por qué no?. El conjunto de vértices de un ciclo de orden \( n \) tiene un elemento más que el conjunto de vértices de un ciclo de orden \( n-1 \). ¿No es claro que en un conjunto de \( n \) elementos se obtiene añadiendo otro elemento a uno de \( n-1 \) elementos?."

Dos objeciones:

1) Hablás de eliminar vértices cuando en la prueba del profesor nunca dice eliminar, sino agregar.

2) Hablás sobre un ejemplo de ciclos cuando se sabe que un árbol no tiene ciclos.

Por lo tanto no puedo entenderte si no apuntás hacia un ejemplo correcto.

Citar
Se sabe que la unión de conjuntos es otro conjunto, de la misma forma tomando los conjuntos como vértices. ¿Esto es lo que criticás? ???

Reiterando la idea que te he comentado antes: un grafo (y por tanto un árbol) es mucho más que simplemente su conjunto de vértices.

De acuerdo; pensé que con nombrar los vértices era suficiente. Sé que un árbol es un grafo (y por tanto tiene aristas y vértices) con la particularidad de que etc.

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!.

Cuando me haya quedado claro tu crítica leeré con paciencia la demostración que escribís.

Saludos

18 Febrero, 2020, 10:48 am
Respuesta #16

Luis Fuentes

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

Dos objeciones:

1) Hablás de eliminar vértices cuando en la prueba del profesor nunca dice eliminar, sino agregar.

Si hablo de eliminar es porque la única forma que se me ocurre de justificar que un árbol de \( n+1 \) vértices puede ser necesariamente construído añadiendo un vértice a un árbol de \( n-1 \) vértices. Pero olvida esto si quieres.


Citar
2) Hablás sobre un ejemplo de ciclos cuando se sabe que un árbol no tiene ciclos.

Por lo tanto no puedo entenderte si no apuntás hacia un ejemplo correcto.

¡Es que SI es cierto que todo árbol de \( n+1 \) vértices puede conseguirse añadiendo un vértice a un árbol de \( n \) vértices!. Entonces no puedo ponerte un ejemplo donde eso sea falso, porque no lo hay. Lo que digo es que no está justificado, que es distinto.

Resulta que:

1- Para probar una propiedad sobre árboles de \( n+1 \) vértices ves lícito comenzar con un árbol de \( n \) vértices y añadirle un vértice. Sin mayor justificación.

2- Para probar una propiedad sobre ciclos de orden \( n+1 \) NO ves lícito comenzar con un ciclo de orden \( n \) y añadirle un vértice. ¿Por qué?.

Si en algún momento en (1) y en (2) no usas que tiene de especial un árbol o un ciclo para justificar que tiene sentido una cosa si y la otra no. ¿Qué diferencia hay? ¿Una palabra a la que realmente no otorgas ningún significado?.

La clave es que para probar una propiedad sobre un grafo de \( n+1 \) vértices tienes que comenzar con un grafo de \( n+1  \) vértices.

Saludos.

18 Febrero, 2020, 11:50 pm
Respuesta #17

manooooh

  • Matemático
  • Mensajes: 2,823
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

1- Para probar una propiedad sobre árboles de \( n+1 \) vértices ves lícito comenzar con un árbol de \( n \) vértices y añadirle un vértice. Sin mayor justificación.

2- Para probar una propiedad sobre ciclos de orden \( n+1 \) NO ves lícito comenzar con un ciclo de orden \( n \) y añadirle un vértice. ¿Por qué?.

Si en algún momento en (1) y en (2) no usas que tiene de especial un árbol o un ciclo para justificar que tiene sentido una cosa si y la otra no. ¿Qué diferencia hay? ¿Una palabra a la que realmente no otorgas ningún significado?.

Está bien, entiendo que si no quiero probar (1) estaría "probando" (2), cuando sabemos que que (2) es falso. Entonces hay que probar (1), pero sigo sin entender por qué hablás de eliminar vértices, o sea no entiendo esta prueba:

- 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]

Tampoco entiendo esto:

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!.

Claro, es lo único que falta probar en la demostración del profesor, porque en su prueba usa que un árbol de \( h+1 \) vértices se puede construir a partir de otro de \( h \) vértices agregándole un vértice. ¿Dónde habla de eliminar vértices?

Saludos

19 Febrero, 2020, 10:24 am
Respuesta #18

Luis Fuentes

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

En general estoy desconcertado; porque todo lo que digo me parece obvio e intuitivo. No me refiero a los detalles técnicos que pudieran tener matices, me refiero a la idea global. Me gustaría que detallases más tus "no entiendo".

En ese sentido aunque primero he contestado a tus preguntas concretas al final he incluido otro ejemplo para intentar explicar mejor porque no me parece que esté bien la prueba de tu profesor. Casi me gustaría que te centrases primero en ese ejemplo antes que en lo demás.

1- Para probar una propiedad sobre árboles de \( n+1 \) vértices ves lícito comenzar con un árbol de \( n \) vértices y añadirle un vértice. Sin mayor justificación.

2- Para probar una propiedad sobre ciclos de orden \( n+1 \) NO ves lícito comenzar con un ciclo de orden \( n \) y añadirle un vértice. ¿Por qué?.

Si en algún momento en (1) y en (2) no usas que tiene de especial un árbol o un ciclo para justificar que tiene sentido una cosa si y la otra no. ¿Qué diferencia hay? ¿Una palabra a la que realmente no otorgas ningún significado?.

Está bien, entiendo que si no quiero probar (1) estaría "probando" (2), cuando sabemos que que (2) es falso. Entonces hay que probar (1)

No se...  :D. La frase que he marcado en rojo me resulta confusa. Entonces no se si he sabido transmitir bien la idea.

Citar
- 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]

No tengo claro que quieres decir con que no entiendes esa prueba. Te haré varias preguntas concretas.

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?.

Citar
Claro, es lo único que falta probar en la demostración del profesor, porque en su prueba usa que un árbol de \( h+1 \) vértices se puede construir a partir de otro de \( h \) vértices agregándole un vértice. ¿Dónde habla de eliminar vértices?

La respuesta esto es el punto (2) del párrafo anterior. Soy yo y no tu profesor el que habla de eliminar vértices; e insisto en lo mismo, hablo de ello porque es la única forma que se me ocurre de justificar que todo de \( n+1 \) vértices se obtiene añadiendo un vértice a un árbol de \( n \) vértices.


Te voy a poner otro ejemplo más elaborado a ver si logro explicar mejor la crítica que hago a la prueba de tu profesor.

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?.

Saludos.

20 Febrero, 2020, 04:56 am
Respuesta #19

manooooh

  • Matemático
  • Mensajes: 2,823
  • 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.

El resto lo leo luego.

Gracias.
Saludos