En mi club de squash local, hay una escalera que funciona de la siguiente manera.
- Al comienzo de la temporada, construimos una tabla con el nombre de cada miembro del club en una línea separada.
- Luego escribimos el número de juegos ganados y el número de juegos jugados al lado de cada nombre (en la forma: jugador gana / juegos).
Así, al comienzo de la temporada, la tabla se ve así:
Carol 0/0
Billy 0/0
Alice 0/0
Daffyd 0/0
Cualquiera de los dos jugadores puede jugar un partido, con un jugador ganador. Si gana el jugador más cercano al final de la mesa, se cambia la posición de los jugadores. Luego repetimos el paso 2., actualizando el número de victorias y juegos al lado de cada jugador. Por ejemplo, si Alice vence a Billy, tenemos
Carol 0/0
Alice 1/1
Billy 0/1
Daffyd 0/0
Estos partidos continúan durante toda la temporada y eventualmente dan como resultado que los jugadores sean listados en un orden aproximado de fuerza.
Desafortunadamente, la actualización ocurre de una manera bastante casual, por lo que se cometen errores. A continuación se muestran algunos ejemplos de tablas no válidas, es decir, tablas que no se pudieron producir siguiendo correctamente los pasos anteriores para un orden de inicio (hemos olvidado el orden que usamos al comienzo de la temporada) y la secuencia de partidos y resultados:
Alice 0/1
Billy 1/1
Carol 0/1
Daffyd 0/0
Alice 2/3
Billy 0/1
Carol 0/0
Daffyd 0/0
Alice 1/1
Billy 0/2
Carol 2/2
Daffyd 0/1
Dada una tabla, ¿cómo podemos determinar eficientemente si es válida? Podríamos comenzar señalando lo siguiente:
El orden de los nombres no importa, ya que hemos olvidado el orden inicial original.
El número total de victorias debe ser la mitad de la suma del número de juegos jugados. (Esto muestra que el primer ejemplo anterior no es válido).
- Supongamos que la tabla es válida. Luego hay un multigrafo , un gráfico que admite múltiples aristas pero sin bucles, con cada vértice correspondiente a un jugador y cada arista a un partido jugado. Entonces, el número total de juegos jugados por cada jugador corresponde al grado del vértice del jugador en el multigrafo. Entonces, si no hay un multigrafo con los grados de vértice apropiados, entonces la tabla debe ser inválida. Por ejemplo, no hay un multigrafo con un vértice de grado uno y uno de grado tres, por lo que el segundo ejemplo no es válido. [Podemos verificar eficientemente la existencia de tal multigraph.]
Por lo tanto, tenemos dos comprobaciones que podemos aplicar para comenzar, pero esto todavía permite tablas no válidas, como el tercer ejemplo. Para ver que esta tabla no es válida, podemos trabajar hacia atrás, agotando todas las formas posibles en que la tabla podría haber surgido.
Me preguntaba si alguien puede pensar en un algoritmo de tiempo polinómico (en el número de jugadores y el número de juegos) para resolver este problema de decisión.
fuente
Respuestas:
Esta no es una respuesta completa. Doy una declaración más simple del problema y algunas observaciones.
Comenzamos con un gráfico donde los vértices están etiquetados con .[ n ]
Observación
Creo que debería ser posible combinar esta observación con Havel-Hakimi para obtener un algoritmo de tiempo polinómico.
fuente
No he resuelto el problema, pero tengo resultados parciales, cuyas declaraciones se dan a continuación. Escribiré las pruebas si alguien está interesado.
Proposición . Suponga que la escalera (1) contiene más de un jugador (2) contiene el mismo número de victorias y derrotas; y (3) es tal que cada jugador ha ganado al menos un juego y ha perdido al menos un juego. Entonces la escalera es válida.
fuente