X ENS Informatique Commune MP PC PSI 2026Sujet

Cycles et unification

• A0.Les arcs sortants d'un sommet donné sont étiquetés par des entiers consécutifs en partant de 0.
• A1. G est acyclique.

• -L'expression len(a) renvoie la longueur n.
• -L'expression a[i] désigne le i-ième élément de la liste, pour 0 ≤ i < n.
• -L'instruction a[i] = v affecte la valeur v au i-ième élément de la liste, pour 0 ≤ i < n.
• -L'instruction a.append(e) ajoute l'élément e à la fin de la liste a.
• -L'expression a.pop() supprime et renvoie le dernier élément de la liste a.

• -Le test (k in d) renvoie True si k est une clé du dictionnaire d, et False sinon.
• -L'expression d [k] renvoie la valeur associée à la clé k dans le dictionnaire d, le cas échéant.
• -L'instruction d[k] = v affecte la valeur v à la clé k dans le dictionnaire d.

Partie I. Détection de cycles

• -époque et sortie sont des dictionnaires associant un entier à chaque sommet de G,
• -présent et compteur sont des entiers.

• A2.époque [s] ⩽ présent, pour tout sommet s de G.
• A3.époque [s] ⩽ époque [t] pour tout arc s → t de G.
• A4.époque [s] = époque [t] ⇒ sortie[s] ⩾ sortie[t] pour tout arc s → t de G.

for s in G.keys():
    sortie[s] = 0
    époque[s] = 0
compteur = 0
présent = 1
pp('a')

présent += 1

présent += 1
pp(s)

Figure 1 - Exemple de graphe avec sa représentation Python.

# Variables globales.
# L'initialisation (cachée) satisfait les invariants.
G = { ... }
sortie = { ... }
époque = { ... }
présent = 0
compteur = 0
def pp(s):
    """
    Effectue un parcours en profondeur à partir de ˋsˋ,
    affecte l'époque ˋprésentˋ à tous les sommets visités,
    ainsi qu'une certaine numérotation dans ˋsortieˋ.
    """
    global compteur # époque, sortie et présent sont implicitement globales
    époque[s] = présent
    for t in G[s]:
        if époque[t] != présent:
            pp(t)
    sortie[s] = compteur
    compteur += 1

Partie II. Unification

def fn(s):
    if len(G[s]) == 0: # sommet libre
        return s
    elif len(G[s]) == 1: # sommet lié
        return fn(G[s][0])
    else: # sommet interne
        return (fn(G[s][0]), fn(G[s][1]))

def accessible(s, t):
    """Renvoie True si, et seulement si, il existe un chemin de s à t."""
    global présent, compteur
    if (époque[s] > époque[t] or
            (époque[s] == époque[t] and sortie[s] < sortie[t])):
        return False
    présent += 1
    pp(s)
    return époque[t] == présent
def lier (u, s):
    """
    Ajoute l'arc u -> s s'il ne crée pas de cycle.
    Signale l'ajout réussi en renvoyant True.
    """
    if not accessible(s, u):
        G[u].append(s)
        return True
    return False

def unif(P):
    """
    Ajoute des arcs dans G jusqu'à obtenir une extension solution de P.
    Renvoie False si P n'a pas de solution. Renvoie True sinon.
    """
    while len(P) > 0:
        s, t = P.pop()
        if len(G[s]) == 1:
            P.append((G[s][0], t))
        elif len(G[t]) == 1:
            P.append((s, G[t][0]))
        elif len(G[s]) == 2 and len(G[t]) == 2:
            P.append((G[s][0], G[t][0]))
            P.append((G[s][1], G[t][1]))
        elif len(G[s]) == 0:
            ... # à compléter
        else:
            P.append((t, s))
    return True

Partie III. Représentation relationnelle

• -une table sommets dont les colonnes sont
  • -id, clé primaire entière,
  • -degré, entier, représente le degré sortant,
  • -sortie, entier,
  • -époque, entier ;
• -une table arcs dont les colonnes sont
  • -étiquette, entier,
  • -source, clé étrangère vers sommets,
  • -cible, clé étrangère vers sommets.