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

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

08 Febrero, 2021, 10:48 pm
Respuesta #40

manooooh

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

¿Pero cuál es entonces la definición de árbol? ¿Un grafo con dos vértices y dos aristas paralelas que los conectan es un árbol? Porque si lo consideras un árbol, entonces tiene el mismo número de vértices que de aristas, luego la afirmación es falsa.

No, no. La definición de árbol sigue siendo la misma (grafo conexo sin ciclos). Mi pregunta apuntaba a ver si la prueba de Luis cambia si en su demostración usa de fondo la definición "clásica" de grafo para usar la "nueva" definición de grafo y ver si seguía siendo la misma prueba o había que cambiarla.

Es decir, al usar la "nueva" definición de grafo en la prueba de Luis, ¿ésta prueba hay que cambiarla o sigue siendo la misma?

En el "\( p\rightarrow q \)" del que hablas, \( p \) es

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

Bien, ya hemos supuesto \( p \), y queremos demostrar \( q \), que es

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

¿Y ahora qué? Una vez hemos supuesto \( p \) ¿qué hacemos para demostrar \( q \)? Tendrás que tomar un árbol con \( h+1 \) vértices para ver si tiene \( h \) aristas, ¿no?

Claro. Eso es lo que hace inmediatamente después:

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

Por lo tanto no veo que haya que cambiar su redacción, que es lo que yo intuí que era una de las cosas que criticabas (la otra es no haber demostrado que todo árbol de \( h \) vértices puede ser construido a partir de uno de \( h-1 \)).

Pero tu profesor toma un árbol con \( h \) vértices, a partir de él construye otro de \( h+1 \) vértices, y con ello demuestra que "si un árbol de \( h+1 \) vértices se ha construido a partir de otro de \( h \) vértices, entonces tiene \( h \) aristas". Ahora le falta justificar que los árboles de \( h+1 \) vértices construidos a partir de árboles de \( h \) vértices son todos los árboles de \( h+1 \) vértices.

Ya, la mención de la construcción la entendí, lo que pregunto es si la redacción es "lógicamente" válida, por más que falte demostrar una buena parte (ver párrafo anterior).

Saludos

08 Febrero, 2021, 11:07 pm
Respuesta #41

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No, no. La definición de árbol sigue siendo la misma (grafo conexo sin ciclos). Mi pregunta apuntaba a ver si la prueba de Luis cambia si en su demostración usa de fondo la definición "clásica" de grafo para usar la "nueva" definición de grafo y ver si seguía siendo la misma prueba o había que cambiarla.

Es decir, al usar la "nueva" definición de grafo en la prueba de Luis, ¿ésta prueba hay que cambiarla o sigue siendo la misma?

¿Pero entonces hay que entender que un árbol no puede tener aristas paralelas o bucles? Porque si es así, es irrelevante que en la definición general de grafo los admitas o no, si no pueden aparecer en los árboles. No hay que cambiar nada.

Ya, la mención de la construcción la entendí, lo que pregunto es si la redacción es "lógicamente" válida, por más que falte demostrar una buena parte (ver párrafo anterior).

No sé lo que es una redacción lógicamente válida. No son dos críticas sino una misma. La prueba no está bien redactada porque oscurece una parte del argumento. No sólo es que falta un trozo por probar, sino que la redacción lo disimula. Lo que procede es partir de un árbol con \( h+1 \) vértices, y al partir de uno con \( h \) vértices está oscureciendo el argumento, porque deja a cargo del lector caer en la cuenta de que eso vale porque todo árbol con \( h+1 \) vértices se puede construir a partir de uno con \( h \) vértices. Es una redacción capciosa porque no es que uno pueda verla y preguntar: ¿cómo se justifica ese paso?, sino que la redacción tiende a ocultar que falta un paso, porque ya parte de un planteamiento capcioso al tomar un árbol con \( h \) vértices y aparenta que así está bien y que no hace falta nada más.

08 Febrero, 2021, 11:26 pm
Respuesta #42

manooooh

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

¿Pero entonces hay que entender que un árbol no puede tener aristas paralelas o bucles? Porque si es así, es irrelevante que en la definición general de grafo los admitas o no, si no pueden aparecer en los árboles. No hay que cambiar nada.

Exacto. Si un árbol tiene aristas paralelas forma un ciclo, y si tiene bucles también. Por eso los grafos pueden tener estas aristas y los árboles no, pero pensé que la prueba de Luis usaba en algún momento que un grafo no tiene aristas paralelas o no tiene bucles y podía fallar si lo incluíamos como definición, que es lo que pretendo incluir.

