Duas pessoas jogam o seguinte jogo sob um grafo G: Jogador 1 começa pela escolha de qualquer vértice. Cada escolha subsequente deve ser adjacente...
1. O segundo jogador tem uma estratégia vencedora se G tem um emparelhamento perfeito;
2. caso contrário o primeiro jogador tem um estratégia vencedora.
Observe que se G tem um emparelhamento perfeito M significa que cada escolha do Jogador 1 de x ∈ V permite que o Jogador 2 escolha o vértice y em que xy ∈ M . Desta forma, a estratégia do Jogador 2 será sempre escolher o vértice adjacente em que a aresta formada com a escolha do Jogador 1 estará no emparelhamento M .
Seja M um emparelhamento máximo de G em que M não é perfeito. Como M não é perfeito, existe um vértice em que não está no emparelhamento M e o Jogador 1 deverá escolhé-lo forçando jogador 2 a escolher um vértice coberto por M (caso contrário M não seria máximo). A partir desse ponto o Jogador 1 poderá seguir com a estratégia de sempre escolher o x ∈ V na vizinhança da escolha y ∈ V do Jogador 2 de forma a xy ∈ M . Observe que o Jogador 1 sempre terá essa possibilidade pela maximalidade de M .
Essa pergunta também está no material:
💡 1 Resposta
Ed 
O jogo descrito é conhecido como "Jogo do Caminho Alternado". A prova da afirmação é a seguinte: 1. Se G tem um emparelhamento perfeito M, então o segundo jogador tem uma estratégia vencedora: - O primeiro jogador escolhe um vértice x qualquer. - O segundo jogador escolhe um vértice y adjacente a x, tal que xy ∈ M. - A partir de agora, o segundo jogador sempre escolhe um vértice adjacente a x, tal que a aresta formada com a escolha do primeiro jogador esteja em M. Como M é perfeito, sempre haverá um vértice adjacente a x que satisfaça essa condição. - Como M é perfeito, o segundo jogador sempre terá uma escolha disponível, até que ele faça a última jogada e vença o jogo. 2. Se G não tem um emparelhamento perfeito M, então o primeiro jogador tem uma estratégia vencedora: - O primeiro jogador escolhe um vértice x que não está coberto por M. - O segundo jogador escolhe um vértice y adjacente a x, tal que xy não está em M. - A partir de agora, o primeiro jogador sempre escolhe um vértice adjacente a y, tal que a aresta formada com a escolha do segundo jogador não esteja em M. Como M não é perfeito, sempre haverá um vértice adjacente a y que satisfaça essa condição. - Como M não é perfeito, o primeiro jogador sempre terá uma escolha disponível, até que ele faça a última jogada e vença o jogo.
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Compartilhar