QCM - Jeux à deux joueurs

QCM - Jeux à deux joueurs et attracteurs

Question 1. Dans la modélisation d'un jeu à deux joueurs, le graphe $G = (S, A)$ est :

Un graphe non orienté quelconqueUn graphe orienté bipartiUn arbre binaireUn graphe complet

Question 2. Tout graphe orienté acyclique possède :

Un cycleUn puitsUn chemin hamiltonienUn sommet de degré pair

Question 3. Une stratégie pour le joueur $i$ est :

Un chemin du grapheUne fonctionUn ordre sur les sommetsUn sous-graphe

Question 4. On note $S_i$ l'ensemble des sommets où le joueur $i$ joue. Dans l'algorithme de calcul des attracteurs, $A_{n}(i)$ contient : (plusieurs réponses possibles)

Les sommets de $S_i$ ayant au moins un successeur dans $A_n(i)$Les sommets de $S_i$ ayant tous les successeurs dans $A_n(i)$Les sommets de $S_{1-i} \setminus T$ dont au moins un successeur est dans $A_n(i)$Les sommets de $S_{1-i} \setminus T$ dont tous les successeurs sont dans $A_n(i)$

Question 5. Si un jeu n'a ni état nul ni cycle, que peut-on dire de $A(0)$ et $A(1)$ ?

$A(0) = A(1)$$A(0) \cup A(1) = S$$A(0) \cap A(1) = S$On ne peut rien dire

Question 6. Quelle est la complexité du calcul des attracteurs sur un graphe $G = (S, A)$ ?

$O(|S|)$$O(|S| + |A|)$$O(|S|^2)$$O(|S| \cdot |A|)$

Question 7.

À partir du graphe ci-dessus (avec $s_0 = 0$), quels sommets appartiennent à l'attracteur $A(0)$ ?

$\{0, 2, 4, 5, 7\}$$\{0, 1, 2, 4, 5, 7\}$$\{0, 2, 3, 4, 5, 7\}$$\{2, 4, 5, 7\}$