Corrigé CCINP 2025 Informatique MP — Partie V (Q29 à Q38) : Jeu sur un graphe

Q29. Variant : le nombre d'arêtes non attribuées, entier naturel égal à $|A|$ au départ. Chaque coup attribue une arête qui ne l'était pas : il diminue de $1$. Quand il est nul, la configuration est finale et la partie s'arrête. Toute partie compte donc exactement $|A|$ coups.

Q30. Supposons $|S|⩾2$ (avec un seul sommet, il n'y a aucune arête et les deux joueurs ont le même graphe : le cas est dégénéré). Pour un sous-graphe $G^{\prime }$ connexe, ${\overline{b}}_{\lim }(G^{\prime })$ est, d'après Q28, le poids d'une arête $a^{\prime }$ de son arbre couvrant de poids maximal, donc d'une arête de $G^{\prime }$ : c'est un réel, et non $\pm \infty$.

• Si $G_1$ et $G_{-1}$ sont tous deux connexes, leurs valeurs sont $p(a_1)$ et $p(a_{-1})$ avec $a_1$ arête de $G_1$ et $a_{-1}$ arête de $G_{-1}$. Les ensembles d'arêtes des deux joueurs étant disjoints, $a_1\ne a_{-1}$, et l'injectivité de $p$ donne $p(a_1)\ne p(a_{-1})$ : l'un des deux gagne.
• Si un seul est connexe, sa valeur est un réel et celle de l'autre vaut $-\infty$ : le joueur connexe gagne.
• Si aucun n'est connexe, les deux valeurs valent $-\infty$ : match nul.

Le match nul se produit donc exactement quand aucun joueur n'obtient un graphe connexe, la connexité s'entendant sur tous les sommets de $S$ (un sommet isolé suffit à la rompre).

Q31. Sur l'île de Korße, faisons jouer à MaxDébit la stratégie gloutonne, et à MinLatence les trois arêtes issues du sommet $2$ :

• MaxDébit prend $\{1,3\}$ ($8$) ; MinLatence prend $\{0,2\}$ ($2$) ;
• MaxDébit prend $\{0,3\}$ ($7$) ; MinLatence prend $\{1,2\}$ ($5$) ;
• MaxDébit prend $\{0,1\}$ ($6$) ; MinLatence prend $\{2,3\}$ ($3$).

MaxDébit (tirets) a le triangle $\{0,1,3\}$ et le sommet $2$ isolé : son graphe n'est pas connexe, ${\overline{b}}_{\lim }(G_1)=-\infty$. MinLatence (pointillés) a l'étoile de centre $2$, arbre couvrant : ${\overline{b}}_{\lim }(G_{-1})=2$. MinLatence gagne. Le résultat ne dépend même pas de l'ordre de MinLatence : les arêtes $8,7,6$ sont les trois plus lourdes, et MinLatence n'y touchant pas, la stratégie gloutonne les prend toujours. La stratégie gloutonne n'est donc pas gagnante : elle ignore la connexité, qui est le premier critère. Pourtant MaxDébit a une stratégie gagnante sur ce graphe (la fonction score de Q34 vaut $1$ sur la configuration initiale) : dans la partie ci-dessus, il lui suffisait de prendre $\{2,3\}$ au lieu de $\{0,1\}$ au dernier coup, pour obtenir l'étoile de centre $3$ (${\overline{b}}_{\lim }=3$) en laissant à MinLatence le triangle $\{0,1,2\}$, qui isole $3$.

Q32. La partie est terminée quand aucune case de etat ne vaut $0$ :

def finale(c):
    t, etat = c
    for x in etat:
        if x == 0:
            return False
    return True

Coût $O(m)$. On peut aussi écrire return 0 not in etat. Essais : True pour la figure 5(b), False pour la configuration (-1, [-1, 0, 0, 1, 1, 0]). La fonction score du sujet l'appelle est_finale : c'est la même.

Q33. Le joueur t peut prendre chaque arête libre ; la configuration obtenue est contrôlée par l'adversaire -t :

def configurations_suivantes(c):
    t, etat = c
    suivantes = []
    for k in range(len(etat)):
        if etat[k] == 0:
            suiv = etat.copy()
            suiv[k] = t
            suivantes.append((-t, suiv))
    return suivantes

Chaque configuration suivante a sa propre liste, copie de etat modifiée en une case : c n'est jamais modifiée, et les configurations renvoyées ne se partagent pas leurs listes. Coût $O(m^2)$ (au plus $m$ copies de taille $m$). Essai : depuis (-1, [-1, 0, 0, 1, 1, 0]), on obtient les trois configurations (1, [-1, -1, 0, 1, 1, 0]), (1, [-1, 0, -1, 1, 1, 0]), (1, [-1, 0, 0, 1, 1, -1]), et c est intacte.