Demostrando que cada gráfico contiene un árbol de expansión?

Question

como parte de la Matemática Discreta curso que estamos tomando una introducción a la teoría de grafos. Llegamos a esta pregunta para hacer la tarea:

Deje $G=(V,E)$ un grafo conexo. Demostrar que existe un sub-grafo $H$ $G$ tal que $H$ es un árbol y se incluyen todos los de $G$'s de vértices.

Así que, inmediatamente pensé en el proceso de eliminación de todos los bordes de $G$ tal de que su eliminación no va a aumentar el número de componentes conectados, asegurando así que los hemos conectado a un ciclo de libre gráfico, que es un árbol.

Mi pregunta: es la descripción de este proceso realiza una prueba válida? Este curso es solo la introducción así que no estamos muy formal, pero todavía quiere asegurarse de que la posibilidad de este proceso en cualquier conectados gráfico demuestra la existencia de un árbol.

Answer 1

Usted podría tratar de formalizar esta por inducción: Probar que en cualquier grafo conexo con m aristas, hay algunos de árbol de expansión. Usted podría utilizar el caso sin bordes (un solo nodo) como su base de caso, luego de su paso inductivo afirmación de que ya sea un gráfico con (m + 1) de los bordes, es ya un árbol o puede eliminar un borde que no se desconecte el gráfico, el uso de la IH encontrar árboles de expansión para lo que queda, y, a continuación, conecte el gráfico juntos.

Otro enfoque inductivo: Trate de probar que para el caso de que usted tiene un gráfico con un nodo y, a continuación, mostrar que en el gráfico de (n + 1) nodos, se pueden señalar algunos nodo, sacarlo de la gráfica, y el uso de la hipótesis inductiva para obtener los subárboles para cada uno de los componentes conectados restantes. Usted puede entonces unirse a ellos en un árbol.

Dado que esta es una tarea de la pregunta, voy a dejar esto como un ejercicio para el lector. :-)

Answer 2

Si utiliza la inducción en los bordes y, a continuación, al quitar cualquier borde, entonces G es un G=(v, E-k) E-k < E, a continuación, de acuerdo a la hipótesis de la inducción será cierto. Y si no hay ningún borde que podemos eliminar entonces G es un árbol y H=G.

Answer 3

Usted puede convertir un algoritmo para la construcción de un objeto, en una existencia de prueba de la siguiente manera:

1. Estado el algoritmo
2. Demostrar que el algoritmo finalmente termina
3. Demostrar que el resultado del algoritmo satisface las propiedades deseadas

El algoritmo puede ser descrito en pseudocódigo de la siguiente manera:

SPANNING_TREE(G):
    let H = G
    while H contains an edge e whose removal does not disconnect the graph:
        remove e from H
    return H

Tenga en cuenta que para ser más rigurosos en los que usted quiere describir cómo encontrar un borde para quitar (si existe uno). Entonces todo lo que necesita hacer es demostrar que SPANNING_TREE termina y que el resultado realmente es un árbol de expansión de el gráfico de entrada.