Couplages - preuves (A)

Soit $M = \{e_1, e_2, \dots, e_k\}$ un couplage de taille $k = |M|$.

Étape 1 : Définition des arêtes

Par définition, chaque arête $e_i \in M$ possède exactement deux extrémités (deux sommets).

Étape 2 : Propriété d'indépendance

La définition d'un couplage impose que deux arêtes distinctes de $M$ n'ont jamais d'extrémité en commun. Cela signifie que les ensembles de sommets incidents à chaque arête $e_i$ sont disjoints deux à deux.

Étape 3 : Somme des sommets

Le nombre total de sommets saturés est la somme des extrémités de chaque arête du couplage.

Puisque les ensembles d'extrémités sont disjoints :

$\text{Nombre de sommets saturés} = \sum_{e \in M} 2 = 2 \times |M|$

Conclusion :

Le nombre de sommets saturés est toujours égal à deux fois la cardinalité du couplage.

Soit $M$ un couplage parfait dans $G$.

Étape 1 : Définition de la saturation totale

Un couplage est dit parfait si l'ensemble de tous les sommets $S$ est saturé. Autrement dit, l'ensemble des sommets saturés par $M$ est exactement $S$.

Étape 2 : Utilisation de la relation de cardinalité

D'après la propriété fondamentale des couplages, le nombre de sommets saturés par un couplage $M$ est $2|M|$.

Étape 3 : Conclusion

Puisque $S$ est l'ensemble des sommets saturés :

$|S| = 2|M|$

Comme $|M|$ est un entier, $|S|$ est un multiple de 2.

Conclusion :

Un graphe possédant un couplage parfait a nécessairement un nombre pair de sommets.

Soit $M$ un couplage maximum de $G$. Supposons par l'absurde que $M$ ne soit pas maximal.

Étape 1 : Définition de la non-maximalité

Si $M$ n'est pas maximal (au sens de l'inclusion), cela signifie qu'il existe une arête $e \in A \setminus M$ telle que $M' = M \cup \{e\}$ est encore un couplage valide.

Étape 2 : Comparaison des cardinalités

Si $M' = M \cup \{e\}$ avec $e \notin M$, alors :

$|M'| = |M| + 1$

Donc $|M'| > |M|$.

Étape 3 : Contradiction

Nous avons trouvé un couplage $M'$ de taille strictement supérieure à $M$. Or, $M$ est supposé être un couplage maximum (c'est-à-dire qu'il n'existe aucun couplage de taille supérieure). C'est une contradiction.

Conclusion :

L'hypothèse que $M$ n'est pas maximal est fausse. Tout couplage maximum est donc maximal.

Pour prouver qu'une implication universelle est fausse, il suffit d'exhiber un contre-exemple.

Étape 1 : Construction du graphe

Considérons le graphe chemin $P_4$ avec les sommets $S=\{1, 2, 3, 4\}$ et les arêtes $A=\{\{1,2\}, \{2,3\}, \{3,4\}\}$.

Étape 2 : Choix d'un couplage maximal

Soit $M_1 = \{\{2,3\}\}$.

• Les sommets 2 et 3 sont saturés.
• L'arête $\{1,2\}$ ne peut être ajoutée car 2 est déjà saturé.
• L'arête $\{3,4\}$ ne peut être ajoutée car 3 est déjà saturé.
• Donc $M_1$ est maximal (on ne peut rien ajouter). Sa taille est 1.

Étape 3 : Existence d'un couplage plus grand

Considérons $M_2 = \{\{1,2\}, \{3,4\}\}$.

• C'est un couplage valide.
• Sa taille est 2.

Conclusion :

$M_1$ est un couplage maximal, mais il n'est pas maximum car $|M_1| < |M_2|$. La proposition est donc fausse.

Soit $P = (x_0, x_1, \dots, x_{2k+1})$ une chaîne augmentante par rapport à $M$.

Étape 1 : Propriétés de la chaîne augmentante

Par définition :

1. Les extrémités $x_0$ et $x_{2k+1}$ sont insaturées (libres).
2. La chaîne est alternée : les arêtes de rang impair $\{x_0, x_1\}, \{x_2, x_3\}, \dots$ ne sont pas dans $M$, et les arêtes de rang pair $\{x_1, x_2\}, \{x_3, x_4\}, \dots$ sont dans $M$.
3. La longueur de la chaîne est impaire. Elle contient $k$ arêtes de $M$ et $k+1$ arêtes hors de $M$.

