Verificando se a classificação de perda e vitória de uma liga é possível

Você está hospedando uma liga de basquete 1 x 1 com uma programação de jogos. No final da liga, cada jogador registra seu suposto recorde de vitórias e derrotas (não há empate), mas deseja verificar se as classificações propostas eram realmente possíveis, de acordo com o cronograma.

Por exemplo: você tem quatro jogadores (Alice + Bob + Carol + Dave) e sua agenda é um rodízio simples. As classificações relatadas [ A: 3-0 B: 1-2 C: 1-2 D: 1-2] e [ A: 2-1 B: 1-2 C: 1-2 D: 2-1] seriam possível, mas a posição [ A: 3-0 B: 0-3 C: 0-3 D: 3-0] não seria.

Agora, suponha que o cronograma seja um jogo de 3 confrontos entre Alice + Bob e Carol + Dave. A posição relatada [ A: 3-0 B: 0-3 C: 0-3 D: 3-0] agora é possível, mas [ A: 3-0 B: 1-2 C: 1-2 D: 1- 2] não seria mais.

(O cronograma não precisa ser simétrico de forma alguma. Você pode fazer Alice jogar contra Bob apenas 10 vezes e fazer Bob + Carol + Dave jogar 58 rodadas consecutivas.)

Problema : Dado um cronograma com k participantes e um total de n jogos, verifique com eficiência se uma classificação de perda e ganho proposta poderia realmente ocorrer a partir desse cronograma.

O método de força bruta O ( ) é óbvio, enumera todos os resultados possíveis do jogo e verifica se algum deles corresponde à classificação proposta. E se k for pequeno, aumentando n não adiciona muita complexidade - é muito fácil verificar a classificação de uma liga para duas pessoas, independentemente de jogar dez ou dez bilhões de jogos. Além disso, não progredi muito na busca de um método melhor e fiquei curioso para saber se alguém já havia visto um problema semelhante antes.$2^n$

Isso pode ser modelado como um problema de fluxo máximo.

Como uma etapa de pré-processamento, verifique se o número de jogos é igual à soma do número de vitórias (caso contrário, você sabe que algo está errado).

Deixei $G$ ser um conjunto de vértices correspondentes aos jogos disputados e $P$um conjunto de vértices correspondentes aos jogadores. Deixei$s$ e $t$ denotar dois vértices adicionais (origem e coletor).

Agora para todos os jogos $g\in G$ jogado entre $p1\in P$ e $p2\in P$, adicione uma aresta de $s$ para $g$ com capacidade $1$ e arestas de $g$ para $p1$ e $g$ para $p2$ também com capacidade $1$. Isso modela o fato de que o jogo pode dar um ponto para qualquer jogador.

Então, para cada jogador $p\in P$ adicione uma aresta de $p$ para $t$ com capacidade igual ao número relatado de vitórias para o jogador $p$. Isso modela o fato de que esse jogador deve vencer no máximo esse número de jogos.

É fácil ver daqui que, se as pontuações relatadas forem possíveis, haverá um fluxo saturado de $s$ para $t$e reciprocamente. Então, tudo que você precisa verificar é se o máximo$s,t$-fluxo neste gráfico é igual ao número de jogos jogados.

Como alternativa, você também pode ter um gráfico com um vértice por jogo e um número de vértices para cada jogador correspondente ao número de vitórias, conectá-los da mesma maneira que antes e verificar se o número de arestas em uma correspondência máxima é igual a o número de jogos (mas isso é quase a mesma coisa).