No sé lo que es una redacción lógicamente válida. No son dos críticas sino una misma. La prueba no está bien redactada porque oscurece una parte del argumento. No sólo es que falta un trozo por probar, sino que la redacción lo disimula. Lo que procede es partir de un árbol con \( h+1 \) vértices, y al partir de uno con \( h \) vértices está oscureciendo el argumento, porque deja a cargo del lector caer en la cuenta de que eso vale porque todo árbol con \( h+1 \) vértices se puede construir a partir de uno con \( h \) vértices. Es una redacción capciosa porque no es que uno pueda verla y preguntar: ¿cómo se justifica ese paso?, sino que la redacción tiende a ocultar que falta un paso, porque ya parte de un planteamiento capcioso al tomar un árbol con \( h \) vértices y aparenta que así está bien y que no hace falta nada más.

Vuelvo a repetir, entiendo muy bien la crítica de que falta un trozo por probar, pero tú mismo dices: "No sólo es que falta un trozo por probar, sino que la redacción lo disimula", o sea hay 2 críticas que no tienen relación.

Es como te dijera formalizar la frase: "Todos los humanos no sólo son animales, sino que tienen consciencia". Según tú definirías \( p(x) \) como "\( x \) es animal y tiene consciencia" para luego traducir como \( \forall x\,p(x) \), pero yo creo que es mucho más natural tratarlas como separado: \( p(x) \) como "\( x \) es animal", \( q(x) \) como "\( x \) tiene consciencia" y traducirlo como \( \forall x\,p(x)\land q(x) \). Aquí ves que cantidad de predicados (críticas en nuestro caso) según tú es 1 pero según yo son 2. Yo veo más natural usar 2 en vez de 1.

Saludos

08 Febrero, 2021, 11:38 pm
Respuesta #43

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Vuelvo a repetir, entiendo muy bien la crítica de que falta un trozo por probar, pero tú mismo dices: "No sólo es que falta un trozo por probar, sino que la redacción lo disimula", o sea hay 2 críticas que no tienen relación.

¿Cómo no van a tener relación si el único defecto que se le puede poner a la redacción es que oculta el agujero? No hay ninguna frase objetable en ella, salvo el hecho de que no justifica por qué puede partir de un árbol con \( h \) vértices, y ese "defecto de redacción" no es ni más ni menos que el "defecto lógico" de la prueba. Son la misma cosa. El único defecto de la redacción es que disimula un error lógico. No con ninguna frase mal redactada, sino con la concepción global de presentar un argumento como si eso fuera lo que procede y al acabar ya hemos acabado, cuando no es así. Tú preguntabas si es que hay que cambiar alguna frase, si hay algo que no esté bien expresado, y no es nada de eso. Lo que hay que cambiar es la redacción global, para que no aparente que esté bien lo que no debería plantear como lo hace. Vamos, que corregir la redacción es lo mismo que corregir el error lógico.

08 Febrero, 2021, 11:44 pm
Respuesta #44

manooooh

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

¿Cómo no van a tener relación si el único defecto que se le puede poner a la redacción es que oculta el agujero? No hay ninguna frase objetable en ella, salvo el hecho de que no justifica por qué puede partir de un árbol con \( h \) vértices, y ese "defecto de redacción" no es ni más ni menos que el "defecto lógico" de la prueba. Son la misma cosa. El único defecto de la redacción es que disimula un error lógico. No con ninguna frase mal redactada, sino con la concepción global de presentar un argumento como si eso fuera lo que procede y al acabar ya hemos acabado, cuando no es así. Tú preguntabas si es que hay que cambiar alguna frase, si hay algo que no esté bien expresado, y no es nada de eso. Lo que hay que cambiar es la redacción global, para que no aparente que esté bien lo que no debería plantear como lo hace. Vamos, que corregir la redacción es lo mismo que corregir el error lógico.

Ahora entiendo. Siempre pensé que por un lado te quejabas de la redacción en el sentido "lógico" ("técnicamente el modo de razonar del profesor es incorrecto peeeero es tan sutil que lo podríamos dejar pasar"). Jamás se me ocurrió pensar que el profesor lo escribió así para ocultar algo, consciente o inconscientemente. Lo máximo que llegué a ver fueron cosas como "Y la demostración queda a cargo del lector", pero una metedura de pata así nunca. :P

Saludos

08 Febrero, 2021, 11:49 pm
Respuesta #45

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Jamás se me ocurrió pensar que el profesor lo escribió así para ocultar algo, consciente o inconscientemente. Lo máximo que llegué a ver fueron cosas como "Y la demostración queda a cargo del lector", pero una metedura de pata así nunca. :P

No creo que tu profesor haya tratado de ocultar nada. Es más probable que pensara que así estaba bien, y que si su forma de expresarlo oculta esa idea es porque estaba oculta para él, es decir, que lo redacto de forma que "parece" que está todo en orden porque a él le parecía que estaba todo en orden.

