Si T es un gráfico acíclico conectado, ¿cómo probaría que dos vértices de T están conectados exactamente por una ruta?

Answer 1

Debe tener más cuidado aquí, quiere decir un camino simple (los vértices no se repiten). Aquí hay una forma común de probar esta afirmación.

Suponga que hay más de una ruta, así que deje las rutas [matemáticas] P, P ‘\ subseteq G [/ matemáticas] desde el vértice [matemáticas] u [/ matemáticas] al vértice [matemáticas] v [/ matemáticas], donde [matemáticas] P \ neq P ‘[/ matemáticas]. El gráfico está conectado por lo que hay una ruta desde cualquiera de los dos vértices en el gráfico. Como [math] P \ neq P ‘[/ math], hay al menos un vértice en cada ruta que difiere. Ahora solo tiene que mostrar cómo construir el ciclo utilizando esta información (solo necesita un ciclo, por lo que los ciclos adicionales no son motivo de preocupación). Tenga en cuenta que debe tener cuidado ya que este ciclo (simple) puede existir en cualquier lugar a lo largo de los dos caminos. Al mostrar que hay un ciclo, se obtiene una contradicción.

Por ejemplo, el ciclo que desea es CDFEC aquí. Pero, tenga en cuenta que puede ser un ciclo más largo que este, e incluso puede estar al principio o al final de los dos caminos. Notarán que si acabo de tomar el camino de [matemáticas] u [/ matemáticas] a [matemáticas] v [/ matemáticas] y luego de [matemáticas] v [/ matemáticas] a [matemáticas] u [/ matemáticas] eso es No es simple .

Si necesita una solución: Path in Tree es Unique. Si usa mi imagen de arriba como una pista, es más fácil de seguir.

La forma más corta de probar esto (si no se le pide explícitamente que pruebe esta afirmación específica) es simplemente observar que es un árbol , luego use esto: Árbol (teoría de grafos) – Wikipedia. Esto se encuentra muy comúnmente en la mayoría de los textos introductorios de teoría de grafos o, a veces, en los libros de texto de algoritmos.

Answer 2

Debe ser bastante fácil de visualizar. El gráfico está conectado, por lo que puede ir de cada punto a cualquier otro punto al menos de una manera. Esa es la definición de conectado. Eso prueba que hay al menos un camino entre dos puntos.

Ahora a la prueba de la unicidad del camino. Tome cualquiera de los dos puntos en la gráfica. Suponga que puede ir de uno a otro a través de dos o más rutas. Ahora, si va del primer punto al segundo por la ruta 1 y de regreso al primero por la ruta dos, las dos rutas juntas formarán un ciclo. Pero el gráfico es acíclico. Esta contradicción desmiente nuestra suposición de que hay dos o más caminos entre dos puntos. Por lo tanto, solo hay un camino entre dos puntos.

QED

Editar: estos gráficos se llaman árboles por cierto.

Answer 3

(¿El gráfico está dirigido o no dirigido? Si no está dirigido, ¿está fuertemente conectado o débilmente conectado?)

Prueba por contradicción: supongamos que A y B están conectados por dos caminos. Si el gráfico no está dirigido, simplemente podemos invertir la dirección de uno de los caminos y obtener un ciclo.

Si el gráfico está dirigido, tenemos que usar su conectividad. Pero la propiedad no se mantiene si el gráfico está débilmente conectado, considere los cuatro bordes:

A-> C

A-> D

C-> B

D-> B

Este gráfico está débilmente conectado y tiene dos caminos, pero no tiene ciclo.

Si el gráfico está fuertemente conectado, entonces podemos razonar de la siguiente manera: si las dos rutas entre A y B son diferentes, entonces deben tener algún vértice en cada ruta que sea único para esa ruta. Llame a esos vértices V1 y V2.

Afirmamos que hay un ciclo A -> V1 -> B -> V2 -> A. Obviamente, las dos primeras rutas existen, por supuesto. B-> V2 y V2-> A deben existir si el gráfico está fuertemente conectado. Eso nos da el ciclo deseado.

(De hecho, cada gráfico dirigido fuertemente conectado con al menos dos vértices debe tener un ciclo).

Answer 4

Deje que [math] u [/ math] y [math] v [/ math] sean vértices arbitrarios de [math] T [/ math].

Como [math] T [/ math] está conectado, hay al menos una ruta entre [math] u [/ math] y [math] v [/ math].

Supongamos que hay dos caminos distintos [matemática] p [/ matemática] y [matemática] q [/ matemática] entre ellos; entonces [math] p \ cup -q [/ math] es un ciclo.

Por lo tanto, hay exactamente una ruta entre dos vértices.

Answer 5

La prueba por contradicción funciona muy bien aquí.