Digamos que tenemos un gráfico $ G $. Elegimos un borde de él (cualquier borde). ¿Siempre habrá un árbol de expansión que contiene ese mismo borde?
Creo que la respuesta es sí, porque no importa lo que hagamos, siempre podemos crear un árbol de expansión de modo que se incluya el borde que elegimos. Por supuesto, una prueba más formal sería necesario?
Comentarios
- Usted ' no ha escrito ni siquiera una prueba informal: esencialmente, usted ' ha dicho " Creo que la respuesta es sí, porque la respuesta es sí. "
Respuesta
Tenga en cuenta que el gráfico inicial $ G $ necesita estar conectado o no tiene árboles de expansión (aunque el mismo argumento aplicado a cada componente mostraría que cualquier gráfico tiene un bosque de expansión que contiene cualquier borde elegido).
Sea $ G = (V, E) $ sea una gráfica conectada, sea $ T $ sea cualquier subárbol de expansión y sea $ e $ cualquier borde en $ E $. Afirmamos que hay un árbol de expansión que incluye $ e $. Si $ e \ en T $, hemos terminado. De lo contrario, $ T + e $ contiene un ciclo. Ese ciclo contiene necesariamente al menos un borde $ e «\ neq e $ (en realidad, contiene al menos dos). $ T + ee» $ es un árbol de expansión que contiene $ e $.
Debes demostrarte a ti mismo que $ T + ee «$ realmente es un árbol de expansión.
Respuesta
Agregar un borde a un árbol provoca un ciclo único. Puede eliminar cualquier borde de este ciclo (diferente del que agregó) para recuperar un árbol. Este nuevo árbol contiene el borde que se agregó.
Comentarios
- ¡Eso ' es exactamente lo que dije!
- Sí, pero Lo dije con menos palabras. 🙂
- Porque mis siete oraciones realmente deben resumirse en tres. Tenemos cinco mil preguntas sin respuesta en el sitio. Sería mucho mejor responder algunas de ellas que publicar respuestas duplicadas a preguntas que no ' no las necesitan.
- Luego, lea la respuesta existente s antes de publicar uno propio.
- Nada es realmente obligatorio – ¿cómo podríamos hacerlo cumplir? Pero generalmente se espera que las respuestas aporten algo nuevo, y ¿cómo puede saber que ' está haciendo eso si no ' no sabe ¿Qué ' ya se ha dicho? Tener varias respuestas que dicen lo mismo simplemente satura la página, aunque obviamente eso ' no es gran cosa con solo dos. Publicar una respuesta corta, de estilo resumido, definitivamente puede ser valioso cuando las respuestas existentes son largas; Simplemente no ' no creo que agregue nada en este caso particular.