Demuestre que la ruta entre dos nodos es única si el gráfico es un árbol.

Question

Creo que la prueba es fácil suponiendo que hay al menos dos rutas entre dos nodos. Si eso es cierto, entonces debe haber un ciclo en alguna parte. Pero si hay un ciclo, entonces esto no es un árbol, lo cual es una contradicción. Siento que el paso cuando digo que debe haber un ciclo si hay más de un camino es algo descuidado. Parece que es verdad, pero no estoy seguro de eso. ¿Cómo hago mi prueba un poco más rigurosa?

Answer 1

Si usted tiene dos caminos distintos entre dos nodos, a continuación, las rutas de acceso podrá acordar que una vez que empieza en el nodo de inicio, y también de acuerdo por un tiempo termina en el nodo final, pero el punto es que en algún lugar de los dos caminos divergentes de cada uno de los otros y ser disjuntas (incluso si es sólo por un nodo), y luego volver a un nodo común. Si esto no fuese así, tendría el mismo camino por ambos caminos. Esto le da a usted su ciclo. Si quieres, también puedo proporcionar una prueba por inducción, si se acepta que un árbol con $n$ nodos siempre se puede obtener de alguna manera por la eliminación de un nodo de un árbol con $n+1$ nodos.

Answer 2

Deje que la ruta mínima del nodo$a$ al nodo$b$ sean bordes$x_1...x_m$. Si existe otra ruta mínima de$a$ a$b$$y_1...y_n$, entonces$$x_1...x_ny_n^{-1}...y_1^{-1}$$ is a cycle unless $ x_k = y_k$ for all $ k $.