Teoría de grafos- Eliminación de un vértice de un grafo

Question

Dado un grafo conectado no dirigido $G=(V,E)$ y dos vértices $s,t \in V$ . Sabemos que la longitud del camino más corto de s a t es mayor que $V / 2 $.

Me encantaría tu ayuda para demostrar que debe haber un vértice que, si lo elimináramos, junto con las aristas que salen de él, no habría un camino entre $s$ y $t$.

lamentablemente no llegué a ninguna conclusión inteligente.

¡Gracias!

Answer 1

Pista: Demuestra que $s$ y $t$ no pertenecen al mismo componente biconexo de $G$.

Answer 2

[esta prueba es incorrecta tal como está]

Prueba: Coloque el camino más corto entre s y t de izquierda a derecha.

Suponiendo que el vértice siguiente a s no cumple con el requisito para dividir s-t por eliminación, entonces debe haber un camino alternativo alrededor de él. Este camino alternativo puede ser disjunto, al camino que ya tenemos. Pero tenemos el camino más corto, por lo que el camino alternativo debe ser igual de largo con vértices diferentes. Esto no puede ser ya que nuestro camino utiliza más de la mitad de los vértices. Por lo tanto, concluimos que el camino alternativo debe unirse a nuestro camino más corto en algún punto, digamos el vértice u.

Eliminando todos los vértices de s a u en nuestro camino y el camino alternativo, y usando el hecho de que los subcaminos de un camino más corto siguen siendo caminos más cortos, nos queda un subproblema que cumple exactamente las mismas hipótesis que teníamos para el problema original.

Continuando con esta reducción, llegamos a un punto donde el próximo vértice será de hecho uno cuya eliminación separará el grafo.

Answer 3

Realmente no es tan difícil. La prueba es la siguiente:

1) Eliminar todos los vértices en el camino más corto dejará s-t desconectados (obviamente, ya que solo quedan $< V/2+1$ vértices, lo que significa que cualquier camino tiene menos de $V/2$ aristas, si fuera un camino s-t, contradiría el camino s-t más corto).

2) Construimos un grafo orientado, donde

$V' = \{s, t\} \cup \{ v_+, v_- | v \neq s, t\}$

$E' = \{(x_-, y_+) | xy \in E\} \cup \{(x_+, x_-)| \{x_+, x_-\} \subset V' \} \cup \{(s, x_+)|sx \in E\} \cup \{(x_-, t) | xt \in E}$

Supongo que st no es una arista en el grafo original; si lo fuera, solo podría tener menos de 2 vértices, lo que contradice que hay vértices $s$ y $t$).

Se puede mostrar fácilmente que cualquier camino s-t en el grafo original corresponde a un camino s-t en el nuevo grafo dirigido y viceversa.

3) flujo máximo = corte mínimo

Hay un flujo s-t en el nuevo grafo (fluyendo a lo largo del camino más corto; las capacidades están todas configuradas a 1). Es maximal, porque no permite ningún otro flujo a través de sus vértices (porque $x_+\rightarrow x_-$ la capacidad es 1) y sabemos que no se puede ir de s a t sin pasar por uno de los vértices del camino más corto.

El flujo máximo tiene tamaño 1, por lo tanto, el corte mínimo también tiene tamaño 1.

4) Usamos el corte mínimo - o corresponderá a una arista en el grafo original (OK, eliminamos cualquiera de sus vértices siempre que no sea s o t) o corresponderá a un vértice (obvio).

Answer 4

No tengo suficiente reputación para publicar algo en un comentario, así que lo publicaré aquí. Gracias por tu cooperación.

Entonces mi confusión es:

si borramos un vértice v:

v ∈ V - {s,t} 

de un grafo no dirigido conectado G = (V,E).

¿Podemos demostrar que la eliminación de v desconecta G?