Supongamos que tenemos un gráfico $G$ y un árbol de expansión mínimo $T$ con peso $w$ . Sea $Z$ sea un ciclo que visite cada vértice al menos una vez.
¿Cómo puedo demostrar que cada ciclo $Z$ tiene al menos un peso $w$ .
Intuitivamente, está claro que el árbol de expansión mínimo también tiene un peso mínimo. Pero no veo cómo se puede demostrar esto formalmente. ¿Se puede convertir cada ciclo $Z$ en un árbol de expansión mínimo $T$ ?
Si elimina algún borde de $Z$ se obtiene una ruta de acceso $P$ que sigue visitando cada vértice exactamente una vez. Como las aristas de $P$ son un subconjunto de las aristas de $Z$ el peso de $Z$ es al menos el peso de $P$ .
Un camino es un árbol, por lo que $P$ es un árbol de expansión. Dado que $T$ es un árbol de mínima extensión, el peso de $P$ es al menos el peso de $T$ .
Tenemos $\text{weight}(Z) \ge \text{weight}(P) \ge \text{weight}(T) = w.$
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.