Étape 2 : Construction du nouveau couplage $M'$

Considérons l'ensemble $M'$ obtenu en prenant la différence symétrique $M \Delta P$ (les arêtes de la chaîne qui étaient dans $M$ en sortent, celles qui n'y étaient pas y entrent).

$M' = (M \setminus P) \cup (P \setminus M)$

Étape 3 : Vérification de la validité

• Les sommets internes de la chaîne ($x_1, \dots, x_{2k}$) gardent leur degré (1) dans le couplage (on remplace une arête incidente par l'autre).
• Les extrémités $x_0$ et $x_{2k+1}$, initialement de degré 0 dans $M$ (insaturés), deviennent de degré 1 dans $M'$ (saturés par la première et la dernière arête de la chaîne).
• Les sommets hors de la chaîne ne sont pas affectés.

Donc $M'$ est bien un couplage.

Étape 4 : Cardinalité

$M$ contenait $k$ arêtes de la chaîne. $M'$ en contient $k+1$.

$|M'| = |M| - k + (k+1) = |M| + 1$

Conclusion :

Nous avons construit un couplage $M'$ strictement plus grand que $M$. Donc $M$ n'était pas maximum.

Supposons qu'il existe un couplage $M$ qui sature $X$. Soit $U \subseteq X$ un sous-ensemble quelconque de sommets.

Étape 1 : Définition de l'application injective

Puisque $M$ sature $X$, chaque sommet $x \in U$ est l'extrémité d'une arête $\{x, y\} \in M$.

Définissons l'ensemble $M(U) = \{ y \in Y \mid \exists x \in U, \{x, y\} \in M \}$. C'est l'ensemble des partenaires des sommets de $U$ dans le couplage.

Étape 2 : Propriété d'un couplage

Dans un couplage, deux sommets distincts de $X$ ne peuvent pas être reliés au même sommet de $Y$. L'association définie par $M$ est donc une bijection entre $U$ et $M(U)$.

Par conséquent, $|M(U)| = |U|$.

Étape 3 : Relation d'inclusion

Par définition, si $y$ est un partenaire d'un $x \in U$, alors $y$ est un voisin de $x$.

Donc, l'ensemble des partenaires $M(U)$ est un sous-ensemble de l'ensemble des voisins $N(U)$.

$M(U) \subseteq N(U)$

Étape 4 : Conclusion sur les cardinalités

Puisque $M(U) \subseteq N(U)$, on a $|M(U)| \le |N(U)|$.

En combinant avec l'étape 2 ($|M(U)| = |U|$), on obtient :

$|U| \le |N(U)|$

Conclusion :

La condition de Hall est une condition nécessaire pour l'existence d'un couplage saturant $X$.

Soit $G=(X \cup Y, A)$ un graphe biparti $k$-régulier avec $k \ge 1$.

Étape 1 : Comptage des arêtes incidentes à $U$

Soit $U \subseteq X$. Calculons le nombre d'arêtes $m$ ayant une extrémité dans $U$.

Puisque chaque sommet a un degré $k$ :

$m = k \times |U|$

Étape 2 : Destination des arêtes

Par définition du voisinage $N(U)$, toutes ces $m$ arêtes ont leur autre extrémité dans $N(U) \subseteq Y$.

Étape 3 : Majoration par les sommets de $N(U)$

Le nombre maximal d'arêtes pouvant arriver dans $N(U)$ est la somme des degrés des sommets de $N(U)$.

Puisque le graphe est $k$-régulier, chaque sommet de $N(U)$ a un degré $k$.

Le nombre d'arêtes incidentes à $N(U)$ est donc $k \times |N(U)|$.

Les $m$ arêtes partant de $U$ étant un sous-ensemble des arêtes incidentes à $N(U)$, on a :

$m \le k \times |N(U)|$

Étape 4 : Combinaison

On remplace $m$ par sa valeur :

$k \times |U| \le k \times |N(U)|$

Puisque $k \ge 1$, on peut diviser par $k$ :

$|U| \le |N(U)|$

Conclusion :

La condition de Hall est vérifiée pour tout $U \subseteq X$. D'après le théorème de Hall, le graphe admet un couplage saturant $X$. Comme le graphe est régulier, $|X|=|Y|$, donc ce couplage est parfait.

Considérons l'algorithme où les hommes ($X$) proposent aux femmes ($Y$).

Étape 1 : Monotonie des propositions

Chaque homme $x \in X$ propose aux femmes dans l'ordre décroissant de sa liste de préférences.

Il ne propose à une femme suivante que s'il a été rejeté par la précédente.

Il ne propose jamais deux fois à la même femme.

Étape 2 : Finitude de l'espace de recherche

Soit $n$ la taille des ensembles $X$ et $Y$. Chaque homme a une liste de préférences de longueur $n$.

Le nombre total de propositions possibles que l'ensemble des hommes peut faire est donc borné par $n \times n = n^2$.

Étape 3 : Progression

À chaque étape de l'algorithme (si celui-ci ne s'est pas arrêté), au moins une nouvelle proposition est faite. Le nombre total de propositions faites augmente donc strictement.

Conclusion :

Puisque le nombre total de propositions ne peut dépasser $n^2$, l'algorithme doit nécessairement s'arrêter après un nombre fini d'étapes.

Supposons que l'algorithme se termine et qu'il existe un homme $x \in X$ qui n'est pas couplé (libre).

Étape 1 : Analyse de l'homme libre

Si $x$ est libre à la fin, cela signifie qu'il a proposé à toutes les femmes de sa liste (tous les $y \in Y$) et qu'il a été rejeté par chacune d'elles.

Étape 2 : Analyse des femmes

Une femme ne rejette une proposition que si :

1. Elle en tient déjà une meilleure (fiancée).
2. Elle reçoit une meilleure proposition (elle change de fiancé mais reste fiancée).

Une fois qu'une femme reçoit une première proposition, elle reste fiancée (à quelqu'un) jusqu'à la fin. Elle ne redevient jamais libre.

