Les graphes : modèle et représentations

Degrés sortants : $d^{+}(u)=1$, $d^{+}(v)=2$, $d^{+}(w)=1$, $d^{+}(x)=1$ (la boucle) — somme $5$. Degrés entrants : $d^{-}(u)=1$ (depuis $w$), $d^{-}(v)=1$, $d^{-}(w)=1$, $d^{-}(x)=2$ ($v$ et la boucle) — somme $5=|A|$. ✓ Chemins de $u$ à $x$ : $u,v,x$ (longueur $2$) ; $u,v,x,x$ (longueur $3$, via la boucle). Cycles : $u\to v\to w\to u$ (longueur $3$) et la boucle $x\to x$ (longueur $1$). (Compter séparément les deux familles de degrés, puis vérifier l'égalité des sommes : le contrôle systématique qui attrape les arcs oubliés — l'équivalent graphe du « mêmes éléments » des tris.)

def degres_entrants(G: dict) -> dict:
    d = {s: 0 for s in G}            # tous présents, même degré entrant nul !
    for u in G:
        for v in G[u]:
            d[v] += 1
    return d

assert degres_entrants({"u": ["v"], "v": ["w", "x"],
                        "w": ["u"], "x": ["x"]}) \
       == {"u": 1, "v": 1, "w": 1, "x": 2}

Coût : $O(n+m)$, un parcours complet du graphe. L'asymétrie est structurelle : les listes d'adjacence stockent les arcs chez leur origine — $d^{+}(s)$ est une simple longueur de liste ($O(1)$), tandis que $d^{-}(s)$ exige de fouiller toutes les listes. L'initialisation à zéro pour tous les sommets est le piège de l'exercice : sans elle, un sommet sans arc entrant (comme une page web que personne ne cite) manquerait du dictionnaire. (Quand une application interroge sans cesse les prédécesseurs — « qui pointe vers cette page ? » —, on stocke aussi le graphe inverse : de l'espace contre du temps, l'arbitrage du chapitre 10.)

def depuis_aretes(aretes: list, n: int) -> dict:
    G = {s: [] for s in range(n)}
    for (u, v) in aretes:
        G[u].append(v)
        G[v].append(u)               # non orienté : les DEUX sens
    return G

G = depuis_aretes([(0, 1), (0, 2), (1, 2), (1, 3)], 5)
# G == {0: [1, 2], 1: [0, 2, 3], 2: [0, 1], 3: [1], 4: []}
M = listes_vers_matrice(G, 5)
assert all(M[i][j] == M[j][i] for i in range(5) for j in range(5))   # symétrie
assert sum(len(G[s]) for s in G) == 2 * 4                            # 2 |A|
assert sum(sum(ligne) for ligne in M) == 2 * 4

Les trois assertions sont les invariants de cohérence d'un graphe non orienté : matrice symétrique, somme des degrés $=2|A|$ dans les deux représentations. Le sommet $4$, isolé, doit exister avec sa liste vide — c'est l'initialisation for s in range(n) qui le garantit, pas les arêtes. (La liste d'arêtes est le format d'échange — celui des fichiers — et les deux représentations du cours sont les formats de travail : la conversion d'entrée est toujours la première fonction d'un projet graphes, et ses invariants le premier jeu de tests.)

(a) Listes, sans hésitation : $m\approx 10^{11}$ — les listes occupent $O(n+m)\approx 10^{11}$ cellules (déjà énorme, mais c'est l'information elle-même) ; la matrice exigerait $n^2=10^{18}$ cases remplies à $0,00002\%$ : exclu.

(b) Matrice : le graphe est complet par construction — $m=\left(\genfrac{}{}{0ex}{}{300}{2}\right)\approx 45000=n^2/2$ : la matrice ($90000$ cases) ne gaspille rien, donne « qui a battu qui » en $O(1)$, et la symétrie n'est pas requise (graphe orienté des victoires). Les listes n'apporteraient rien : quand $m\approx n^2$, leurs avantages s'évanouissent.

(c) Le cas piège : le test d'arc en $O(1)$ plaide pour la matrice, mais $n^2=10^{14}$ cases pour $m\approx 1,5\cdot 10^7$ routes : inenvisageable. Réponse : listes d'adjacence — le test v in G[u] y coûte $O(d)=O(3)$, c'est-à-dire constant en pratique puisque le degré est borné. (La morale de (c) : les coûts en $O$ se lisent avec les ordres de grandeur du problème — un $O(d)$ avec $d\le 5$ vaut un $O(1)$, et la densité tranche toujours en premier.)

