Corrigé X-ENS 2025 Informatique C MPI — Partie III (Q32 à Q33) : Couplages parfaits, méthode probabiliste

Partie à composer en C, en réutilisant la partie II (read_sqmatrix, write_sqmatrix, determinant, en $O(n^4)$). Un couplage parfait couvre tous les sommets. Un graphe non orienté de sommets $0,\dots ,n-1$ est donné par sa matrice d'adjacence linéarisée ($A_{i,j}=1$ si $\{i,j\}$ est une arête, $0$ sinon). Sa matrice de Tutte $T(G)$ a pour coefficients $X_{i,j}$ si $i<j$ et $\{i,j\}$ est une arête, $-X_{j,i}$ si $i>j$ et $\{i,j\}$ est une arête, $0$ sinon (en particulier sur la diagonale), les $X_{i,j}$ ($i<j$) étant des variables.

Théorème de Tutte : $G$ a un couplage parfait si et seulement si $\det T(G)$ n'est pas le polynôme nul. Lemme de Schwartz--Zippel : si $P$ est un polynôme réel non nul de degré total $d$, et si ses variables sont tirées uniformément et indépendamment dans un ensemble fini non vide $S$, alors $P$ s'annule avec une probabilité au plus $d/|S|$.

Fournis : int rand_range(int n), entier uniforme de $\{0,\dots ,n\}$ en $O(1)$ ; la déclaration int t[m]; en $O(m)$ ; log2 de <math.h>.

Q32. Écrire int tirage_tutte(int n, int *A) : déterminant de $T(G)$ où chaque $X_{i,j}$ est tiré au hasard dans $\{0,1,\dots ,n^2\}$, en $O(n^4)$.
Q33. Écrire bool parfait(int n, int *A, int p), qui décide si $G$ a un couplage parfait avec une probabilité d'erreur inférieure à $2^{-p}$ (à justifier), en $O(p{n}^4/{\log }_{2}n)$ (à justifier).