Stratégie gagnante pour un jeu donné sur les graphiques

Question

Le jeu va comme suit. Deux joueurs jouent à un jeu, joueur 1 et joueur 2, dans lequel le premier joueur commence par nommer un héros $ h_1 $ , puis le joueur 2 répond avec un méchant $ V_1 $ Qui a joué dans un film avec $ h_1 $ . Ensuite, le joueur 1 répond avec un autre héros $ h_2 $ qui a joué dans un film avec $ v_1 $ , et ainsi de suite. Chaque héros et méchant peuvent être utilisés au plus une fois. Le premier joueur qui ne peut nommer aucun caractère (les héros / méchants disponibles n'ont pas de film commun avec le dernier choix de l'autre joueur), perd le jeu. Le joueur 1 commence toujours le jeu.

L'entrée est un ensemble de héros $ h $ , un ensemble de méchants $ v $ ( $ | h |= | v | \ geq 1 $ ) et une famille de films $ m $ , où chaque film est un ensemble de héros et de méchants qui sont apparus dans ce film.

La question est la suivante: pouvez-vous, basé sur $ h $ , $ V $ et $ M $ , décidez quel joueur gagne le jeu en supposant que les deux joueurs jouent de manière optimale?

---

Exemple:

Compte tenu des données suivantes: Les héros sont Iron Man , Captain America , Thor et Spider-man . Les méchants sont washlash , ultron , Thanos et vautour . Les films sont Avengers: War de l'infini (Stars Iron Man, Captain America, Thor, Thanos et Spider-Man) et Spider-Man: Homecoming (étoiles Iron Man, Vautour et Homme araignée). Pouvez-vous décider quel joueur a la stratégie gagnante?

---

Mon approche consiste à utiliser une correspondance maximale bipartite pour savoir quel joueur a la stratégie gagnante, car nous pouvons diviser les données dans deux ensembles, à savoir $ h $ et $ v $ et avoir des relations entre ces deux ensembles. L'algorithme HopCroft-Karp peut prendre deux de tels ensembles et trouver la cardinalité maximale. Merci de me corriger si je me trompe: dans les cas où il y a une assortie parfaite, un joueur 2 victoires et sinon joueur 1 gagne. Chaque fois qu'il y a une correspondance parfaite, cela signifie que le joueur 2 a toujours eu des réponses au héros que joueur 1 nommé.

Comment résoudriez-vous cela? Existe-t-il une solution meilleure et plus efficace que quelques assorties bipartites maximales.

Answer 1

La réponse courte est, le joueur deux gagne si et seulement si le graphique correspondant admet une correspondance qui "couvre" "couvre" l'ensemble $ H $

.

.

.

---

Voici un peu d'explication.

Votre idée est presque juste. Cependant, la preuve n'est pas intuitive et vous risquez de manquer quelques détails que vous avez besoin s'il s'agit d'une question théorique ou si vous avez besoin de concevoir la stratégie gagnante exacte et non seulement de produire le lecteur gagnant.

Alors, commençons par la partie manquante de votre réponse. Supposons qu'une instance donnée correspond à un graphique qui admet une correspondance parfaite. Selon votre stratégie, le joueur 2 gagne dans ce cas qui a raison. Supposons maintenant que le même exemple est donné avec un autre méchant, ou dix autres méchants ou mille d'entre eux. Clairement, le joueur deux remporte encore depuis l'ajout de méchants, peu importe la manière dont nous les attributions, aide uniquement le deuxième joueur. Donc, votre demande ne tient pas toujours. Cependant, votre réponse est très proche de ma réclamation et a la même intuition. Il manque seulement un peu de formalité.

réclamation. En supposant que les deux joueurs jouent de manière optimale, le joueur 1 gagne si et seulement si, étant donné une instance $ i $ , la valeur correspondante Le graphique n'admet pas d'assorti de saturation de l'ensemble $ H $ .

Alors qu'est-ce que cela signifie? Une assortie sature un ensemble de sommets $ S $ , si chaque sommet dans $ s $ est incident à une sommet dans la correspondance. Maintenant, nous prouvons la réclamation. Nous montrons deux stratégies gagnantes une pour le joueur deux lorsque le graphique admet une correspondance de la saturation de la série $ h $ et une pour le joueur deux lorsque le graphique n'admet pas une telle correspondance .

Preuve. Supposons maintenant que le graphique admet une telle correspondance. Laissez cette correspondance être $ m $ . La stratégie va comme suit. Tant que le joueur, on ne perdait pas, pour chaque choix $ h \ in h $ pour le joueur un, choisissez $ v \ en v $ le sommet correspondant à $ h $ in $ m $

La correction suit directement du fait que chaque sommet du joueur deux est unique et adjacent au choix du joueur un (en raison des propriétés d'une correspondance). Intuitivement, le joueur on manquera de mouvements à un moment donné (éventuellement après avoir choisi tous les héros dans l'ensemble $ h $ ).

En supposant maintenant que le graphique n'admet pas d'une saturation assortie $ h $ , selon le théorème de la salle, il y a un sous-ensemble $ A \ sous -éréeq h $ , telle que $ | n (a) | . Choisissez un tel ensemble qui est minimal d'inclusion. Nous prétendons qu'il y a une correspondance $ M '$ qui sature $ n (a) $ . En supposant autrement, à nouveau en raison de la salle, il y a un sous-ensemble $ s \ sous -éréeq n (a) $ tel que $ | N (S) | , mais ensuite enlever $ n (s) \ cap a $ de $ a $ et $ S $ de $ n (a) $ donne un sous-ensemble de $ A $ qui contredit également la condition de la salle qui forme une contradiction avec le choix de $ a $ être minimal. Par conséquent, il y a une $ m '$ qui sature $ n (a) $

La stratégie va maintenant comme suit. Choisissez un sommet dans $ A $ qui n'est pas incident à aucun bord dans $ M $ . Un tel sommet existe depuis $ | n (a) | <| A | $ . Choisissez ce sommet au début et pour chaque choix $ v \ in v $ du joueur deux, choisissez le sommet $ h \ in H $ correspondant à $ v $ in $ m '$

.

.

Encore une fois, il est facile de voir que le joueur deux manquera de mouvements à un moment donné (éventuellement après avoir choisi tous les sommets dans $ n (a) $ ) et Par conséquent, le joueur on gagne.