5 votos

Gráficos de bosqueF1F1 yF2F2 con los mismos vértices pero bordes diferentes. Demuestra que hay un borde dondeF1F1 con él sigue siendo un bosque

Estoy teniendo un momento bastante difícil con esta pregunta, he estado pensando en ello por unas horas y no tengo ni idea de cómo empezar a probar esto, porque es trivial, pero demostrando que ha sido difícil para mí.

Dado dos bosquesF1=(V,A)F1=(V,A) yF2=(V,B)F2=(V,B) con el mismo grupo de vérticesVV. También se da que|B|>|A||B|>|A|. Demuestre: existe un bordeeBAeBA dondeF1{e}F1{e} sigue siendo un bosque.

¡Cualquier ayuda será apreciada!

1voto

proy Puntos 752

Sugerencia: El hecho de que |B|>|A||B|>|A| puede ser usado para demostrar que F1F1 no está conectado. ¿Por qué hace esto implica que tal un borde existe?

Algunos de los más comentarios: Este es un resultado intermedio, de que hay una parte importante de la discusión que requiere que no haya conectividad (o algo equivalente) para hacer el trabajo.

Observe que, en general, no hay ningún borde que hace que F1F1 conectado. Incluso si no es, no podría ser en BB. Pero no estamos buscando un borde, simplemente una en BB que no produce un ciclo en el AA.

0voto

Ashot Puntos 2368

Agregar uno de los bordes de BABA AAy mira si hay un ciclo en AA. Si no se soluciona el problema, de lo contrario no es exactamente un ciclo en AA. En este ciclo existe un borde ee que no está de BB, de lo contrario un ciclo será también en BB lo cual es imposible, ya que BB es bosque. Retire ee AA y continuar desde el principio. Por lo que podemos sustituir todos los bordes en AA por los bordes en BB.

Si no va a ser una ventaja en BABA, que se contradice |B|>|A||B|>|A|, ya que el tamaño de AA no es cambiado.

Eso significa que no podemos seguir infinitamente, por lo que habrá un borde en BABA cuando se añade a AA no forma un ciclo.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X