Jeu sur graphe orienté

DAG

Un Directed Acyclic Graph (ou graphe orienté sans cycle) est un graphe orienté ne possédant aucun circuit.

Un circuit est un sous-graphe de type A→B→C→...→A

On considère ici des DAG particuliers, possédant exactement

Voici un exemple de DAG avec un départ (le sommet F) et une arrivée (le sommet B).

%3 A A B B A->B E E A->E C C C->B D D D->C E->B E->C E->D F F F->A F->D F->E

Règle du jeu

Chaque joueur dispose d'un pion.

Par exemple avec ce graphe (le départ et l'arrivée sont dessinés en traits doubles) :

%3 1 😷 2 1->2 3 1->3 4 1->4 2->3 3->4 7 3->7 11 👵 3->11 5 4->5 6 4->6 4->7 5->6 6->7 8 7->8 9 8->9 10 8->10 9->10 10->11

C'est le Docteur qui commence. Pour jouer, le Docteur déplace son pion en suivant une flèche (un arc du graphe). Par exemple

%3 1 2 1->2 3 1->3 4 😷 1->4 2->3 3->4 7 3->7 11 👵 3->11 5 4->5 6 4->6 4->7 5->6 6->7 8 7->8 9 8->9 10 8->10 9->10 10->11

River Song par contre, lorsque c'est à son tour de jouer, déplace son pion en remontant une flèche. Par exemple (c'est à son tour de jouer) :

%3 1 2 1->2 3 1->3 4 😷 1->4 2->3 3->4 7 3->7 11 3->11 5 4->5 6 4->6 4->7 5->6 6->7 8 7->8 9 8->9 10 👵 8->10 9->10 10->11

Si, à un moment, le Docteur arrive jusqu'à l'arrivée, il gagne :

%3 1 2 1->2 3 1->3 4 1->4 2->3 3->4 7 👵 3->7 11 😷 3->11 5 4->5 6 4->6 4->7 5->6 6->7 8 7->8 9 8->9 10 8->10 9->10 10->11

Mais si à un moment c'est River Song qui arrive au départ, c'est le Docteur qui gagne :

%3 1 👵 2 1->2 3 1->3 4 1->4 2->3 3->4 7 😷 3->7 11 3->11 5 4->5 6 4->6 4->7 5->6 6->7 8 7->8 9 8->9 10 8->10 9->10 10->11

En fait, le seul moyen de gagner, pour River Song, est d'arriver à ce que les deux pions occupent le même sommet, comme ici :

%3 1 2 1->2 3 1->3 4 1->4 2->3 3->4 7 😷👵 3->7 11 3->11 5 4->5 6 4->6 4->7 5->6 6->7 8 7->8 9 8->9 10 8->10 9->10 10->11

Y a-t-il une stratégie gagnante ? Si oui, pour qui ?

Exemple

Sur le graphe du début, le Docteur est placé en F et River Song est placée en B :

%3 A B ⛂ A->B E A->E C C->B D D->C E->B E->C E->D F ⛀ F->A F->D F->E

Le Docteur (qui commence) a trois choix : A, D ou E

S'il choisit A, S'il choisit D, S'il choisit E,
%3 A ⛀ B ⛂ A->B E A->E C C->B D D->C E->B E->C E->D F F->A F->D F->E %3 A B ⛂ A->B E A->E C C->B D ⛀ D->C E->B E->C E->D F F->A F->D F->E %3 A B ⛂ A->B E ⛀ A->E C C->B D D->C E->B E->C E->D F F->A F->D F->E
alors River Song pose son jeton sur celui du Docteur et gagne : alors River Song mène son jeton en C : alors River Song pose son jeton sur celui du Docteur et gagne :
%3 A ⛃ B A->B E A->E C C->B D D->C E->B E->C E->D F F->A F->D F->E %3 A B A->B E A->E C ⛂ C->B D ⛀ D->C E->B E->C E->D F F->A F->D F->E %3 A B A->B E ⛃ A->E C C->B D D->C E->B E->C E->D F F->A F->D F->E
et le Docteur n'a pas d'autre choix que poser son jeton sur celui de River Song
%3 A B A->B E A->E C ⛁ C->B D D->C E->B E->C E->D F F->A F->D F->E
et le Docteur perd le jeu.

Sur ce graphe, River Song dispose donc d'une stratégie gagnante : jouer C si le Docteur va en D, sinon, jouer le même sommet que le Docteur.

Quel est le DAG le plus simple sur lequel le Docteur a une stratégie gagnante ?