Étape 3 : Contradiction (Principe des tiroirs)

Pour que $x$ ait été rejeté par toutes les femmes, il faut que toutes les femmes soient fiancées à d'autres hommes à la fin de l'algorithme.

Il y a $n$ femmes et elles sont toutes fiancées. Cela requiert $n$ hommes distincts.

Or, si $x$ est libre, il n'y a que $n-1$ hommes fiancés au maximum.

Il est impossible que $n$ femmes soient fiancées avec seulement $n-1$ hommes disponibles.

Conclusion :

L'hypothèse est fausse. Tous les hommes (et donc toutes les femmes) sont couplés. Le couplage est parfait.

Soit $M$ le couplage final. Raisonnons par l'absurde en supposant qu'il existe une paire instable $(x, y) \notin M$.

Soient $(x, y_{current}) \in M$ et $(x_{current}, y) \in M$ les couples formés par l'algorithme.

Hypothèse d'instabilité :

1. $x$ préfère $y$ à $y_{current}$.
2. $y$ préfère $x$ à $x_{current}$.

Étape 1 : Historique des propositions de $x$

Puisque $x$ propose aux femmes dans l'ordre décroissant de ses préférences et qu'il a fini avec $y_{current}$, il a nécessairement proposé à $y$ avant de proposer à $y_{current}$ (car il préfère $y$).

Étape 2 : Réaction de $y$

Si $x$ a proposé à $y$ et qu'ils ne sont pas mariés ensemble à la fin, c'est que $y$ a rejeté $x$ (soit immédiatement, soit plus tard).

Une femme ne rejette $x$ que si elle a une proposition d'un homme $z$ qu'elle préfère à $x$.

Étape 3 : Évolution des fiançailles de $y$

Les femmes améliorent (ou gardent) la qualité de leur partenaire au fil de l'algorithme. Si $y$ a rejeté $x$ pour un certain $z$, alors son partenaire final $x_{current}$ est soit $z$, soit quelqu'un qu'elle préfère encore plus que $z$.

Par transitivité, $y$ préfère $x_{current}$ à $x$.

Étape 4 : Contradiction

L'étape 3 contredit la deuxième condition de l'hypothèse d'instabilité ($y$ préfère $x$ à $x_{current}$).

Conclusion :

Il ne peut pas exister de paire instable. Le couplage $M$ est stable.