FR 
EnglishPar défaut
Українська
Polski💞 Couplage biparti — Chemins augmentants
Associez les nœuds de gauche aux nœuds de droite le long des arêtes en trouvant répétitivement des chemins augmentants. Observez les paires assorties se verrouiller et les sommets non assortis tenter de nouveaux chemins alternants jusqu'à atteindre le couplage maximum.
À propos du couplage biparti
Un graphe biparti sépare ses sommets en deux ensembles disjoints — ici, les candidats à gauche et les postes à droite — avec des arêtes reliant uniquement les deux ensembles, jamais à l'intérieur d'un même ensemble. Un couplage est un sous-ensemble d'arêtes dans lequel aucun sommet n'apparaît plus d'une fois ; un couplage maximum est le plus grand sous-ensemble de ce type réalisable pour un graphe donné. La méthode classique pour agrandir un couplage consiste à rechercher répétitivement un chemin augmentant : un trajet qui commence et se termine sur des sommets non assortis et alterne entre arêtes non assorties et arêtes assorties. Inverser chaque arête le long de ce chemin augmente la taille du couplage d'exactement un, et un couplage est prouvablement maximum précisément lorsqu'il ne reste plus de chemin augmentant. Exécuter cette recherche depuis chaque sommet non assorti une fois prend un temps O(V·E) ; l'algorithme de Hopcroft–Karp améliore cela à O(E√V) en trouvant plusieurs chemins augmentants les plus courts par phase au lieu d'un seul. Au-delà de la théorie des graphes, le couplage biparti modélise l'attribution d'emplois, l'allocation de cours, et les problèmes de couplage stable qui sous-tendent les systèmes d'affectation scolaire et de résidence hospitalière.
Questions fréquentes
Qu'est-ce qu'un chemin augmentant dans le couplage biparti ?
Un chemin augmentant est une séquence d'arêtes qui commence et se termine sur des sommets non assortis, alternant entre des arêtes hors du couplage courant et des arêtes qui en font partie. En trouver un et inverser le statut de chaque arête le long de celui-ci — assortie devient non assortie et vice versa — augmente toujours la taille totale du couplage d'exactement un.
Pourquoi inverser un chemin augmentant augmente-t-il la taille du couplage de un ?
Un chemin augmentant a toujours une arête non assortie de plus qu'une arête assortie, car il commence et se termine sur des sommets non assortis. Échanger le statut de chaque arête du chemin convertit donc k arêtes non assorties en assorties et k−1 arêtes assorties en non assorties, un gain net d'exactement une arête assortie, tandis que chaque sommet du chemin reste couvert par exactement une arête assortie.
À quelle vitesse l'algorithme de Hopcroft–Karp fonctionne-t-il par rapport à une approche naïve ?
L'approche naïve — exécuter répétitivement un seul chemin augmentant par recherche en profondeur depuis chaque sommet non assorti — prend un temps O(V·E) dans le pire des cas, car jusqu'à V chemins augmentants peuvent être nécessaires et chaque recherche coûte O(E). Hopcroft–Karp trouve à la place un ensemble maximal de chemins augmentants les plus courts et disjoints en sommets par phase à l'aide d'une seule passe BFS+DFS, ne nécessitant que O(√V) phases, pour un total de O(E√V) — une accélération substantielle sur les grands graphes.
Quels problèmes du monde réel sont résolus par le couplage biparti ?
Le couplage biparti sous-tend l'attribution d'emplois et de tâches (associer des travailleurs à des rôles compatibles), les admissions universitaires et l'affectation des résidences hospitalières (un précurseur de l'algorithme de couplage stable de Gale–Shapley), et les problèmes de flux réseau tels que la planification et l'allocation de ressources, où maximiser le nombre de paires assorties maximise directement l'utilisation efficace de ressources limitées.
Trouvez un couplage maximum dans un graphe biparti via des chemins augmentants inversant arêtes assorties et non assorties — la base de l'attribution d'emplois.
3D · Moteur de rendu Three.js / WebGL · Cible 60 FPS · fonctionne entièrement côté client, sans installation