Añado: Por otro lado, al insistir tanto y darle tantas vueltas estás sobredimensionando el asunto. Cualquiera que lea esto podría formarse la idea de que tu profesor ha cometido un error de bulto, imperdonable, cuando es algo mucho más intrascendente, una mera redacción desafortunada de una prueba, sin gran importancia real. Uno lee la prueba, lo piensa un segundo y dice: vale, pero podría haberlo dejado más claro. Y ya está. No es un asunto que dé para más.

09 Febrero, 2021, 01:14 am
Respuesta #46

manooooh

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

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]

Quisiera saber qué índices tiene el mayor camino acíclico que hay en la demostración de la cita porque no se ve bien. ¿Dice "\( v_1,v_2,\dots,v_k \) con \( v_1\neq v_k \) tiene a \( v_1 \) y \( v_k \) como extremos"?

Por otro lado, inmeditamente después dice "lo cual significa que su grado es \( 1 \)". ¿No se refiere a los extremos por lo que debería decir "lo cual significa que sus grados son \( 1 \)"?

Saludos

09 Febrero, 2021, 01:26 am
Respuesta #47

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Quisiera saber qué índices tiene el mayor camino acíclico que hay en la demostración de la cita porque no se ve bien. ¿Dice "\( v_1,v_2,\dots,v_k \) con \( v_1\neq v_k \) tiene a \( v_1 \) y \( v_k \) como extremos"?

No sé si entiendo la pregunta. Si intento ampliar la imagen se ve borrosa y no distingo la letra de los subíndices, pero no debería ser \( k \), ya que \( k \) es el número total de vértices menos uno del árbol. Si pone \( k \), es porque está considerando ese fragmento como la prueba de un hecho general independiente de que va antes y lo que va después, pero sería mejor que la letra fuera otra.

Por otro lado, inmeditamente después dice "lo cual significa que su grado es \( 1 \)". ¿No se refiere a los extremos por lo que debería decir "lo cual significa que sus grados son \( 1 \)"?

Supongo que el original inglés diría "their degree is one" (el grado de ellos es 1) y el traductor no se ha complicado la vida, pero, en efecto, hubiera sido mejor que hubiera cambiado el singular por el plural, ya que el posesivo español no indica el número.

09 Febrero, 2021, 01:31 am
Respuesta #48

manooooh

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

Añado: Por otro lado, al insistir tanto y darle tantas vueltas estás sobredimensionando el asunto. Cualquiera que lea esto podría formarse la idea de que tu profesor ha cometido un error de bulto, imperdonable, cuando es algo mucho más intrascendente, una mera redacción desafortunada de una prueba, sin gran importancia real. Uno lee la prueba, lo piensa un segundo y dice: vale, pero podría haberlo dejado más claro. Y ya está. No es un asunto que dé para más.

El problema está cuando la prueba que el profesor hace es la que se esperaría que un alumno en un examen esboce. Por eso es que la prueba debe ser correcta, ¿no crees?

No sé si entiendo la pregunta. Si intento ampliar la imagen se ve borrosa y no distingo la letra de los subíndices, pero no debería ser \( k \), ya que \( k \) es el número total de vértices menos uno del árbol. Si pone \( k \), es porque está considerando ese fragmento como la prueba de un hecho general independiente de que va antes y lo que va después, pero sería mejor que la letra fuera otra.

No me percaté que la letra ya estaba siendo usada. ¿Entonces esa parte de la oración quedaría así?: "\( v_1,v_2,\dots,v_j \) con \( v_1\neq v_j \) tiene a \( v_1 \) y \( v_j \) como extremos"

Gracias y saludos

09 Febrero, 2021, 01:40 am
Respuesta #49

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
El problema está cuando la prueba que el profesor hace es la que se esperaría que un alumno en un examen esboce. Por eso es que la prueba debe ser correcta, ¿no crees?

Sí, pero lo que te digo es que no ha cometido un crimen merecedor de que le quiten su título de licenciado. Que sólo es una redacción desafortunada, una redacción que habría quedado mejor de otra manera, pero que, a poco que uno reflexione sobre ella, entiende la situación y no es para tanto. Es como si uno al final de un cálculo dice que \( 2+3=6 \) y el resultado final no es el que tendría que ser, pero cualquiera que lo lea se da cuenta del lapsus y lo puede corregir por sí mismo sin poner el grito en el cielo porque un profesor ha hecho mal una suma. Yo veo eso en un libro y no se me ocurre decir: ¡esto está mal! ¿Cómo puede ser que alguien diga algo así?, sino que meramente pienso: "podría haberlo hecho más directo y más claro".

No me percaté que la letra ya estaba siendo usada. ¿Entonces esa parte de la oración quedaría así?: "\( v_1,v_2,\dots,v_j \) con \( v_1\neq v_j \) tiene a \( v_1 \) y \( v_j \) como extremos"

Pero no entiendo qué es lo que preguntas. Al margen de que no se distingan bien la letra que pone, ¿no se ve en la imagen que eso que dices es lo que pone, sea con una j o con la letra que sea? Yo diría que parece una n o una m.