Estoy confundido acerca de cómo abordar esto. Dice:
Mostrar que cada gráfico conectado tiene un árbol de expansión. Es posible encontrar una prueba que comienza con el gráfico y trabaja "hacia abajo" hacia el árbol de expansión.
Me dijeron que puede trabajar una prueba por la contradicción, pero no estoy viendo cómo usarlo. ¿Hay un visual, dibujo-tipo de prueba? Agradezco cualquier tips o Consejo.
Aquí es lo que yo pienso del problema. Esto es sólo una aproximación, no es la solución completa.
Una gráfica podría no ser un árbol por dos razones:
("La gráfica tiene muy pocos los bordes.") Es desconectado; es decir, algunos de los dos vértices de la gráfica no se puede alcanzar utilizando los bordes del gráfico solo.
("La gráfica tiene demasiadas aristas.") Contiene un ciclo.
Advertencia: Las frases en cursiva son sólo para el bien de la intuición, y no debe ser tomado literalmente. Por ejemplo, como un ejercicio fácil, construir un gráfico de tal manera que (i) tiene al menos un ciclo; y (ii) está desconectado. Si uno toma la cursiva las frases literalmente, estaríamos obligados a concluir que este grafo tiene demasiado pocos y demasiado muchas aristas, simultáneamente.
En su caso, se le da un grafo conexo $G$. Así que si en todas las $G$ no es un árbol, es porque contiene redundante bordes, en forma de ciclos. Así que lo desea, puede "recortar" el gráfico mediante la eliminación innecesaria de los bordes. Por supuesto, al hacerlo, nos gustaría asegurarnos de que no tenemos que destruir la conexión de la gráfica. La verdadera pregunta es: ¿qué borde(s) escogerías para eliminar?
Ayuda esto a usted? O ¿quieren más pistas?
Trabajar "hacia arriba" en lugar de "hacia abajo". Elige un vértice $v_0$ y poner $V_0:=\{v_0\}$, $E_0:=\emptyset$. Proceder de forma recursiva como sigue (es bastante obvio):
Asumir que un $k\geq0$ se ha construido un árbol parcial $(V_k, E_k)$ y $V':=V\setminus V_k$ no es vacío. Entonces deje que $V''=\{v_1,\ldots, v_m\}$ el conjunto de vértices $v\in V'$ tal que $\{v,w\}\in E$ $w\in V_k$. Cada $v_j\in V''$ elija un $w_j\in V_k$ y poner $$V_{k+1}:=V_k\cup V''\ , \quad E_{k+1}:=E_k\cup\bigl\{\{v_j,w_j\}\bigm|1\leq j\leq m\bigr\}\ .$ $
La esencia de lo que estás diciendo es que la equivalencia de estas definiciones:
Un árbol de expansión de un grafo conexo $G$ es el subárbol $T$ $G$ para el cual cada vértice de $G$ es incidente a un borde de $T$.
Un árbol de expansión de un grafo conexo $G$ es una máxima del conjunto de aristas que no contiene ciclos.
En realidad hay una tercera definición equivalente, de ordenación de la combinación de las dos ideas anteriores:
Un árbol de expansión de un grafo conexo $G$ es un conjunto mínimo de aristas que contiene todos los vértices.
Una vez que usted entienda estas equivalencias (las pruebas son mejores descubierto que leer), que se pondrá de manifiesto cómo mostrar la información de cada gráfica tiene un árbol de expansión en ambos sentidos: la construcción el uso de Def. 2, y la construcción de abajo, con Def. 1. De hecho, en cualquiera de los casos la prueba se saltan a la vista!
Si usted está realmente atascado aquí es un esquema de la equivalencia de las dos definiciones: supongamos que usted tiene un árbol de expansión en el segundo sentido. Podría ser desconectado? (No. ¿Por qué?) No podía faltar un vértice? (No. Por qué? Usted puede agregar un borde.)
Supongamos que usted tiene un árbol de expansión en el primer sentido, es evidente que no tiene ciclos, pero puede agregar cualquiera de los bordes? (No. Por qué? Te gustaría crear un ciclo.)
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.
