Un poco de diversión con los torneos (gráficos).

Question

Supongamos que $G$ es un torneo es decir, un grafo dirigido (finito) tal que entre dos vértices cualesquiera, $a$ y $b$ , hay al menos una arista en una de las dos direcciones, $a\rightarrow b$ o $b\rightarrow a$ .

1. Demuestre que hay al menos un Trayectoria hamiltoniana es decir, un camino que sigue la dirección de las aristas y que visita todos los vértices exactamente una vez. (Esta parte es un ejercicio clásico y sirve para preparar la segunda parte del problema).
2. Considere todos los posibles perdedores, es decir, el conjunto de todos los vértices que pueden ser puntos finales de las trayectorias hamiltonianas del torneo, véase la parte (1). Demuestre que el subgrafo de todos los perdedores tiene un Ciclo hamiltoniano es decir, un ciclo que sigue la dirección de las aristas y pasa por cada vértice exactamente una vez y vuelve al vértice inicial.

Por ejemplo

todos estos son torneos y el $\color{red}{\text{red}}$ Los puntos son los perdedores. Fíjate en que siempre hay un ciclo que los une.

Answer 1

Esta pregunta fue respondida en su mayoría en mi respuesta a esta otra pregunta . En lugar de volver a escribirlo todo, citaré esa respuesta. Un dígrafo es fuertemente conectado si hay un camino (dirigido) de cada vértice a cada otro vértice.

Propuesta I. Un torneo $T$ en $n$ vértices ( $n\gt1$ ) tiene un ciclo hamiltoniano si y sólo si está fuertemente conectado.

Prueba de la dirección no trivial, citada en mi respuesta anterior:

Supongamos que $T$ está fuertemente conectada; tenemos que demostrar que $T$ tiene un ciclo hamiltoniano. Comenzamos mostrando que $T$ tiene un ciclo, no necesariamente de longitud $n$ . Elija una arista dirigida $uv$ . Desde $T$ está fuertemente conectado, hay un camino desde $v$ a $u$ Este camino, junto con el borde $uv$ , nos da un ciclo en $T$ .

Dejemos que $C$ sea un ciclo en $T$ de longitud máxima $m$ ; tenemos que demostrar que $m=n$ . Sea $W$ (por "ganadores") sea el conjunto de todos los jugadores que ganan al menos a un jugador en $C$ es decir, $v\in W$ si existe una arista dirigida desde $v$ a algún vértice en $C$ . Del mismo modo, dejemos que $L$ (por "perdedores") sea el conjunto de todos los jugadores derrotados por al menos un jugador en $C$ es decir, $v\in L$ si existe una arista dirigida a $v$ desde algún vértice en $C$ . Consideramos varios casos.

Caso 1. $W=\emptyset=L$ .

En este caso, el ciclo $C$ contiene todos los vértices de $T$ Así que $m=n$ y todo está bien. Veremos que cada uno de los otros casos lleva a una contradicción.

Caso 2. $W=\emptyset\ne L$ .

Entonces $C$ no tiene aristas "entrantes". Si $u\in L$ y $v\in C$ , entonces no hay camino desde $u$ a $v$ contradiciendo la suposición de que $T$ está fuertemente conectada.

Caso 3. $W\ne\emptyset=L$ .

Si $u\in C$ y $v\in W$ entonces no hay camino desde $u$ a $v$ contradiciendo la suposición de que $T$ está fuertemente conectada.

Caso 4. $W\cap L\ne\emptyset$ .

Si $v\in W\cap L$ entonces podemos insertar $v$ entre dos vértices consecutivos de $C$ para obtener un ciclo de longitud $m+1$ contradiciendo la supuesta maximalidad de $m$ .

Caso 5. $W\ne\emptyset$ , $L\ne\emptyset$ y $W\cap L=\emptyset$ .

Desde $T$ está fuertemente conectada, debe haber una arista dirigida $uv$ para algunos $u\in L$ , $v\in W$ . Entonces los vértices $u,v$ puede insertarse en el ciclo $C$ para obtener un ciclo de longitud $m+2$ contradiciendo la supuesta maximalidad de $m$ .

Propuesta II. Todo torneo tiene una trayectoria hamiltoniana.

La forma más sencilla de demostrarlo es considerar un camino lo más largo posible en $T$ y demostrar que, si no contiene todos los vértices, podemos construir un camino más largo. Otra forma (teorema de Rédei) es utilizar el principio de entrada y salida (también conocido como inclusión-exclusión) para demostrar que el número de caminos hamiltonianos en $T$ es un número impar, por tanto, no nulo. Otra forma es demostrar que Teorema de Gallai-Milgram que tiene como caso especial la Proposición II. Una forma muy tonta es derivar la Proposición II de la Proposición I sobre el Hamiltoniano ciclos que es lo que voy a hacer.

Dejemos que $T$ ser un torneo. Puede o no estar fuertemente conectado, pero podemos incluirlo en un torneo fuertemente conectado $T'$ añadiendo dos nuevos vértices $u,v$ una arista dirigida $uv$ y aristas dirigidas $tu,vt$ para cada $t\in T$ . Por la proposición I, $T'$ tiene un ciclo hamiltoniano, que claramente tiene que contener la arista $uv$ ; borrando los vértices $u,v$ del ciclo hamiltoniano nos deja un camino hamiltoniano en $T$ .

Propuesta III. El subtorno en el conjunto de todos los "perdedores" está fuertemente conectado; por lo tanto, tiene un ciclo hamiltoniano, siempre que haya más de un perdedor.

[El teorema 2 de mi respuesta anterior es esencialmente equivalente a esto, pero expresado en términos de "ganadores" en lugar de "perdedores"].

Prueba. Dejemos que $T$ sea un torneo. Deja que $S$ sea el conjunto de todos los vértices $v\in T$ tal que, para cada vértice $u\in T$ existe un camino (dirigido) desde $u$ a $v$ . (Demostraré que $S$ coincide con el conjunto de todos los "perdedores" tal y como se define en la pregunta, es decir, el último vértice de alguna trayectoria hamiltoniana; esto es sólo una forma más sencilla y natural de definirlos).

1. Está claro que todo perdedor pertenece a $S$ si hay un camino hamiltoniano que termina en $v$ entonces podemos llegar desde cualquier vértice a $v$ siguiendo ese camino.

2. Si $u\in S$ y $uv\in E(T)$ entonces $v\in S$ . Esto se desprende de la definición de $S$ .

3. $S$ está fuertemente conectada. Para ver esto, considera cualquier vértice $u,v\in S$ . Según la definición de $S$ hay un camino desde $u$ a $v$ en $T$ ya que no hay aristas dirigidas desde $S$ a $T\setminus S$ Todo el camino debe estar en $S$ .

4. Terminamos la prueba mostrando que cada vértice en $S$ es un perdedor; es decir, consideramos un vértice $v\in S$ y encontrar un camino hamiltoniano que termine en $v$ . En cualquier caso, por la Proposición II existe un camino hamiltoniano en $T$ . Dado que no se puede escapar de $S$ la ruta debe atravesar primero todos los vértices (si los hay) en $T\setminus S$ entonces todos los vértices de $S$ . Si $S=\{v\}$ hemos terminado. Supongamos que $S$ contiene más de un vértice. Por la Proposición I, podemos encontrar un ciclo hamiltoniano en $S$ ; deja que $w$ sea el sucesor de $v$ en ese ciclo. Sigue el camino original de Hamilton siempre que se mantenga en $T\setminus S$ ; luego salta a $w$ y seguir el ciclo hasta $v$ . Q.E.D.