La distancia entre vértices del ciclo mínimo coincide en todo el grafo [Comprobación de la prueba]

Question

Con el fin de seguir mejorando mi intuición sobre los gráficos, y motivado por este ejercicio Quiero probar o refutar lo siguiente

Sea G un grafo simple y conectado que no es un árbol, y $v_0v_1...v_kv_0$ un ciclo en $G$ de longitud mínima. Si $1 \leq i < j \leq k$ la distancia entre $v_i$ y $v_j$ en el gráfico se logra en el ciclo, es decir

$$ d_G(v_i,v_j) = \min\{j-i,(k +1) - (j-i)\} $$

Si lo que he escrito es correcto, lo primero debería ser afirmativo. Lo que sigue es mi intento de probar esto, realmente apreciaría si usted pudiera, en primer lugar, revisar mi trabajo, y en segundo lugar, sugerir un argumento más corto.

Procedamos por inducción. Si $n \leq 2$ no hay gráficos que satisfagan la hipótesis, así que empezamos el caso base en $n = 3$ en cuyo caso el único gráfico de este tipo es $K_3$ , que es en sí mismo un ciclo, por lo que no hay nada que demostrar.

Ahora, dejemos que $G$ sea un gráfico de tamaño $n$ y supongamos que el resultado es cierto para cualquier gráfico de tamaño $m < n$ y que $C = v_0v_1...v_kv_0$ sea un ciclo mínimo, es decir, $l(C) = g(G)$ .

Si $G = C$ no hay nada que probar. De lo contrario, existe $v \in G \setminus C$ . Dado que el subgrafo inducido $H := G[G \setminus \{v\}]$ tiene un tamaño inferior a $n$ , verifica las hipótesis inductivas. Además, un ciclo en $H$ induce un ciclo en $G$ de la misma longitud, y $C \subset H$ Así que $C$ es un ciclo mínimo en $H$ . Por lo tanto,

$$ d_H(v_i,v_j) = \min\{j-i,(k +1) - (j-i)\} $$

Queremos demostrar ahora, entonces, que no podemos acortar la distancia entre estos vértices en $G$ . Es decir, $d_G(v_i,v_j) = d_H(v_i,v_j)$ . Sea $1 \leq i < j \leq k$ y $\xi = v_iw_1...w_lv_j$ un camino mínimo desde $v_i$ a $v_j$ . Si $\xi$ consiste en todos los vértices de $H$ hemos terminado. Si no, es de la forma

$$ v_iw_1 \ ... \ w_svw_{s+1} \ ... \ w_lv_j $$

Para concluir, podemos demostrar por inducción el tamaño de $I_{\xi} := \{w_r\}_{1\leq r \leq l} \cap C$ que ningún camino de este tipo es mínimo. Para ser más precisos, la proposición sobre la que haremos la inducción es

$p(a) = $ "Ningún camino de la forma $\xi = v_iw_1 \ ... \ w_svw_{s+1} \ ... \ w_lv_j$ con $v_i,v_j \in C$ puede tener una longitud inferior a $d_H(v_i,v_j)$ , si $|I_{\xi}| = a$ ".

Si $a = 0$ Esto está claro, porque $$ v_0 ... v_{i-1} \ \xi \ v_{j+1} ... v_k $$

contradiría la minimidad de $C$ . Sea $1 \leq a \leq n$ y supongamos $p(b)$ se mantiene para $b < a$ . Ahora, dejemos que $w_r = v_d$ sea la primera aparición de un elemento en $C$ . Hay dos casos, ya que $r \leq s$ o $r \geq s+1$ .

En el primer escenario, si $r \leq s$ sabemos por la hipótesis inductiva (anidada) que $w_r...v_j$ tiene mayor longitud que el camino $v_d...v_j$ de vértices en $C$ . Desde $\xi$ es mínima, $v_i$ debe estar en $v_d ... v_j$ porque si no podemos sustituir la última parte de $\xi$ para obtener un camino más corto,

$$ v_i...w_{r-1}v_d...v_j $$

Pero además, llegamos a una condradicción: si $v_i$ se encuentra en $v_d...v_j$ ,

$$ l(v_i v_{i+1} ...v_{j}) \leq l(v_d v_{d+1}...v_j) \leq l(w_r...v_j) < l(\xi) $$

pero una vez más, $\xi$ es mínima.

Si en cambio $r \geq s+1$ la última aparición de un elemento de $C$ en $\xi$ se produce después de $v$ , en cuyo caso podemos copiar el argumento anterior intercambiando los papeles.

Entonces hemos demostrado que ningún camino que contenga $v$ entre vértices en $C$ puede ser mínimo, lo que concluye la prueba.

¿Qué opinas?

Answer 1

EXE : $v_0,w_1,\cdots ,w_s,v_k$ es el camino más corto. Entonces $$ d_G(w_i,w_{i+t})=t$$

Prueba : Tenga en cuenta que $d_G$ es una métrica. Si $d_G(w_i,w_{i+t})<t$ entonces $$ s+1=d_G(v_0,v_k)\leq d_G(v_0,w_i) + d_G(w_i,w_{i+t}) + d_G(w_{i+t},v_k) < s+1 $$

EXE : Por comodidad, suponemos que el ciclo $(v_0,\cdots,v_k,\cdots,v_{k+l},v_0)$ de longitud $k+l+1$ es mínimo.

Entonces demuestre que $d_G(v_0,v_k)=k$ si $k<l+1$ .

Prueba : Supongamos que $$v_0,w_1,\cdots ,w_s,v_k\ \ast$$ es el camino más corto de longitud $s+1<k$ $(A)$ .

Aquí suponemos que $s$ es el más pequeño en número que satisface $(A)$ .

Si $$\{ w_1,\cdots, w_s\} \bigcap \{ v_1,\cdots, v_{k-1}\} = \emptyset $$ entonces hay un ciclo de longitud $k+s+1$ por lo que es una contradicción.

Si $$\{ w_1,\cdots, w_s\} \bigcap \{ v_{k+1},\cdots, v_{k+l} \} = \emptyset $$ entonces hay un ciclo de longitud $s+l+2$ por lo que es una contradicción.

Por lo tanto, $ v_a,\ v_b\in \{w_1,\cdots ,w_s\} $ con $0<a<k<b\leq k+l$ .

Aquí $d_{G}(v_a,v_b)\leq s-1$ . Es decir, $$v_a=w_{\alpha},\cdots,w_{\alpha+\beta}=v_b\ \ast\ast$$ se contradice con una definición de $s$ . Aunque suponemos que el camino en $\ast$ de tipo $\ast$ es el más pequeño, tenemos un camino de tipo $\ast$ es decir $\ast\ast$ .