def est_symetrique(G: dict) -> bool:
    for u in G:
        for v in G[u]:
            if u not in G[v]:
                return False
    return True

def symetrise(G: dict) -> dict:
    H = {s: list(G[s]) for s in G}        # copie : G n'est pas modifié
    for u in G:
        for v in G[u]:
            if u not in H[v]:
                H[v].append(u)
    return H

G = {"a": ["b"], "b": [], "c": ["c"]}
assert not est_symetrique(G)
S = symetrise(G)
assert est_symetrique(S) and S["b"] == ["a"] and S["c"] == ["c"]

Coût de est_symetrique : pour chaque arc, un test u in G[v] en $O(d(v))$ — total $O({\sum }_u{\sum }_{v\in G[u]}d(v))$, au pire $O(nm)$ mais $O(m\cdot d_{\max })$ en général, parfaitement praticable sur graphes creux. La boucle c teste le cas limite : son retour, c'est elle-même — déjà présente, aucun doublon à créer. (La copie préalable de symetrise applique la discipline du chapitre 10 : fonction pure, source intacte ; et est_symetrique rejoint la collection d'invariants de cohérence de l'exercice 3 — un graphe « non orienté » non symétrique est une donnée corrompue à détecter tôt.)

def graphe_grille(p: int, q: int) -> dict:
    G = {}
    for i in range(p):
        for j in range(q):
            voisins = []
            for (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < p and 0 <= nj < q:      # rester dans la grille
                    voisins.append((ni, nj))
            G[(i, j)] = voisins
    return G

G = graphe_grille(2, 3)
assert len(G) == 6
assert sum(len(G[s]) for s in G) == 2 * 7            # 7 arêtes
assert sorted(G[(0, 0)]) == [(0, 1), (1, 0)]         # un coin : 2 voisins

Comptes : $|S|=pq$ ; les arêtes horizontales sont $p(q-1)$, les verticales $(p-1)q$, soit $|A|=2pq-p-q$ — pour $2\times 3$ : $12-2-3=7$. ✓ (La grille est le graphe des labyrinthes, des images — chapitre 8 : un pixel et ses voisins ! — et des plateaux de jeu ; le test des bornes 0 <= ni < p est exactement celui de somme_voisins du chapitre 8 : les graphes unifient des problèmes qu'on croyait distincts, c'est leur raison d'être. Noter les sommets-tuples : clés de dictionnaire licites, chapitre 2.)

On impose l'ordre $u<v<w$ pour ne compter chaque triangle qu'une fois :

def nb_triangles(G: dict) -> int:
    c = 0
    for u in G:
        for v in G[u]:
            if v > u:                          # chaque arête une fois
                for w in G[v]:
                    if w > v and w in G[u]:    # u < v < w, et l'arête de fermeture
                        c += 1
    return c

triangle_plus_queue = {0: [1, 2], 1: [0, 2, 3], 2: [0, 1], 3: [1]}
assert nb_triangles(triangle_plus_queue) == 1

Sans le filtre croissant, le triangle $\{0,1,2\}$ serait vu depuis chacune de ses $3!=6$ permutations. Coût : pour chaque arête $(u,v)$, on parcourt les voisins de $v$ avec un test d'appartenance w in G[u] en $O(d(u))$ — au total $O(m\cdot d_{\max }^2)$ dans cette version naïve ; remplacer les listes de voisins par des ensembles (test en $O(1)$, même idée que le dictionnaire du chapitre 2) ramène à $O(m\cdot d_{\max })$. (Sur le graphe d'un réseau social réel, ce comptage mesure la « cohésion » ; les versions industrielles reposent exactement sur cette boucle, ordonnée et optimisée — et le passage liste $\to$ ensemble des voisinages est le premier réglage qu'on y fait.)

Par récurrence sur $k$. Pour $k=1$ : $M[i][j]$ vaut $1$ s'il y a un arc — un chemin de longueur $1$ — et $0$ sinon. ✓ Supposons la propriété pour $k$. Par définition du produit :

$$(M^{k+1})[i][j]=\sum _{\ell \in S}(M^k)[i][\ell ]\cdot M[\ell ][j].$$

Le terme $\ell$ vaut (nombre de chemins de longueur $k$ de $i$ à $\ell$) $\times$ ($1$ si l'arc $\ell \to j$ existe) : c'est le nombre de chemins de longueur $k+1$ de $i$ à $j$ dont l'avant-dernier sommet est $\ell$. La somme sur $\ell$ les compte tous, chacun une fois (un chemin a un seul avant-dernier sommet). ✓

Vérification : pour le triangle, $M^3=I$ (le calcul donne la matrice identité) — de chaque sommet, exactement un chemin de longueur $3$ revient à lui-même (le tour complet), et aucun ne mène ailleurs. ✓ (Ce théorème est la passerelle entre l'algèbre et les graphes : compter des chemins devient multiplier des matrices — et l'exponentiation rapide du chapitre 5 compte les chemins de longueur $10^9$ en $30$ produits. C'est aussi lui qui fait des matrices d'adjacence l'outil des marches aléatoires et de l'algorithme de classement des pages web : la matrice du graphe, normalisée, itérée — le cours de probabilités y reviendra.)

def listes_vers_arcs(R: dict) -> dict:
    return {(u, v): R[u][v] for u in R for v in R[u]}

def arcs_vers_listes(P: dict, sommets: list) -> dict:
    R = {s: {} for s in sommets}
    for (u, v) in P:
        R[u][v] = P[(u, v)]
    return R

P = listes_vers_arcs({"a": {"b": 3}, "b": {"a": 3, "c": 1}, "c": {}})
assert P == {("a", "b"): 3, ("b", "a"): 3, ("b", "c"): 1}
assert ("a", "c") not in P                        # test d'arc : O(1)

Bilan : mémoire $O(m)$ (mieux que la matrice, comparable aux listes) ; test d'arc et lecture de poids en $O(1)$ (comme la matrice) ; ajout d'arc $O(1)$. L'opération sacrifiée : énumérer les voisins d'un sommet — il faudrait balayer tous les arcs ($O(m)$), là où les listes répondent en $O(d)$. Or les parcours du chapitre 13 ne font que ça : demander les voisins, des millions de fois. (D'où la conclusion mûre du chapitre : il n'y a pas de représentation universelle — listes pour parcourir, matrice ou dictionnaire d'arcs pour interroger, liste d'arêtes pour échanger ; un projet réel en maintient parfois deux, synchronisées, et le « choix éclairé des collections » du programme se joue exactement ici. En pratique, le dictionnaire de dictionnaires du cours cumule d'ailleurs le meilleur des deux : voisins en $O(d)$ et test-poids en $O(1)$ — c'est pourquoi il sera notre format au chapitre 14.)

(a) Métro : sommets $=$ stations par ligne (Châtelet-ligne-1 et Châtelet-ligne-4 sont deux sommets !) ; arêtes pondérées par le temps : tronçons entre stations consécutives ($\approx 2$ min) et arcs de correspondance entre les doublons d'une même station ($\approx 5$ min) — c'est ce dédoublement qui fait payer les changements, l'erreur de modélisation classique étant de l'omettre. Non orienté pour l'essentiel ; $n\approx 10^3$, $m\approx 3\cdot 10^3$ : listes d'adjacence pondérées, et l'algorithme sera Dijkstra (chapitre 14).

(b) Modules : sommets $=$ modules, arc orienté $u\to v$ si $u$ importe $v$ ; non pondéré. Une dépendance circulaire $=$ un cycle dans ce graphe orienté — la question est exactement « le graphe a-t-il un cycle ? » (chapitre 13). $n=10^3$, $m\approx 10^4$ : listes d'adjacence ; la matrice ($10^6$ cases) serait défendable mais sans bénéfice, aucun test d'arc isolé n'étant requis.

(c) Amis d'amis : sommets $=$ comptes, arêtes non orientées, non pondérées ; $n\approx 10^9$, $d\approx 200$ : listes d'adjacence obligatoires (exercice 4). « Les amis de mes amis » $=$ les sommets à distance exactement 2 — l'union des voisins des voisins, privée des voisins directs et de soi : deux niveaux de la boucle de voisinage, soit $O(d^2)\approx 40000$ opérations par requête, instantané même à l'échelle du réseau entier. (Trois énoncés en français, trois graphes différents par chacun de leurs attributs — orienté ou non, pondéré ou non, dédoublé ou non : la modélisation est la première décision algorithmique, et la plus lourde de conséquences ; les chapitres 13 et 14 fournissent les algorithmes, mais c'est ici que se gagne ou se perd leur pertinence.)