Un attracteur à la main

Initialisation : $A = {f}$ .
Itération 1 : On cherche les sommets hors de $A$ pouvant entrer dans l'attracteur.
Le sommet $e \in S_{1}$ possède un unique successeur $f \in A$ . Par la règle 2, $e$ entre dans $A$ (choix du coup gagnant : $e \to f$ ). $A = {f, e}$ .
Itération 2 :
Le sommet $d \in S_{2}$ possède les successeurs $e \in A$ et $g \in / A$ . La règle 3 impose que tous les successeurs soient dans $A$ . Comme $g \in / A$ , $d$ n'entre pas.
Le sommet $b \in S_{2}$ a pour successeurs $c \in / A$ et $e \in A$ . De même, $b$ n'entre pas.
Le sommet $c \in S_{1}$ a pour successeur $d \in / A$ , il n'entre pas.
Le sommet $a \in S_{1}$ a pour successeurs $b, d \in / A$ , il n'entre pas.
Fin : L'ensemble $A$ ne change plus. $Attr_{1} ({f}) = {f, e}$ .
Analyse de l'état $a$ : L'état $a$ n'appartient pas à l'attracteur $Attr_{1}$ , il n'est donc pas gagnant pour $J_{1}$ . Calculons l'attracteur de $J_{2}$ pour $F_{2} = {g}$ :
$A_{2} = {g}$ .
Le sommet $d \in S_{2}$ a pour successeurs $e$ et $g \in A_{2}$ . Pour $J_{2}$ , un seul successeur suffit $⟹ d$ entre dans $A_{2}$ . $A_{2} = {g, d}$ .
Le sommet $c \in S_{1}$ a pour unique successeur $d \in A_{2}$ . Pour $J_{1}$ , tous les successeurs doivent être dans $A_{2} ⟹ c$ entre dans $A_{2}$ . $A_{2} = {g, d, c}$ .
Le sommet $b \in S_{2}$ a pour successeurs $c \in A_{2}$ et $e \in / A_{2} ⟹ b$ entre dans $A_{2}$ (car $J_{2}$ peut choisir d'aller en $c$ ). $A_{2} = {g, d, c, b}$ .
Le sommet $a \in S_{1}$ a pour successeurs $b, d \in A_{2}$ . Tous ses successeurs sont dans $A_{2} ⟹ a$ entre dans $A_{2}$ . L'état $a$ appartient à $Attr_{2} ({g})$ . L'état $a$ est donc une position gagnante pour le joueur $J_{2}$ .

Énoncé

Corrigé

Exercices semblables